日本応用数理学会2018年研究部会連合発表会
「数論アルゴリズムとその応用」(JANT)セッション

日時

会場

参加費

プログラム

数論アルゴリズムとその応用(1) 13:30-14:50

1. 三乗和と五乗和に関するディオファントス方程式の自然数解の探索
   ○五百旗頭 学(大阪大学理学研究科数学専攻博士前期課程2年)

   三乗和と五乗和に関する、あるディオファントス方程式の非自明な自然数解を、有理数体上の楕円曲線の理論を用いて探索した。同方程式の非自明な整数解を探索する方法が先行研究として知られていたが，今回はそれを詳しく分析して、非自明な自然数解を探索する方法に改良した。また、この方法によって非自明な自然数解を無数に計算できることを証明した。

2. 楕円曲線Hidden Number Problem のEdwards 曲線への拡張
   ○小野澤 綜大 (東京大学), 高安 敦 (東京大学/産業技術総合研究所), 國廣 昇 (東京大学)

   Hidden Number Problem (HNP)はDiffie-Hellman鍵共有における共有鍵の上位ビットが漏洩した時の安全性を評価する目的で，Boneh とVenkatesan (CRYPTO'96) が導入した問題である．楕円曲線Diffie-Hellman (ECDH)鍵共有におけるHNP は楕円曲線の演算が複雑なため長く行われてこなかったが，Shani (PKC2017) は式変形を工夫することで解析を行った．Shani の研究では ECDH鍵共有で一般的に用いられる Weierstrass 標準形について解析を行っている． 本研究では近年，暗号方式へ応用されつつあり注目されているEdwards 標準形における HNP を多項式時間で解くアルゴリズムを提案する．まず，我々は Edwards 曲線の加算公式と標準形の定義式を元に共有鍵の未知部分が解となる法付き方程式を導出する．そして，その方程式を Coppersmith の手法を用いることで解く．我々の手法では上位ビットの約83%が得られた時に共有鍵を復元できる．

3. 低次元におけるLLL簡約基底が最短ベクトルを含まない必要十分条件
   ○松田 康太郎 (東京大学), 高安 敦 (東京大学), 高木 剛 (東京大学)

   最短ベクトル問題(SVP)の近似解を求める多項式時間アルゴリズム としてLLLアルゴリズムがある. 本研究では, 3,4次元の場合, LLLアルゴリズムの出力から 最短ベクトルを求める厳密解法を考察する. まず, Lovasz条件のパラメータδが1に近い場合, 3,4次元の LLL簡約基底が非零最短ベクトルを含まない必要十分条件を求める. これによって, LLL簡約基底の{-1,0,1}のみを係数とする線型結合の 一部を調べることで, 非零最短ベクトルが得られることを示す.

4. HFERP – A New Multivariate Encryption Scheme
   ○池松 泰彦 (九州大学), Perlner Ray (NIST), Smith-Tone Daniel (NIST, University of Louisville), 高木 剛 (九州大学), Vates Jeremy (University of Louisville)

   多変数多項式暗号は量子計算機に耐性を持つ公開鍵暗号の候補の一つである。 2016年安田氏らによりSRPという多変数多項式暗号が提案された。これはSquare,Rainbowという二つの暗号、署名方式を、Squareで用いられる変数がRainbowのVinegar変数になるように組み合わせ、さらにランダムな二次多項式を付加(Plus)して、SquareとRainbowの構造を隠すことで構成される。しかし、2017年Perlner氏らはMinRank攻撃の計算量がグレブナー基底のものより下回ることを証明し、MinRank攻撃が有効であることを示した。これは、Squareの公開鍵から得られる行列たちの最低ランクが1であるということから従う。 この講演では、Squareの部分を多変数多項式暗号HFEに代替したHFERPという新しい暗号方式を提案する。さらに、HFEの公開鍵から得られる行列たちの最低ランクがSquareの場合よりも高くなることを述べ、結果的にHFERPへのMinRank攻撃が有効に働かなくなることを説明する。最後にHFERPの80bit securityに対するパラメータを提案する。

数論アルゴリズムとその応用(2) 15:00-16:20

1. GVWアルゴリズムの改良とその実験的評価
   ○池松 泰彦 (九州大学マス・フォア・インダストリ研究所)

   グレブナー基底導出アルゴリズムの1つとして，2010 年に S. Gao, F. Volny IV, M. Wang らによって提案されたGVWアルゴリズムがある．GVWアルゴリズムでは多くの “reduction” を実行するが，従来の高速化手法を拡張することでreduction 数を削減できる．本講演では，高速化手法の拡張を適用したアルゴリズムを数式処理ソフトMagmaで実装し，オリジナルのGVWアルゴリズムと比較評価することで見られる改良手法の効果を説明する．

2. BLS 曲線における Optimal Ate Pairing の実装と評価
   馬渕 圭史 (九州大学), ○横山 俊一 (九州大学), 齋藤 恆和 (NTTセキュアプラットフォーム研究所)

   次世代の公開鍵暗号方式として、任意の ID を公開鍵として利用できる ID ベース暗号があり、実際のサービスへの利用が進んでいる。この ID ベース暗号の多くは楕円曲線上のペアリングを用いて実装されており、安全性はそのペアリングについての離散対数問題の困難性が仮定となる。 CRYPTO2016 において Kim 等は任意のペアリングについての離散対数問題に対する解析手法の改良を提案し、ペアリングの安全性レベルが下がった。この解析手法に耐えうるものとして、SCIS2017 において清村等は 256 ビット安全なペアリングのパラメタとして BLS48 のパラメタを提案した。 本講演では、ID ベース署名の OSS である libsnark を元に BLS48 のパラメタを用いて Optimal Ate Pairing (OAP) を実装し、さらに libsnark 内のペアリングパラメタ BN256 との OAP と比較評価する。

3. 平面4次曲線の線形行列式表示を計算するアルゴリズムについて
   石塚 裕大 (京都大学理学研究科), 伊藤 哲史 (京都大学理学研究科), ○大下 達也 (愛媛大学理工学研究科)

   平面曲線の定義方程式を，線形形式成分の正方行列の行列式で 表すことを「線形行列式表示」という．線形行列式表示の計算は， 19世紀のHesseの研究に遡る伝統的な問題であり，Jacobi多様体 のMordell-Weil群を計算する問題や，直線束の極小分解を計算 する問題と関係することが分かっている．最近では，この問題は， 数論的不変式論の観点からも注目されるようになってきた． この講演では，Klein 4次曲線などの具体的な平面4次曲線について， その線形行列式表示を計算するアルゴリズムの解説を行う． また，具体的な計算結果の紹介を行う．

4. 多重ゼータ値の行列のランク計算へSATのアルゴリズムを応用する研究
   ○町出 智也 (国立情報学研究所（JST ERATO 河原林巨大グラフプロジェクト）), 薗部 知大 (国立情報学研究所（JST ERATO 河原林巨大グラフプロジェクト）)

   多重ゼータ値は Riemann ゼータ関数の特殊値の一般化です。昨今、金子-野呂-鶴巻氏等は、ガウスの消去法を用いて、多重ゼータ値のある線形関係式の集合に対応する行列のランクの上限を計算しました。本講演では、SAT に使用されるアルゴリズムを応用した、ランク計算のアルゴリズムを紹介します。そして、速度などのある点においてはガウスの消去法と同等かそれ以上の性能になることの実験結果を報告します。

数論アルゴリズムとその応用(3) 16:30-16:50

1. 円分体の相対類数の行列式公式の値の大きさの特異性について
   ○谷口 哲也 (金沢工業大学 基礎教育部)

   円分体の相対類数の行列式公式としてDemjanenko 行列，Maillet行列など多数知られているが，これらの行列式の値は係数をランダムに生成して配置した行列式に比べ「極端に大きい」ことを，講演者は数値的に観察している．例えばp=101 円分体では，相対類数公式の行列式値は，平均から4.7標準偏差ほど大きな位置にあり，またHadamard行列がまだ見つかっていない716次行列に対応するDemjanenko行列式の値も極めて大きく，Hadamardの上限の約96.8%の大きさの桁数を実現している． この「行列式の値が大きい」という現象は，たとえば実験計画法などの実学的な応用につながると講演者は考えている（実験計画法では実験効率を上げるために，±1 成分の行列で行列式値が大きなものが利用される）． 本講演ではこれまでに行った数値実験結果，とくに行列式の値の分布，固有値の分布，±1成分のDemjanenko行列から得られる球面上の点の配置に関する数値実験結果および，「ランダムに係数を生成した行列」「Demjanenko行列」「Hadamard行列」を，距離行列と対応付けて比較した結果について報告する．時間が許せば他の行列での相対類数公式でも同様の現象が起こっていることも報告したい．

問い合わせ先