各講演20分（質疑応答時間を含む）
○印は登壇者
現在広く使用されている公開鍵暗号であるRSA暗号では秘密鍵として大きな素数が用いられ、 そのような素数の生成にMiller-RabinテストやLucasテストなどの確率的素数判定法が利用されている。 一方で、計算コスト及び誤判定率の双方を考慮した観点で、確率的素数判定法を改良する研究が進められている。 例えば、Miller-Rabinテストで扱う底とよばれるパラメータをある区間までの全ての素数の集合から選び、 そのような任意の底に対してMiller-Rabinテストを実行しても合成数と判定されない最小の合成数を探索する研究がある。 本研究では、確率的素数判定法の一つである強Lucasテストを用いて、先行研究と同様の探索を行った。 強Lucasテストの計算コストを削減するためにLucas chainを導入し、そのために必要な定理を証明し、 計算コストをMiller-Rabinテストと同程度に抑えることに成功した。 さらに実際に数値実験を行い強Lucasテストの効率性を検証した。 本発表ではこれらの成果について説明する。
グレブナー基底計算を効率的に計算する代表的なアルゴリズムとして F4 や M4GB algorithm などが挙げられる. M4GB algorithm は, 計算の途中で使用する reductor を格納し, 格納した多項式を以降の簡約操作においても reductor として用いることにより計算コストの削減を行う. また, 多変数公開鍵暗号で利用される連立代数方程式を解くコンテストである Fukuoka MQ Challenge において6種の問題が設定されており, M4GB algorithm は現在までに, その内の2種の問題において最も変数の多い連立代数方程式を解くことに使用されている. 本講演では M4GB algorithm における多項式格納方法と多項式の簡約操作などに関する改良を提案し， それらによる数値実験の結果と考察について述べる.
P, Qを有理数として，3項間の線形漸化式 w_{n+2} = P w_{n+1} - Q w_n を満たす数列のうち， ある条件を満たすもの全体に「乗法」を定義することができ，アーベル群になる． 表題のLaxton群はこのアーベル群の，ある商群として得られるものである． 本講演では，Laxton群の元で平方になっているものに対して平方根を求めるという問題を扱う． 同時に，Laxton群の，素数ごとに定まる二つの部分群の剰余群においても同じ問題を考える． それぞれ，2元2次形式での整数の表現，有限体の乗法群での平方根を求める問題に帰着される．
多変数二次多項式系の求解問題（MQ問題）は、数式処理においてだけでなくさまざまな暗号方式の安全性を考える上で重要な問題である。XLアルゴリズムは、グレブナー基底を求めるアルゴリズムと並んで、MQ問題の主要な求解アルゴリズムの一つであり、Macaulay行列に対するガウス消去を行うことで解を求めている。本研究では、多項式環上のMacaulay行列を利用したXLアルゴリズムの改良手法を提案し、その計算量を理論的に評価した。
保型形式の周期は, 保型L関数の特殊値と密接に結びついていることが知られていて, 古くから盛んに研究されている.しかしながら, その具体的な値を計算するという試みはあまり知られていない. 今回, 数式処理ソフトMagmaを用いて四元数体上の代数的保型形式のトーラス周期を計算した. 本講演では, トーラス周期と保型L関数の特殊値の関係について説明した後, どのような手順で計算したのかを紹介する.
講演「トーラス周期の値の分布について I（鈴木氏、トーラス周期とそのアルゴリズムの説明が主）」の後に続いて、この講演を行いたいと考えています. 我々は前講演のアルゴリズムによって定値四元数環上の代数的保型形式のトーラス周期の値の大量計算を行い, その計算結果を用いてトーラス周期の値の分布に関する研究を行いました. この講演では, その分布のグラフを基にトーラス周期の諸性質について議論します. そして, 新たに発見されたトーラス周期の持つ性質の予想について解説を行います.
A hash function is one of most important concepts as a primitive in cryptography. Especially, many attempts to close to idealistic hash functions based on sophisticated mathematical backgrounds are encouraging in these days. In this talk we provide hash functions based on triplet and sextet graphs which are cubic high-girth graphs introduced by Biggs (1988) and Biggs, Hoare (1983), respectively. Then we discuss some security properties of the proposed hash functions based on algebraic graph theory and the study of group word problems on projective linear groups over finite fields.
耐量子計算機署名としてChuengsatiansupらによってModFalcon が提案されている. ModFalconは, 現在NISTのコンペティションの最終ラウンドに残っているFalconをベースとしており, module格子を組み込むことで, 署名サイズを小さくすることができる. しかし, ModFalconはスクリプト実装での評価のみで,実環境での評価がなされていない. また, スクリプト実装での評価では, 多項式乗算をKaratsuba法やFFTによる基本的な実装により行っており, 高速化を検討していない. そこで本稿では, 高速な多項式乗算を実現する, Toom-Cook法やRadix4 FFTを組み込んだModFalconの実環境での評価を行った.
有限体上の多変数２次多項式の集合を公開鍵とする 多変数多項式暗号は、耐量子暗号の候補の一つとして 期待されている。とくに、署名方式のUOVやRainbowは 安全性、署名認証のはやさなどに利点が大きいことが 知られている。一方で、これらの方式では鍵のサイズが 比較的大きくなりがちで、鍵サイズを小さくする取り組み も少なくない。 昨年9月に開催されたIWSEC2021では、Yinらが Simple matrix signature scheme という多項式行列の乗算を基にした署名方式を 提案した。この方式では、比較的小さいサイズの鍵で Rainbow と同等の安全性を確保できると 提案者によって見積もられている。 しかしながら、その構造をよく見ると、UOVの特殊版 でしかなく、安全性も見積もられているより大幅に小さい。 本講演では、この方式の具体的な構造と、実際の安全性に ついて説明する。
耐量子計算機暗号の1つである同種写像暗号において、同種写像計算の高速化が 重要なテーマの1つである。2020年にBernsteinらによって提案された終結式を用 いた同種写像公式により高次の同種写像計算が高速化できることが知られてい る。Bernsteinらの公式はMontgomery曲線上で記述されていた。守谷らはこれを Edwards曲線に拡張し、それにより高速化可能であるとしたが、具体的な実装は 与えなかった。特に射影座標において終結式を計算する際に先頭項の係数から生 じる差を調整する必要があり、計算の高速さを損なわずどのように調整するかは 未解決であった。本講演では、その係数を調整する方法を与え、Edwards曲線の 射影座標上で終結式を用いた同種写像計算公式を明示的に構成する方法について 述べる。さらに公式を実装し、体の演算回数による性能評価をした結果について も述べる。
MinRank問題は、与えられた複数の行列が張る空間からランクの低い行列を見つける問題である。この問題はNP-hardであり、いくつかの暗号の安全性根拠となっていることから、暗号学的にも重要な問題となっている。特に、アメリカのNISTが行っている耐量子計算機暗号の標準化計画の最終候補であるRainbow署名方式の安全性根拠の一つである。MinRank問題の解法として、二次方程式系に帰着して解くKipnis-Shamir approachが知られているが、最近Verbelらによってこの方程式系のsyzygyが詳しく解析された。彼らが扱ったMinRank問題はランダムケースであり、Rainbowに現れるような特殊ケースは考えられていない。そこで、この講演ではRainbowに付随するMinRank問題に対してVerbelらの結果がどう影響するかを考察する。
多変数多項式公開暗号は耐量子計算機暗号であり，次世代暗号の候補の1つである． 連立二次多変数代数方程式の求解(MQ問題)は多変数公開鍵暗号の安全性根拠となっており，その計算困難性を評価することは重要な研究課題である． MQ問題を解く有力な方法の一つとしてGroebner基底を求める方法があり，その際にはF4，F5などのアルゴリズムが用いられる． Hybrid approachは有限体上の連立多変数代数方程式の解法の一つで，総当り法(exhaustive search)とGroebner基底を計算する方法を合わせた方法であり，MQ問題の変数の数nが多項式の数mより大きい場合にあらかじめ代入を行い，n<mとしてGroebner基底を求める． この発表では，Hybrid approachにおける代入計算の前に，あらかじめGroebner基底計算を途中まで進めてから代入計算し，Groebner基底を求める手法について検討したので報告する．
東京都立大学 大学院理学研究科 数理科学専攻
横山 俊一
s-yokoyama@tmu.ac.jp