各種日程、参加費については上記ウェブページをご覧ください。
各講演20分（質疑応答時間を含む）
○印は登壇者
一方向性関数は現代暗号理論における基礎的な関数であり、公開鍵暗号をはじめとして多くの応用がある。 本講演では、1997年にAnshelとGoldfeldによって提案された有理数体上の楕円曲線に付随するL関数に基づく2つの一方向性関数について考察する。 彼らの論文では理論的な議論が主であったが、ここでは、彼らの提案関数に基づき、一方向性関数と期待される関数を再定義するとともに、アルゴリズムとして詳しく書き下し、それらの計算量等について述べる。
有限体上の二次多変数多項式からなる連立方程式を解く問題はMQ問題と呼ばれている。 この問題は量子計算機を用いても解くことが困難であると考えられているため、耐量子計算機暗号の候補である多変数公開鍵暗号の分野で重要である。 MQ問題を解く方法の一つとして、グレブナー基底を用いるものがある。グレブナー基底の計算において、多項式のペアの選択方法はアルゴリズムの計算効率に影響を与えるため、効果的なペア選択方法が研究されている。 これまでの研究では、ペア選択方法を一つに固定したときのグレブナー基底計算の効率性について焦点が当てられていた。 本研究ではグレブナー基底計算の振る舞いが前半と後半で異なることに着目し、前半と後半で異なるペア選択方法を組み合わせるアイデアについて考察する。 そのために、前半のペア選択方法を固定し、後半で様々なペア選択方法に切り替わるよう実装し、後半で発生した演算回数を測定する実験を行った。 また、後半でのみ有効な新しいペア選択方法を提案し、既存の方法と比較した。その結果と考察について報告する。
p進体Qpの拡大たちは与えられた次数nに対して有限個である。数論データベースLMFDBでは、p<200かつn<16の拡大たちのデータベースを格納している。 データは定義多項式をはじめ、判別式やGalois群などの不変量を格納している。Galois群の計算アルゴリズムについても多くの先行研究があり、20次程度まで計算されている。 正標数局所体についてはn次拡大が有限個とは限らないが、判別式を抑えると有限個となる。本研究では、与えられた次数nと判別式をもつ正標数局所体の拡大たちのデータベースを作成し、それぞれのGalois群を計算した。
近年，Matveevによる代数的数の対数からなる線形和が取る下限評価と，DujellaとPethöによる範囲縮小法を用いて，多くの指数型 Diophantine方程式が解かれている．その中でも，2022年にRihaneにより，２つのFibonacci数の和や差で表されるPell 数が決定されたことや，Gaberにより，２つのJacobsthal数の和で表現されるPell 数が決定されたことはこの方針の大きな成果となっている．本講演では，まずその手法に従って，２つのLucas数の和や差で表されるPell 数の完全なリストを与える．次に，本結果の応用として，隣接行列から得られる特性多項式による有向グラフの分類を紹介する． このような問題は，そのグラフに結びついた行列の特性方程式・固有値・固有ベクトルに関係したグラフの性質を研究するスペクトラルグラフ理論に属している． 2023年JSIAML(15)で講演者達が示した手法により，特性方程式がFibonacci 型の漸化式で表現される有向グラフが多数見つかった．Fibonacci多項式に代表されるような多項式族の相違は，Fibonacci型数列の関係を用いて簡明に調べることが可能であり，それゆえ特性方程式によるグラフの分類・決定が可能となったので，それらを紹介したい．
FESTAなどの同種写像暗号方式は，種数2の超楕円曲線における同種写像計算とスカラー倍算を用いている． 超楕円曲線上のスカラー倍算は，Mumford表現の加算と2倍算を組み合わせて実現される．これらを有限体上の演算のみを用いて構成する陽的加法公式が多く提案されている． 種数2の超楕円曲線y^2 = f(x)における陽的加法公式の先行研究は，fが5次かつモニックな場合に限ったものが大半だった． 一方で，同種写像暗号ではfが6次かつ非モニックな曲線を用いているが，BassoらはFESTAの実装においてCostello-Lauterの陽的公式のアフィン座標における一般化を提案している． 本発表では，LangeおよびCostello-Lauterらによるfが5次かつモニックな場合の陽的加法公式を，fが6次かつ非モニックな場合についてアフィン座標および射影座標において一般化した公式を提案する． また，これらの提案手法をBassoらの公式も含め比較し，計算機実験の結果を報告する．
2019年にAccardiらは，有限体上の行列演算を用いたDiffie-Hellman型の耐量子性を有する鍵共有方式SAA-5を提案した． SAA-5の安全性は，行列を変数とする多変数多項式系の解読問題に帰着できる． 秘密鍵として用いる行列SがFull-Rankではないことから，多変数多項式系がintrinsically indeterminateとなり，総当たり攻撃のみが可能であると主張している． また，有限体Fp上のd次正方行列のSAA-5に対する総当たり攻撃の計算量は，p^{d^2-Rank(S)}と評価されている． 本研究では，SAA-5に対して多項式時間で解読可能な弱鍵の存在を考察する．p-1の素因数分解の情報を利用して，行列SのRankが低下する場合の確率を評価する． 特に，q|(p-1)を満たす素数qに対して，mod qでのみFull-Rankではない場合の確率を与えた． その結果，最も高確率で生成される鍵がq=2の場合であり，それが最も弱い鍵であることを示した． また，SAA-5の推奨パラメータ(p=4294967291, d=5)に対し，Magmaを用いた実装を行い，52.8%の秘密鍵に対して平均62.9秒で共有鍵を求めることができた．
Grӧbner基底の計算量を精密に評価することは一般には困難であるが、零次元イデアルの場合はFGLM基底変換が適用できるので、特定の項順序（特に次数付き順序）に対する計算量評価が重要となる。 次数付き順序では、各次数（step degreeという）におけるS多項式簡約を行う方法が最も効率的な戦略であり、step degreeの上界を評価することで全体の計算量評価が可能となる。 しかし、入力が非斉次の場合はdegree fallと呼ばれる現象が起こるため、その上界の評価は一般には難しい。 Bardet、Faugѐreらは入力が半正則である場合に、正則性次数と呼ばれる不変量を利用した評価を試みてきたが、その主張には数学的厳密性に欠ける部分がある。 本講演では、入力が半正則な非斉次多項式列の場合に、その斉次化が生成するイデアルに付随するHilbert級数の明示公式を与える。 これにより、正則性次数をDとしたとき、D未満のstep degreeでは効率的にGrӧbner基底の元を計算することが可能となる。 また、D以上の各step degreeで計算すべきGrӧbner基底の個数を評価し、これによりstep degreeの上界が2D-2であることを示す。 この上界は入力が半正則な非斉次多項式列の場合のbest possibleな値である。さらに、Bardet、Faugѐreらの主張を定式化し、それらに対する厳密な証明を与える。
超特別曲線は数論や代数幾何学における重要な研究対象であり、最近では同種写像暗号のパラメータとしての利用も期待されている。 奇素数pを標数とする代数閉体上において、種数3超特別曲線の存在性はOort (1991)により示されており、それらの同型類の個数はBrock(1993)が具体的に与えている。 しかしながら、そのうち超楕円的なものが幾つ存在するかは未解決な問題であり、小さい標数pであってもこの問題を効率的に解くアルゴリズムは知られていない。 そこで本研究では、超特別3次元アーベル多様体間の(2,2,2)-同種写像グラフの計算アルゴリズムを、テータ関数を利用して具体的に構成する。 これにより全ての種数3超特別曲線の定義方程式を効率的にリストアップすることが可能となり、実際にMagma上で実行し100未満の標数で超楕円的な種数3超特別曲線の数え上げに成功した。 また、同様のアルゴリズムを用いて10000未満の標数においては、超楕円的な種数3超特別曲線が少なくとも1つ存在することも確認した。
耐量子計算機暗号の分野において, 楕円曲線間の同種写像を用いた鍵共有プロトコルとしてSIDHやB-SIDHがあるが, 2022年にCastryckとDecruらがこれらに対する多項式時間攻撃を与えた. また, この攻撃は暗号化方式FESTAをはじめとした他のプロトコル構成への応用も知られている. この攻撃ではアーベル曲面間の同種写像を計算する必要があるため, その効率的なアルゴリズム及び実装を与えることは重要な問題とされている. アーベル曲面間の同種写像を計算する方法として, テータ関数を用いる方法が知られている. 上記攻撃やその応用にはこの同種写像の列の合成を計算する必要がある. 我々は, 後の写像合成部の計算に役立つ補助点を初期曲面上で予め計算しておく工夫を施した効率的な計算方法を具体的に構成し, 計算機代数システムMagma上で実装した. また, それを用いてB-SIDHへの攻撃を構成し, 30ビット安全性をもつとされていたパラメータの場合に約7日で攻撃が完了することを確認した.
富山大学学術研究部理学系
木村巌
iwao@sci.u-toyama.ac.jp