| 講演名 | 2002/9/13 離散対数問題にもとづく高速擬似乱数生成 小柴 健史, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | メルセンヌ素数位数となるGF(2^n)^*上の離散対数問題にもとづく高速擬似乱数生成法を提案する。新方式は次のような特徴を持つ。(1)暗号学的擬似乱数であることが証明可能、(2)実用的な設定で高速実装を持つ、(3)実用的な設定のもとで出力される擬似乱数列は統計的性質を持つ。まず、離散対数の羅の上位n-ω(log n)ビットが連続的にハードコアビットであることを示す。これにより、短い冪の離散対数をもとに擬似乱数生成法が構成できることになる。実装においては冪計算が高々ω(log n)回の乗算で計算できる。次に、メルセンヌ素数位数となるGF(2^n)^*の離散対数問題についての新しい表現形式を提案する。一般に幕計算には算術演算が不可避であるが、新しい表現の元での冪計算はビット・シフト演算のみで実装可能である。また、速度評価および統計評価についての実験結果も示す。具体的なパラメータのもと試作実装での速度計測を行い55Mbps(Pentium III,800MHz)の値を得た。 |
| 抄録(英) | We propose an efficient pseudorandom generator based on the discrete logarithm problem over GF(2^n)^* of the Mersenne prime order. Our generator is advantageous in the following sense: (1) our generator can be proved to be a cryptographically strong pseudorandom generator; (2) our generator with concrete and practical parameters has a high-speed implementation; (3) our generator with concrete and practical parameters has good statistical properties in the sense that our generator can pass statistical tests such as the NIST statistical test suite for pseudorandom generators. First, we prove that the most significant n -ω(log n) bits of discrete exponent are simultaneously hard-core bits. This enables us to utilize discrete logarithm with short exponent in our generator. This implies that exponentiation can be implemented by using ω(log n) multiplications. Next, we introduce a new representation of the discrete logarithm problem over GF(2^n)^* of the Mersenne prime order. In general, modular multiplications are inevitable in order to compute exponentiations. Our introduction of a new representation of the discrete logarithm problem enables us to compute exponentiations by using bit operations, which is incomparably more efficient than modular computations. We also show some experimental results of the speed evaluations and the statistical evaluations. A prototypical implementation of our generator with the concrete parameters showed that our generator runs at the rate of 55 megabits per second on an 800MHz Pentium III. |
| キーワード(和) | 暗号学的擬似乱数 / 離散対数問題 / メルセンヌツイスター |
| キーワード(英) | cryptographically strong pseudorandom generator / discrete logarithm problem / Mersenne Twister |
| 資料番号 | ISEC2002-57 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2002/9/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 離散対数問題にもとづく高速擬似乱数生成 |
| サブタイトル（和） | |
| タイトル（英） | A Fast Cryptographically Strong Pseudorandom Generator Based on the Discrete Logarithm Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 暗号学的擬似乱数 / cryptographically strong pseudorandom generator |
| キーワード(2)（和/英） | 離散対数問題 / discrete logarithm problem |
| キーワード(3)（和/英） | メルセンヌツイスター / Mersenne Twister |
| 第 1 著者 氏名（和/英） | 小柴 健史 / Takeshi KOSHIBA |
| 第 1 著者 所属（和/英） | (株)富士通研究所 セキュアコンピューテイング研究部 Secure computing Lab.(L22), Fujitsu Laboratories Ltd. |
| 発表年月日 | 2002/9/13 |
| 資料番号 | ISEC2002-57 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 323 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |