離散対数問題にもとづく高速擬似乱数生成

概要

論文の詳細を見る
メルセンヌ素数位数となるGF(2^n)^*上の離散対数問題にもとづく高速擬似乱数生成法を提案する。新方式は次のような特徴を持つ。(1)暗号学的擬似乱数であることが証明可能、(2)実用的な設定で高速実装を持つ、(3)実用的な設定のもとで出力される擬似乱数列は統計的性質を持つ。まず、離散対数の羅の上位n-ω(log n)ビットが連続的にハードコアビットであることを示す。これにより、短い冪の離散対数をもとに擬似乱数生成法が構成できることになる。実装においては冪計算が高々ω(log n)回の乗算で計算できる。次に、メルセンヌ素数位数となるGF(2^n)^*の離散対数問題についての新しい表現形式を提案する。一般に幕計算には算術演算が不可避であるが、新しい表現の元での冪計算はビット・シフト演算のみで実装可能である。また、速度評価および統計評価についての実験結果も示す。具体的なパラメータのもと試作実装での速度計測を行い55Mbps(Pentium III,800MHz)の値を得た。
社団法人電子情報通信学会の論文
2002-09-13