各種日程、参加費については上記ウェブページをご覧ください。
各講演20分（質疑応答時間を含む）
○印は登壇者
ハッシュ関数とは任意長の入力に対して固定長の出力を返す関数であり、同じ出力を返す異なる入力の組を「衝突」と呼ぶ。暗号にハッシュ関数を応用する上では、このような衝突を発見するのが計算量的に困難であること(衝突困難性)が要求される。同種写像ベースのハッシュ関数としては2007年にCharles-Lauter-Gorenが考案した超特異楕円曲線を用いた構成が代表的である。一方で2020年にCastryck-Decru-Smithはその2次元版として、超特別アーベル曲面を用いるハッシュ関数を考案した。彼らの構成において初期曲面は特殊なものを用いており、本発表ではその性質を利用した衝突発見アルゴリズムを紹介する。このアルゴリズムの漸近計算量は基礎体の標数pに対して√p程度であり、既存の攻撃手法より効率的である。またpが特殊な形であれば、我々の手法はpに関して多項式時間となる。我々は計算機代数システムMagma上でこれを実装し、提案者が192bit安全と主張したパラメータ設定下において11時間弱で衝突を発見することに成功した。また、我々の手法を適用しても衝突困難性が保たれるための改善策も提案する。
Deuring対応により超特異楕円曲線間の同種写像は四元数代数の極大整環のイデアルと対応する。与えられた極大整環とその左イデアルに対して、そのイデアルと対応する同種写像を計算するアルゴリズムはideal-to-isogenyアルゴリズムと呼ばれる。本研究では、2次元同種写像と楕円曲線の自己準同型環への虚二次体の埋め込みを用いたideal-to-isogenyアルゴリズムを提案する。我々のアルゴリズムは既存の1次元同種写像のみを用いるアルゴリズムに比べて、楕円曲線の標数に課される条件が弱い。適切に標数を選択することとにより、我々のアルゴリズムは既存のものよりも高速となる。さらに応用として、同種写像署名方式SQIsignが我々のアルゴリズムを用いて高速化できることを示す。また、最近提案された同様のアルゴリズムを紹介し、それらとの比較を述べる.
Groebner基底の計算量を精密に評価することは一般には難しい問題であり、暗号の安全性解析などにおいても重要な課題となっている。Groebner基底の計算量は入力となる生成系のデータの大きさの関数として表され、その計算量を測る指標として求解次数(solving degree)がよく利用される。しかし、求解次数には定義が４種類も存在し、混同されるだけでなく数学的に誤った議論がなされていることも少なくない。本講演ではまず、これらの４種類の定義を正確かつ厳密な形で与えた上で、大小関係や一致する条件などの基本的性質を示す。次に、今年春のJANTで紹介した講演者の求解次数の評価に関する結果に基づいた、Groebner基底の計算量の漸近評価式を明示的に与える。さらに、暗号の安全性解析（特にMQ問題の求解計算量評価）において屡々用いられる半正則性仮定を取り上げ、同仮定下での計算量の漸近評価式を正しい形で述べる。また、「入力多項式系が半正則でないときに半正則である場合と同様の計算挙動になる」という仮定について、従来の半正則性の定義を拡張することで理論的な定式化が得られたので、これについても紹介するとともに、Froeberg予想のある種の一般化を提示し、暗号の安全性解析への応用可能性を示す。
サイボウズ・ラボ株式会社
光成滋生
herumi@nifty.com