An official website of the United States government
Abstract In this survey, the authors review the main quantum algorithms for solving the computational problems that serve as hardness assumptions for cryptosystem. To this end, the authors consider both the currently most widely used classically secure cryptosystems, and the most promising candidates for post‐quantum secure cryptosystems. The authors provide details on the cost of the quantum algorithms presented in this survey. The authors furthermore discuss ongoing research directions that can impact quantum cryptanalysis in the future.
more »
« less
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
We present a proof under a generalization of the Riemann Hypothesis that the class group algorithm of Hafner and McCurley runs in expected time \begin{document}$$ e^{\left(3/\sqrt{8}+o(1)\right)\sqrt{\log d\log\log d}} $$\end{document} where \begin{document}$ -d $$\end{document} is the discriminant of the input imaginary quadratic order. In the original paper, an expected run time of \begin{document}$$ e^{\left(\sqrt{2}+o(1)\right)\sqrt{\log d\log\log d}} $$\end{document}$ was proven, and better bounds were conjectured. To achieve a proven result, we rely on a mild modification of the original algorithm, and on recent results on the properties of the Cayley graph of the ideal class group.more » « less
Full Text Available