Blum–Micali algorithm

The Blum–Micali algorithm is a cryptographically secure pseudorandom number generator. The algorithm gets its security from the difficulty of computing discrete logarithms.[1]

Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$ . Let $x_{0}$ be a seed, and let

$x_{i+1}=g^{x_{i}}\ {\bmod {\ p}}$ .

The $i$ th output of the algorithm is 1 if $x_{i}\leq {\frac {p-1}{2}}$ . Otherwise the output is 0. This is equivalent to using one bit of $x_{i}$ as your random number. It has been shown that $n-c-1$ bits of $x_{i}$ can be used if solving the discrete log problem is infeasible even for exponents with as few as $c$ bits.[2]

In order for this generator to be secure, the prime number $p$ needs to be large enough so that computing discrete logarithms modulo $p$ is infeasible.[1] To be more precise, any method that predicts the numbers generated will lead to an algorithm that solves the discrete logarithm problem for that prime.[3]

There is a paper discussing possible examples of the quantum permanent compromise attack to the Blum–Micali construction. This attacks illustrate how a previous attack to the Blum–Micali generator can be extended to the whole Blum–Micali construction, including the Blum Blum Shub and Kaliski generators.[4]

References

Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 416-417, Wiley; 2nd edition (October 18, 1996), ISBN 0471117099
Gennaro, Rosario (2004). "An Improved Pseudo-Random Generator Based on the Discrete Logarithm Problem". Journal of Cryptology. 18 (2): 91–110. doi:10.1007/s00145-004-0215-y. ISSN 0933-2790. S2CID 18063426.
Blum, Manuel; Micali, Silvio (1984). "How to Generate Cryptographically Strong Sequences of Pseudorandom Bits" (PDF). SIAM Journal on Computing. 13 (4): 850–864. doi:10.1137/0213053. S2CID 7008910. Archived from the original (PDF) on 2015-02-24.
Guedes, Elloá B.; Francisco Marcos de Assis; Bernardo Lula Jr (2010). "Examples of the Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction". arXiv:1012.1776 [cs.IT].

External links

https://web.archive.org/web/20080216164459/http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[schneier-1] Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 416-417, Wiley; 2nd edition (October 18, 1996), ISBN 0471117099

[Gennaro2004-2] Gennaro, Rosario (2004). "An Improved Pseudo-Random Generator Based on the Discrete Logarithm Problem". Journal of Cryptology. 18 (2): 91–110. doi:10.1007/s00145-004-0215-y. ISSN 0933-2790. S2CID 18063426.

[3] Blum, Manuel; Micali, Silvio (1984). "How to Generate Cryptographically Strong Sequences of Pseudorandom Bits" (PDF). SIAM Journal on Computing. 13 (4): 850–864. doi:10.1137/0213053. S2CID 7008910. Archived from the original (PDF) on 2015-02-24.

[4] Guedes, Elloá B.; Francisco Marcos de Assis; Bernardo Lula Jr (2010). "Examples of the Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction". arXiv:1012.1776 [cs.IT].