Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Quantum AttackPseudorandom Number GeneratorGrover's SearchDiscrete LogarithmShor's Algorithm
- Contact author(s)
- fengt1 @ rose-hulman edu
- History
- 2023-10-23: approved
- 2023-10-22: received
- See all versions
- Short URL
- https://ia.cr/2023/1639
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2023/1639,
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{https://eprint.iacr.org/2023/1639}},
url = {https://eprint.iacr.org/2023/1639}
}
