A Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction

Elloá B. Guedes, Francisco M. de Assis, Bernardo Lula Jr.

Abstract

The Blum-Micali construction defines cryptographically secure pseu- dorandom generators widely adopted in many real-world cryptosystems. By en- dangering this construction, the security of certain cryptographic applications may become vulnerable. In the attempt to menace the security of Blum-Micali construction, this paper presents a generalized quantum permanent compromise attack to it. This attack is based on Grover’s quantum search and on quantum parallelism to retrieve the generator’s internal state. Experimental results are also provided to support the number of bits the adversary must know to perform the attack successfully against the Blum-Micali generator. The attack may bring new security requirements to be imposed on pseudorandom numbers generators.