Post-quantum cryptography

Motivation:

Introduction

Quantum computing

Cryptography:

Community:

Using quantum computers for cryptanalysis

Shor's algorithm and extensions

1997. Peter W. Shor. "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer." SIAM Journal on Computing 26, 1484–1509. MR 98i:11108. 1994 version: "Algorithms for quantum computation: discrete logarithms and factoring." MR 1489242. Pages 124–134 in: Shafi Goldwasser (editor). 35th annual IEEE symposium on the foundations of computer science. Proceedings of the IEEE symposium held in Santa Fe, NM, November 20–22, 1994. IEEE. ISBN 0-8186-6580-7. MR 98h:68008.

2003. John Proos, Christof Zalka. "Shor's discrete logarithm quantum algorithm for elliptic curves." Quantum Information & Computation 3, 317–344. MR 2004h:81067.

2005. Greg Kuperberg. "A subexponential-time quantum algorithm for the dihedral hidden subgroup problem." SIAM Journal on Computing 35, 170–188. MR 2007d:81040.

2005. Sean Hallgren. "Fast quantum algorithms for computing the unit group and class group of a number field." MR 2006g:81032. Pages 468–474 in: STOC'05: proceedings of the 37th annual ACM symposium on theory of computing. Held in Baltimore, MD, May 22–24, 2005. ACM Press. ISBN 1-58113-960-8. MR 2006f:68006.

2005. Arthur Schmidt, Ulrich Vollmer. "Polynomial time quantum algorithm for the computation of the unit group of a number field." Pages 475–480 in: STOC'05: proceedings of the 37th annual ACM symposium on theory of computing. Held in Baltimore, MD, May 22–24, 2005. ACM Press. ISBN 1-58113-960-8. MR 2006f:68006.

2007. Sean Hallgren. "Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem." Journal of the ACM 54, 1–19. MR 2008c:11166.

Grover's algorithm and extensions

1996. Lov K. Grover. "A fast quantum mechanical algorithm for database search." MR 1427516. Pages 212–219 in: Proceedings of the twenty-eighth annual ACM symposium on the theory of computing, held in Philadelphia, PA, May 22–24, 1996. ACM Press. ISBN 0-89791-785-5. MR 97g:68005.

1997. Lov K. Grover. "Quantum mechanics helps in searching for a needle in a haystack." Physical Review Letters 79, 325–328.

1998. Gilles Brassard, Peter Høyer, Alain Tapp. "Quantum cryptanalysis of hash and claw-free functions." MR 99g:94013. Pages 163–169 in: Claudio L. Lucchesi, Arnaldo V. Moura (editors). LATIN'98: theoretical informatics. Proceedings of the 3rd Latin American symposium held in Campinas, April 20–24, 1998. Lecture Notes in Computer Science 1380. Springer. ISBN 3-540-64275-7. MR 99d:68007.

1998. Gilles Brassard, Peter Høyer, Alain Tapp. "Quantum counting." MR 2000a:68023. Pages 820–831 in: Kim G. Larsen, Sven Skyum, Glynn Winskel (editors). Automata, languages and programming. Proceedings of the 25th international colloquium (ICALP'98) held in Aalborg, July 13–17, 1998. Lecture Notes in Computer Science 1443. Springer. ISBN 3-540-64781-3. MR 99m:68007.

2000. Lov K. Grover. "Rapid sampling through quantum computing." MR 2115300. Pages 618–626 in: Proceedings of the thirty-second annual ACM symposium on theory of computing. Papers from the symposium (STOC '00) held in Portland, OR, May 21–23, 2000. ACM. MR 2005i:68003. ISBN 1-58113-184-4.

2001. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf. "Quantum lower bounds by polynomials." Journal of the ACM 48, 778–797. MR 2005m:68083.

2003. Lov K. Grover, Terry Rudolph. "How significant are the known collision and element distinctness quantum algorithms?" Quantum Information & Computation 4, 201–206. MR 2005c:81037.

2004. Sandor Imre, Ferenc Balazs. "The generalized quantum database search algorithm." Computing 73, 245–269. MR 2006c:68048.

2004. Scott Aaronson, Yaoyun Shi. "Quantum lower bounds for the collision and the element distinctness problems." Journal of the ACM 51, 595–605. MR 2006m:68016.

2005. Andris Ambainis. "Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range." Theory of Computing 1, 37–46. MR 2322513.

2007. Hartmut Klauck, Robert Spalek, Ronald de Wolf. "Quantum and classical strong direct product theorems and optimal time-space tradeoffs." SIAM Journal on Computing 36, 1472–1493. MR 2284091.

Surveys

2000. Michael A. Nielsen, Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press.

2001. Mika Hirvensalo. Quantum computing. Springer. ISBN 3-540-66783-0.

2002. Samuel J. Lomonaco, Jr. (editor). Quantum computation: a grand mathematical challenge for the twenty-first century and the millennium. American Mathematical Society. ISBN 0-8218-2084-2.

2003. Peter W. Shor. "Why haven't more quantum algorithms been found?" Journal of the ACM 50, 87–90.

2007. Phillip Kaye, Raymond Laflamme, Michele Mosca. An introduction to quantum computing. Oxford. ISBN 978-0-19-857049-3. MR 2008k:81065.

2007. N. David Mermin. Quantum computer science. An introduction. Cambridge. ISBN 978-0-521-87658-2. MR 2341010.

2008. David McMahon. Quantum computing explained. Wiley. ISBN 978-0-470-09699-4. MR 2008j:81023.

2008. Mikio Nakahara, Tetsuo Ohmi. Quantum computing. From linear algebra to physical realizations. CRC Press. ISBN 978-0-7503-0983-7. MR 2387891.

2009. Sean Hallgren, Ulrich Vollmer. "Quantum computing." Pages 15–34 in: Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen (editors). Post-quantum cryptography. Springer, Berlin. ISBN 978-3-540-88701-0.

Version

This is version 2008.11.30 of the quantum.html web page.