Paper 2023/1639

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

Tingfei Feng, Rose-Hulman Institute of Technology

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.

Available format(s)
Attacks and cryptanalysis
Publication info
Quantum AttackPseudorandom Number GeneratorGrover's SearchDiscrete LogarithmShor's Algorithm
Contact author(s)
fengt1 @ rose-hulman edu
2023-10-23: approved
2023-10-22: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Tingfei Feng},
      title = {Analysis of a Quantum Attack on the Blum-Micali Pseudorandom Number Generator},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1639},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.