Welcome to the resource topic for 2023/1639
Title:
Analysis of a Quantum Attack on the Blum-Micali Pseudorandom Number Generator
Authors: Tingfei Feng
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.
ePrint: https://eprint.iacr.org/2023/1639
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .