各講演20分（質疑応答時間を含む）
○印は登壇者
向き付けられた楕円曲線とは、楕円曲線とその自己準同型間への虚二次体の整環の埋め込みのペアのことである。2019年、ColoとKohelは、同じ整環により向き付けられ楕円曲線の同値類の集合がその整環のイデアル類群の単純推移作用を持つと述べ、それに基づく鍵共有方式OSIDHを提案した。本講演では、彼らが証明なしに述べた上記の主張には若干の修正が必要であることを示す。また、OSIDHがうまく動かないパラメータが存在することを示し、そのようなパラメータを避けるための十分条件を提示する。
超特異楕円曲線間の同種写像を求める計算問題に安全性の根拠を持つ同種写像暗号は，量子計算機に耐性のある暗号として期待されている．SIDHやCSIDHといった同種写像暗号の基本的な方式では，いずれも超特異楕円曲線を共有鍵として生成するため，超特異性判定を用いることで選択平文攻撃に対して判別可能となる（IND-CPA安全ではない）．本講演では，これらの方式にsmoothな位数を持つ点を付加することにより，IND-CPA安全な暗号方式となるSiGamalとC-SiGamalを提案する．本暗号方式は，秘密鍵である同種写像による像を計算し，smoothな位数を持つ点の離散対数問題を解くことをトラップドアとしている．IND-CPA安全性は，ある楕円曲線上の与えられた点が隠された同種写像による像であるかの判定問題の困難性に帰着される．
有限体上の超特異楕円曲線の自己準同型環と四元数環のmaximal orderの間にはDeuring対応と呼ばれる1対1対応がある. Kohel-Lauter-Petit-Tignol(KLPT)アルゴリズムは，与えられたmaximal orderを持つ超特異楕円曲線を見つけるconstructive Deuring対応問題を解くツールで暗号分野で幅広い応用先を持つ. しかし，KLPTアルゴリズムの実装に関する文献は少なく，10ビット程度までの標数における実装報告しかない. 本発表ではKLPTアルゴリズムの改良を行うと共に45ビット程度までの標数におけるsageによる実装結果を報告する.
超特別曲線は超特異曲線の中でも有限個しかない曲線クラスであり，その存在性の決定と数え上げは基本的かつ重要な問題である．これまで講演者は種数4，5の場合に上記問題を解くための様々なアルゴリズムを提案し，小さい標数p（最大でもp=23）に対し上記問題を解決してきた．一方で近年，千田氏は種数4の曲線の中でも超特別となる可能性の高いHowe曲線に着目し，上記問題を解くアルリズムを提案しMagmaに実装した（JANT2019春の発表）．しかしその計算量は最悪O~(p^9)であり，実際，p<100程度までしか計算結果は得られていなかった． そこで今回，超特別Howe曲線を決定する新たなアルゴリズムとして，千田氏によるものを改良した方式と，Richelot同種写像の計算に基づく方式の二つを提案する．前者はO~(p^6)，後者はO~(p^4)の計算量であり，後者をMagma上で実行することで全てのp<20000に対し超特別Howe曲線の存在性を示すことができたので，これを紹介する． さらに，提案アルゴリズムによる計算実験に基づいた，任意標数p>7に対する超特別Howe曲線の存在性予想を提示する．
有限体上の非線形多変数多項式の集合を公開鍵とする公開鍵暗号を多変数多項式暗号とよぶが、その多くは2次多項式で構成される。ごく最近, Diene-Thabet-Yusuf は3次多項式で多変数署名方式を構成した。この方式では、3次化する方法を工夫することで、それほど効率性を落とさずにすんでいるが、一方でその工夫は安全性を損なっている。本講演では、この署名方式の構成とその脆弱性について話をする。
東京都立産業技術高等専門学校 ものづくり工学科 電子情報工学コース
田中覚
stanaka@metro-cit.ac.jp