| Presentation | 2002/9/13 A Fast Cryptographically Strong Pseudorandom Generator Based on the Discrete Logarithm Problem Takeshi KOSHIBA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | cryptographically strong pseudorandom generator / discrete logarithm problem / Mersenne Twister |
| Paper # | ISEC2002-57 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2002/9/13(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Fast Cryptographically Strong Pseudorandom Generator Based on the Discrete Logarithm Problem |
| Sub Title (in English) | |
| Keyword(1) | cryptographically strong pseudorandom generator |
| Keyword(2) | discrete logarithm problem |
| Keyword(3) | Mersenne Twister |
| 1st Author's Name | Takeshi KOSHIBA |
| 1st Author's Affiliation | Secure computing Lab.(L22), Fujitsu Laboratories Ltd.() |
| Date | 2002/9/13 |
| Paper # | ISEC2002-57 |
| Volume (vol) | vol.102 |
| Number (no) | 323 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |