Quantum Permanent Compromise Attack to Blum-Micali Pseudorandom Generator

This paper presents a quantum permanent compromise attack to the Blum-Micali pseudorandom generator whose security is based on the assumption of intractability of the discrete logarithm problem. The proposed attack makes use of the Grover’s quantum search extension for multiple solutions and of quantum parallelism to recover the generator’s internal state with high probability. This attack compromises the unpredictability of the Blum-Micali cryptographic secure pseudorandom generator, since it recovers all previous and future output, as well as the generator’s seed. Compared to the classical equivalent attack, the quantum algorithm proposed has a quadratic speedup, and represents a menace against the security of a pseudorandom generator used in many real-world cryptosystems.