2012年連合発表会
「数論アルゴリズムとその応用」 (JANT) 講演要旨

「代数曲面上の求セクション問題に対する Wu のアルゴリズムの適用」
○小椋 直樹(首都大学東京 D3), 三原 千穂((株)東芝), 秋山 浩一郎((株)東芝), 三宅 秀享((株)東芝), 内山 成憲(首都大学東京)

量子計算機に耐性があると考えられる公開鍵暗号 (耐量子公開鍵暗号) として, 代数曲面上の求セクション問題 (Section Finding Problem: SFP) の計算量的困難性に基づく代数曲面暗号(Algebraic Surface Cryptosystem: ASC) が知られている. ASC は他の耐量子公開鍵暗号に比べて, 鍵サイズが小さいという利点がある. 同問題は, 与えられた代数曲面に対し曲面上の特定のパラメータ付けされた代数曲線を求める問題であり, これを解くアルゴリズムについては, これまで多変数連立方程式を解く問題に帰 着させ, グレブナ基底計算を用いて解を求める方法しか知られていない. 本講演では, この従来手法より高速な改良アルゴリズムを提案するとともに, 本手法を実装した結果を示し, 求セクション問題の困難性について議論する.

「平方Weilペアリングと簡約Tateペアリングの計算量評価と数値実験」
○平野　正樹(首都大学東京 M2),中村　憲(首都大学東京)

埋め込み次数5～20のペアリングに適した楕円曲線において, Weilペアリングの平方値（平方Weilペアリング）とべき乗を含んだTateペアリング（簡約Tateペアリング）の 計算量評価と数値実験を行った結果について発表します. なお, 簡約Tateペアリングのべき乗部分については, 単純な反復二乗法だけでなく因数分解とｑ進展開により効率化した方法も実装しました. その結果, 埋め込み次数が大きいときは簡約Tateペアリングでべき乗の効率化を考えなければ 平方Weilペアリングの方が高速であることがわかりました.

「ナップサック暗号の数体を利用した鍵生成法の改良と考察」
○宮本 泰徳(首都大学東京 M2), 中村 憲(首都大学東京)

OTU2000を元にしたナップサック暗号の鍵生成アルゴリズムと, その改良について発表します. 今回, 鍵生成に必要なパラメタが充すべき条件を任意の数体上で効率的に 確認出来る方法が見つかったことにより, 任意の数体上で実際に鍵を生成 できるようになりました. また, パラメータが満たさなければならない条件を 一部緩和できることも分かりました. それらの改良を施したアルゴリズムをMAGMAを用いて実装・実験した結果に ついても発表いたします.

「既定値埋め込み型RSAの既定値長と鍵生成時間の関係について」
○北原 基貴(九州大学 B4), 西出 隆志(九州大学), 櫻井 幸一(九州大学)

RSA暗号において公開鍵の法の一部を事前に決めて鍵生成を行うLenstraアルゴリズムと呼ばれるものがある. 本発表ではこの事前に決める値(既定値)の長さを変えた場合に合致する素数の生成時間がどのように変化したかを報告する. また, N=pqrに拡張した場合についても素数生成時間がどのように変化したか報告する. Lenstraは法の長さの半分まで既定値を埋め込むことができると仮定していた. しかし, 実験によって既定値の長さが法の長さの半分に近づくに従い急激に鍵生成時間が増大することが確認できた. そしてこの実験結果から効率的に鍵生成できる既定値の上限について検討する.

