Title

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

Authors

Tingfei Feng, Rose-Hulman Institute of TechnologyFollow

Document Type

Dissertation

Publication Date

6-2022

First Advisor

Joshua Holden

Abstract

In 2012, Guedes, Assis, and Lula proposed a quantum attack on a pseudorandom number generator named the Blum-Micali Pseudorandom number generator. They claimed that the quantum attack can outperform classical attacks super-polynomially. However, this paper shows that the quantum attack cannot get the correct seed and provides another corrected algorithm that is in exponential time but still faster than the classical attack. Since the original classical attacks are in exponential time, the Blum-Micali pseudorandom number generator would be still quantum resistant.

Comments

Senior Thesis, Department of Computer Science, Rose-Hulman Institute of Technology

Recommended Citation

Feng, Tingfei, "Analysis of a Quantum Attack on the Blum-Micali Pseudorandom Number Generator" (2022). Mathematical Sciences Technical Reports (MSTR). 180.
https://scholar.rose-hulman.edu/math_mstr/180