Paper 2023/1639 Original: eprint.iacr.org/2023/1639 ↗

Analysis of a Quantum Attack on the Blum-Micali Pseudorandom Number Generator

Abstract

This paper re-analyzes the algorithm proposed by Guedes, Assis, and Lula in 2012, which they claimed that the algorithm can break Blum-Micali Pseudorandom number generator in polynomial time. We used a 5×5 transformation matrix instead of the original 2×2 transformation matrix, which can include terms that they missed in their analysis. We proved that their proposed algorithm cannot break the pseudorandom number generator, because during the amplitude amplification process, two iterations of the circuit is the same as an identity gate. To solve this problem, we proposed a corrected algorithm based on Grover’s Search Algorithm for NP-complete problems, which breaks the Blum-Micali Pseudorandom number generator in \(\mathcal{O}(n^4 2^{n/2})\). We conclude that the Blum-Micali Pseudorandom number generator is still quantum resistant. This study indicates that the discrete logarithm problem and prime factorization could still be the foundations of quantum-resistant cryptographical applications.