「2次形式の同型写像を用いた多変数多項式署名の構成」
○安田 貴徳（九州先端科学技術研究所), 高木 剛(九州大学), 櫻井 幸一(九州大学）

多変数多項式公開鍵暗号は多変数方程式の求解の困難性に基づいており, その安全性のため, 鍵長が大きくなることが課題である. 本講演では2次形式を利用した新しい多変数署名方式を提案する. これは多変数多項式署名方式の一つ, Rainbowに比べ, 秘密鍵長を小さくできる. この方式の署名生成のアルゴリズムなどについて述べる.

「指数計算法の線形代数ステップにおけるLanczos法とWiedemann法の比較実験」
○林 卓也(九州大学 D2), 篠原 直行(情報通信研究機構), 高木 剛(九州大学)

離散対数問題の高速な解法である指数計算法には，大きな自然数を法とする 巨大かつ疎な連立一次合同式を解くステップ（線形代数ステップ）がある． 計算実験ではこの解法として，行列サイズ$n$に対して計算量が$O(n^2)$である Lanczos法やWiedemann法が利用されている． 一方で，この二つのアルゴリズムの計算実験による比較は今のところ報告されて いない． 本発表では指数計算法の一つである関数体篩法で実際に得られたデータを基に， Lanczos法とWiedemann法の計算実験による比較について報告する．

「An exhaustive search algorithm for finding all small solutions of a multivariate modular linear equation」
○ Hui Zhang(九州大学 D2), 高木 剛(九州大学)

We present an exhaustive search algorithm for finding all small solutions of a multivariate modular linear equation over the integers on the basis of lattice reduction techniques. Our algorithm can find all the solutions in a given bound; therefore, it can cope with problems with large bounds. Although the algorithm is an exponential time algorithm in the number of unknowns n, experimental results show that it is quite efficient when n < 9. We demonstrate the superiority of our algorithm by applying it to the attack on an RSA-CRT.

「形式化数学システム Mizar による数論アルゴリズムの検証」
○水島 大地(信州大学 M1), 青木 祥希(信州大学 M1), 岡崎 裕之(信州大学), 師玉 康成(信州大学）

NZMATH は， Python　により記述された数論アルゴリズムのライブラリである． 本研究では， NZMATH の形式検証を，形式化数学のシステムである Mizar を用いて行っている． 今回は， NZMATH に収録されている数論アルゴリズムのうち， ユークリッドの互除法・拡張ユークリッドの互除法・中国剰余定理の検証について報告する． また，これらの検証に際して， Mizar での形式記述は人手により行われており，検証に多大な時間を要している． そこで，形式記述の自動化について，プログラムを作成し，実験を行った．

「奇標数有限体の３次拡大体上, 種数２曲線の被覆曲線の構成」
○橋本　拓(中央大学 M2), 飯島　努(中央大学), 趙　晋輝(中央大学), 志村 真帆呂(東海大学)

代数曲線暗号は, 代数曲線上の離散対数問題(DLP)を安全性の根拠としており, 現在の主流であるRSA暗号よりも短い鍵長で同程度の安全性を得られている. ま たGHS攻撃とはGaudry, Hess, Smartらの提案を拡張した代数曲線暗号に対する攻 撃法で, 有限体kのd次拡大体上定義された代数曲線の離散対数問題(DLP)をk上定 義されたより大きな種数を持つ被覆曲線のDLPに移して解く攻撃である. 本発表 では, kの3次拡大体上で定義された種数2の超楕円曲線の全ての被覆曲線の定義 方程式をk上の一つの簡潔な多項式で構成する方法を提案する. またその具体例 を挙げる.

「On the number of Fp-valued points of elliptic curves」
○奥村　伸也(九州大学 M2)

有限体上の楕円曲線EのFq-有理点(q = 素数の冪) の個数|E(Fq)|の素数性は楕円曲線暗号において 重要である. Koblitz は整数係数の有理数体上の 楕円曲線Eについて, pがx以下の素数を走る時, |E(Fp)|が素数となるpの数を予想した. その後, Zywina はこの予想を精密化し, |E(Fp)|/tが素数となるpの数 (tは正の整数)を予想した. そこで本講演では, 素数pを p≡a (mod b) (gcd(a, b)=1)を満たす物に制限した時, |E(Fp)|/tが素数となる確率がどのように変化するかの 予想とその実験結果をいくつか紹介する.

「Magma による p 進体の Galois 群の高速計算」
○横山 俊一(九州大学D2), 吉田 学(九州大学 D3)

p 進体上の多項式の分解体の Galois 群を計算機上で計算する 最も有効な方法として Jones の手法が知られている. ここで用いられている拡大体のデータベース生成法とそれに対する 同型判定アルゴリズムを改良することで, 特別な拡大に対しては 高次の場合にも耐えうるプログラムを作成出来たので, これに ついて報告する.

問い合わせ先

青木美穂 (島根大学総合理工学部)
aoki(at)riko.shimane-u.ac.jp