日本応用数理学会2013年度年会
「数論アルゴリズムとその応用」 (JANT) 講演要旨

Elliptic netによるfixed argument pairingの計算について
劉陽（筑波大）、○金山 直樹（筑波大）、齋藤 和孝（IIJ）、照屋 唯紀（産総研）、内山 成憲（首都大）、岡本 栄司（筑波大）

ペアリング暗号などで用いるペアリングを計算するアルゴリズムは Millerによるものが非常に広く用いられているが、代替的な手段として elliptic netと呼ばれる関数を用いたものが2007年にStangeによって 提案された。だが、これは計算コストがMillerのそれに比べて少し ではあるが大きいため、現在の主流ではない。しかし、状況によっては Millerのそれより効率が良くなる場合がある。本発表では、片方の 入力点が固定された複数のペアリングe(P,Q1), e(P,Q2), …を計算する 場合に、G2×G1型と言われるペアリングの場合はelliptic netを用いた 方式の方がMillerを用いた場合より大幅に高速に計算できる事を示す。

Twisted Edwards curveを用いたスカラー倍算について
○峯尾 康則（首都大）、内山 成憲（首都大）

2007年, Edwardsは楕円曲線の新しい標準形を提案した. この曲線は Weierstrass型の楕円曲線と比べてスカラー倍算を高速に実現することができ, これまでに高速化のための様々なアルゴリズムが示されてきた. 同年, Bernsteinらは{2,3}-基底を用いたEdwards curve のスカラー倍算について考察を与えた. これは2倍算と３倍算を組み合わせてスカラー倍を行う方式である. 今回, twisted Edwards curveの3倍算のための公式を明示的に示し, 彼らが行なっていない, 拡張座標系上で{2,3}-基底を用いたスカラー倍算について考察する.

Improvement of Faug`ere et al.’s method to solve ECDLP
○黃 筠茹（九大）、Petit Christophe (UCL)、篠原 直行（情報通信研究機構）、高木 剛（九大）

Solving the elliptic curve discrete logarithm problem (ECDLP) by using Gro ̈bner basis has recently appeared as a new threat to the security of elliptic curve cryptography and pairing-based cryptosystems. At Eurocrypt 2012, Faug`ere, Perret, Petit and Renault proposed a new method using a multivariable polynomial system to solve ECDLP over finite fields of characteristic 2. At Asiacrypt 2012, Petit and Quisquater showed that this method may beat generic algorithms for extension degrees larger than about 2000. In this paper, we propose a variant of Faug`ere et al.’s attack that practically reduces the com- putation time and memory it requires. Our variant is based on the idea of symmetrization. This idea has provided practical improvements in several previous works for composite-degree extension fields, but its application to prime-degree extension fields has been more challenging. To exploit symmetries in an efficient way in that case, we specialize the definition of factor basis used in Faug`ere et al.’s attack to reduce the size of the polynomial systems. We provide theoretical and experimental evidence that our method is faster and requires less memory than Faug`ere et al.’s method when the extension degree is large enough.

2次形式の分類定理を用いた多変数署名方式の安全性について
○橋本 康史（琉球大）

多変数連立2次方程式の求解問題を基にした多変数暗号は、ポスト 量子暗号の候補のひとつとして、また、効率性の高い暗号として期 待されている。多変数暗号は大雑把に、松本今井暗号・HFE・Sflash などの「拡大体型」と、辻井の順序解法式暗号・UOV・Rainbow・TTS などの「順序解法型」の2つに分類されるが、ごく最近、この2つのどち らにも属しない新たな署名方式が安田-高木-櫻井（2013）によって提 案された。この方式は、2次形式の分類定理を用いており、ほぼ同サ イズのRainbowと比べて復号が9倍程度高速である。しかしながら、 多項式の構造は非常に特殊であり、安全性は高くない。本講演では、その脆弱性と、具体的な解析法を説明する。

Algebraic units and multidimensional continued fraction algorithm for algebraic number fields of higher degree (1)
○田村 純一（津田塾大）、安冨 真一（東邦大）

連分数の周期性に関するLagrangeの定理の高次元版が成り立つことが期待され るような新しい連分数のアルゴリズムを与える。それは連分数をゆっくり進め る加法的なアルゴリズムの高次元版である。６次以下の代数的数体のQー基底 に対してこのアルゴリズムを適用すると例外なく循環することが確かめられる （周期長が長くなる場合もあるが相対的なhightが有限で抑えられことが観察 されこの場合も周期性が出てくると考えられる）。他方Jacobi-Perron, Brun 等の古典的なアルゴリズムではしばしば相対的なhightの爆発が起こることが 観察される。このことにより古典的なアルゴリズムでは周期性は期待されない。

Algebraic units and multidimensional continued fraction algorithm for algebraic number fields of higher degree (2)
○安冨 真一（東邦大）、田村 純一（津田塾大）

我々のアルゴリズムの周期性から代数体の単数が得られる。これについて １）特に純３次体の場合はある整数基底の連分数展開の周期から得られる単数が基本単数になることが観察される。 2)さらに一般に虚な共役を持つ実３次体についても同様な観察がされる。 3)総実な３次体ついては単数群Gのランクは２である。我々のアルゴリズムで生成される単数群をHとしたとき♯[G/H]≦28であることが観察される。 1)-3)の下では３次体の単数群の生成元（基本単数）が我々のアルゴリズムにより求められることになる。 さらに高い次数の体（虚な体も含める）についても若干の結果を紹介したい。

An explicit construction of point sets with large minimum Dick weight
○鈴木 航介（東大）

WAFOMは松本眞氏らによって導入された、digital netの不均等さを表す尺度の一 つである。 s次元単位立方体上の十分滑らかな実数値関数に対しては、 低WAFOMな点集合による準モンテカルロ積分誤差が小さくなる。 WAFOMは、Hamming weightの一般化であるDick weightを用いて評価できる。 本講演では、Niederreiter-Xing列から作られる (t,m,s)-netを適切に選択してDickのinterlacingを行うことにより、 最少Dick weightの大きなdegital netの族が明示的に構成できることを示す。 これは低WAFOMな点集合の族でもある。

Mizarによる有限可換群の基本定理の形式化について
○中正 和久（信州大）、岡崎 裕之（信州大）、山崎 浩（信州大）、師玉 康成（信州大）

本発表では、有限可換群の基本定理の Mizar による形式化について報告する。 Mizarは、Mizar Society によって進められている、計算機を 使用して数学を定式化するプロジェクトの総称である。 Mizar は、厳密な数学的形式記述が可能であり、なおかつ 強力な推論機能を有している。

問い合わせ先

松尾 和人(神奈川大学)
k-matsuo(at)kanagawa-u.ac.jp