# Blum–Micali algorithm

(Redirected from 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 ${\displaystyle p}$ be an odd prime, and let ${\displaystyle g}$ be a primitive root modulo ${\displaystyle p}$. Let ${\displaystyle x_{0}}$ be a seed, and let

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

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

In order for this generator to be secure, the prime number ${\displaystyle p}$ needs to be large enough so that computing discrete logarithms modulo ${\displaystyle 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

1. ^ a b Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 416-417, Wiley; 2nd edition (October 18, 1996), ISBN 0471117099
2. ^ An improved pseudo-random generator based on the discrete logarithm problem R Gennaro - Journal of Cryptology, 2005 - Springer
3. ^ Manuel Blum and Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4 (1984): 850-864. online (pdf)
4. ^ Elloá B. Guedes, Francisco Marcos de Assis, Bernardo Lula Jr, Examples of the Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction http://arxiv.org/abs/1012.1776