Post-quantum cryptography

Lattice-based public-key cryptography

Public-key encryption

1997. Don Coppersmith, Adi Shamir. "Lattice attacks on NTRU." MR 98j:94016. Pages 52–61 in: Walter Fumy (editor). Advances in cryptology—EUROCRYPT '97, international conference on the theory and application of cryptographic techniques, Konstanz, Germany, May 11–15, 1997, proceedings. Lecture Notes in Computer Science 1233. Springer. ISBN 3-540-62975-0.

1997. Oded Goldreich, Shafi Goldwasser, Shai Halevi. "Eliminating decrpytion errors in the Ajtai-Dwork cryptosystem." Pages 105–111 in: Burton S. Kaliski, Jr. (editor). Advances in Cryptology—CRYPTO '97. 17th annual international cryptology conference, Santa Barbara, California, USA, August 17–21, 1997, proceedings. Lecture Notes in Computer Science 1294. Springer.

1997. Oded Goldreich, Shafi Goldwasser, Shai Halevi. "Public-key cryptosystems from lattice reduction problems." Pages 112–131 in: Burton S. Kaliski, Jr. (editor). Advances in Cryptology—CRYPTO '97. 17th annual international cryptology conference, Santa Barbara, California, USA, August 17–21, 1997, proceedings. Lecture Notes in Computer Science 1294. Springer.

1998. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. "NTRU: a ring-based public key cryptosystem." MR 1726077. Pages 267–288 in: Joe P. Buhler (editor). Algorithmic number theory. Proceedings of the 3rd international symposium (ANTS-III) held at Reed College, Portland, OR, June 21–25, 1998. Lecture Notes in Computer Science 1423. Springer. ISBN 3-540-64657-4. MR 2000g:11002.

1998. Phong Nguyen, Jacques Stern. "Cryptanalysis of the Ajtai-Dwork cryptosystem." MR 99i:94053. Pages 223–242 in: Hugo Krawczyk (editor). Advances in cryptology—CRYPTO '98, 18th annual international cryptology conference, Santa Barbara, California, USA, August 23–27, 1998, proceedings. Lecture Notes in Computer Science 1462. Springer. ISBN 3-540-64892-5.

2000. Jeffrey Hoffstein, Joseph H. Silverman. "Optimizations for NTRU." MR 2003f:94060. Pages 77–88 in: Kazimierz Alster, Jerzy Urbanowicz, Hugh C. Williams (editors). Public-key cryptography and computational number theory. Proceedings of the International Conference held in Warsaw, September 11–15, 2000. de Gruyter. ISBN 3-11-017046-9. MR 2002h:94001.

2001. Craig Gentry. "Key recovery and message attacks on NTRU-composite." MR 2003b:94045. Pages 182–194 in: Birgit Pftizmann (editor). Advances in cryptology—EUROCRYPT 2001. Proceedings of the 20th international annual conference on the theory and application of cryptographic techniques held in Innsbruck, May 6–10, 2001. Lecture Notes in Computer Science 2045. Springer. ISBN 3-540-42070-3. MR 2002k:94031.

2001. Daniele Micciancio. "Improving lattice based cryptosystems using the Hermite normal form." Pages 126–145 in: Joseph H. Silverman (editor). Cryptography and lattices. Proceedings of the 1st international conference (CaLC 2001) held in Providence, RI, March 29–30, 2001. Lecture Notes in Computer Science 2146. Springer. ISBN 3-540-42488-1. MR 2002m:11002.

2002. Phong Q. Nguyen, David Pointcheval. "Analysis and improvements of NTRU encryption paddings." MR 2005a:94065. Pages 210–225 in: Moti Yung (editor). Advances in Cryptology—CRYPTO 2002. 22nd annual international cryptology conference, Santa Barbara, California, USA, August 18–22, 2002, proceedings. Lecutre Notes in Computer Science 2442. Springer. ISBN 978-3-540-44050-5.

2003. John Proos. "Imperfect decryption and an attack on the NTRU encryption scheme." http://eprint.iacr.org/2003/002

2003. Nick Howgrave-Graham, Phong Q. Nguyen, David Pointcheval, John Proos, Joseph H. Silverman, Ari Singer, William Whyte. "The impact of decryption failures on the security of NTRU encryption." MR 2005e:94162. Pages 226–246 in: Dan Boneh (editor). Advances in cryptology—CRYPTO 2003, proceedings of the 23rd annual international cryptology conference held in Santa Barbara, CA, August 17–21, 2003. Lecture Notes in Computer Science 2729. Springer. ISBN 3-540-40674-3. MR 2005d:94151.

2004. Oded Regev. "New lattice-based cryptographic constructions." Journal of the ACM 51, 899–942. MR 2006e:94044. Older version: 2003. "New lattice based cryptographic constructions." MR 2005k:94025. Pages 407–416 in: Proceedings of the thirty-fifth annual ACM symposium on theory of computing. Held in San Diego, CA, 2003. ACM Press. ISBN 1-58113-674-9. MR 2005j:68009.

2005. Joseph H. Silverman, Nigel P. Smart, Frederik Vercauteren. "An algebraic approach to NTRU (q=2^n) via Witt vectors and overdetermined systems of nonlinear equations." Pages 278–293 in: Carlo Blundo, Stelvio Cimato (editors). Security in communication networks, 4th international conference, SCN 2004, Amalfi, Italy, September 8–10, 2004, revised selected papers. Lecture Notes in Computer Science 3352. Springer. ISBN 3-540-24301-1.

2005. Nick Howgrave-Graham, Joseph H. Silverman, William Whyte. "Choosing parameter sets for NTRUEncrypt with NAEP and SVES-3." MR 2006j:94066. Pages 118–135 in: Alfred Menezes (editor). Topics in cryptology—CT-RSA 2005. Proceedings of the cryptographers' track at the RSA conference held in San Francisco, CA, February 14–18, 2005. Lecture Notes in Computer Science 3376. Springer. MR 2006d:94073. ISBN 3-540-24399-2.

2005. Oded Regev. "On lattices, learning with errors, random linear codes, and cryptography." Pages 84–93 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. Miklós Ajtai. "Representing hard lattices with O(n log n) bits." Pages 94–103 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.

2006. Nicolas Gama, Nick Howgrave-Graham, Phong Q. Nguyen. "Symplectic lattice reduction and NTRU." MR 2423546. Pages 233–253 in: Serge Vaudenay (editor). Advances in Cryptology—EUROCRYPT 2006, 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28–June 1, 2006, proceedings. Lecture Notes in Computer Science 4004. Springer. ISBN 3-540-34546-9.

2007. Chris Peikert, Alon Rosen. "Lattices that admit logarithmic worst-case to average-case connection factors." Pages 478–487 in: David S. Johnson, Uriel Feige (editors). Proceedings of the 39th annual ACM symposium on theory of computing, San Diego, California, USA, June 11–13, 2007. ACM Press. ISBN 978-1-59593-631-8.

2007. Nicolas Gama, Phong Q. Nguyen. "New chosen-ciphertext attacks on NTRU." Pages 89–106 in: Tatsuaki Okamoto, Xiaoyun Wang (editors). Public key cryptography—PKC 2007, proceedings of the 10th international conference on practice and theory in public-key cryptography held at Tsinghua University, Beijing, April 16–20, 2007. Lecture Notes in Computer Science 4450. Springer. ISBN 3-540-71676-9. MR 2404107.

2007. Akinori Kawachi, Keisuke Tanaka, Keita Xagawa. "Multi-bit cryptosystems based on lattice problems." Pages 315–329 in: Tatsuaki Okamoto, Xiaoyun Wang (editors). Public key cryptography—PKC 2007, proceedings of the 10th international conference on practice and theory in public-key cryptography held at Tsinghua University, Beijing, April 16–20, 2007. Lecture Notes in Computer Science 4450. Springer. ISBN 3-540-71676-9. MR 2404107.

2007. Nick Howgrave-Graham. "A hybrid lattice-reduction and meet-in-the-middle attack against NTRU." Pages 150–169 in: Alfred Menezes (editor). Advances in cryptology—CRYPTO 2007, proceedings of the 27th annual international cryptology conference held in Santa Barbara, CA, August 19–23, 2007. Lecture Notes in Computer Science 4622. Springer. ISBN 978-3-540-74142-8.

2008. Chris Peikert. "Public-key cryptosystems from the worst-case shortest vector problem." http://eprint.iacr.org/2008/481.

2009. Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa. "Efficient public key encryption based on ideal lattices." http://eprint.iacr.org/2009/285.

Signatures

2001. Craig Gentry, Jakob Jonsson, Jacques Stern, Michael Szydlo. "Cryptanalysis of the NTRU signature scheme (NSS) from Eurocrypt 2001." Pages 1–20 in: Colin Boyd (editor). Advances in cryptology—ASIACRYPT 2001. Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security held on the Gold Coast, December 9–13, 2001. Lecture Notes in Computer Science 2248, Springer. ISBN 3-540-42987-5.

2002. Craig Gentry, Michael Szydlo. "Cryptanalysis of the revised NTRU signature scheme." Pages 299–320 in: Lars R. Knudsen (editor). Advances in cryptology—EUROCRYPT 2002, international conference on the theory and applications of cryptographic techniques, Amsterdam, the Netherlands, April 28–May 2, 2002, proceedings. Lecture Notes in Computer Science 2332. Springer. ISBN 3-540-43553-0.

2003. Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte. "NTRUSign: digital signatures using the NTRU lattice." MR 2080134. Pages 122–140 in: Marc Joye (editor). Topics in cryptology—CT-RSA 2003, the cryptographers' track at the RSA conference 2003, San Francisco, CA, USA, April 13–17, 2003, proceedings. Lecture Notes in Computer Science 2612. Springer. ISBN 3-540-00847-0. MR 2005b:94045.

2003. Michael Szydlo. "Hypercubic lattice reduction and analysis of GGH and NTRU signatures." Pages 433–448 in: Eli Biham (editor). Advances in cryptology—EUROCRYPT 2003, proceedings of the 22nd international conference on the theory and applications of cryptographic techniques held in Warsaw, May 4–8, 2003. Lecture Notes in Computer Science 2656. Springer. ISBN 3-540-14039-5. MR 2005c:94003.

2005. Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte. "Performance improvements and a baseline parameter generation algorithm for NTRUsign." http://www.ntru.com/cryptolab/pdf/NTRUSignParams-2005-08.pdf

2006. Phong Q. Nguyen, Oded Regev. "Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures." Pages 271–288 in: Serge Vaudenay (editor). Advances in Cryptology—EUROCRYPT 2006, 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28–June 1, 2006, proceedings. Lecture Notes in Computer Science 4004. Springer. ISBN 3-540-34546-9.

2008. Vadim Lyubashevsky, Daniele Micciancio. "Asymptotically efficient lattice-based digital signatures." Pages 37–54 in: Ran Canetti (editor). Theory of cryptography, fifth theory of cryptography conference, TCC 2008, New York, USA, March 19–21, 2008. Lecture Notes in Computer Science 4948. Springer. ISBN 978-3-540-78523-1.

Hashing, zero-knowledge proofs, etc.

1996. Oded Goldreich, Shafi Goldwasser, Shai Halevi. "Collision-free hashing from lattice problems." http://eccc.hpi-web.de/eccc-reports/1996/TR96-042/index.html.

1997. Jin-Yi Cai, Ajay Nerurkar. "An improved worst-case to average-case connection for lattice problems." Pages 468–477 in: 38th annual symposium on foundations of computer science, FOCS '97, Miami Beach, Florida, USA, October 19–22, 1997. IEEE.

1999. Miklós Ajtai. "Generating hard instances of the short basis problem." Pages 1--9 in: Jiri Wiedermann, Peter van Emde Boas, Mogens Nielsen (editors). Automata, languages and programming, 26th international colloquium, ICALP'99, Prague, Czech Republic, July 11–15, 1999. Lecture Notes in Computer Science 1644. Springer. ISBN 978-3-540-66224-2.

2002. Daniele Micciancio. "Improved cryptographic hash functions with worst-case/average-case connection." MR 2121187. Pages 609–618 in: Proceedings of the thirty-fourth annual ACM symposium on theory of computing. Held in Montreal, QC, 2002. ACM Press. ISBN 1-58113-495-9. MR 2005i:68004.

2003. Daniele Micciancio, Salil P. Vadhan. "Statistical zero-knowledge proofs with efficient provers: lattice problems and more." MR 2005e:68068. Pages 282–298 in: Dan Boneh (editor). Advances in cryptology—CRYPTO 2003, proceedings of the 23rd annual international cryptology conference held in Santa Barbara, CA, August 17–21, 2003. Lecture Notes in Computer Science 2729. Springer. ISBN 3-540-40674-3. MR 2005d:94151.

2006. Chris Peikert, Alon Rosen. "Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices." Pages 145–166 in: Shai Halevi, Tal Rabin (editors). Theory of cryptography, third theory of cryptography conference, TCC 2006, New York, NY, USA, March 4–7, 2006, proceedings. Lecture Notes in Computer Science 3876. Springer. ISBN 3-540-32731-2.

2006. Vadim Lyubashevsky, Daniele Micciancio. "Generalized compact knapsacks are collision resistant." MR 2007m:68072. Pages 144–155 in: Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener (editors). Automata, languages and programming. Part II. Proceedings of the 33rd International Colloquium (ICALP 2006) held in Venice, July 10–14, 2006. Lecture Notes in Computer Science 4052. Springer. ISBN 978-3-540-35907-4.

2007. Daniele Micciancio. "Generalized compact knapsacks, cyclic lattices, and efficient one-way functions." Computational Complexity 16, 365–411. MR 2008m:68050.

2007. Daniele Micciancio, Oded Regev. "Worst-case to average-case reductions based on Gaussian measures." SIAM Journal on Computing 37, 267–302. MR 2008c:68037. Older version: 2004. Pages 372–381 in: Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS).

2008. Craig Gentry, Chris Peikert, Vinod Vaikuntanathan. "Trapdoors for hard lattices and new cryptographic constructions." Pages 197–206 in: Richard E. Ladner, Cynthia Dwork (editors). Proceedings of the 40th annual ACM symposium on theory of computing, Victoria, British Columbia, Canada, May 17–20, 2008. ACM Press. ISBN 978-1-60558-047-0.

2008. Vadim Lyubashevsky. "Lattice-based identification schemes secure under active attacks." Pages 162–179 in: Ronald Cramer (editor). Public key cryptography—PKC 2008, 11th international workshop on practice and theory in public-key cryptography, Barcelona, Spain, March 9–12, 2008, proceedings. Lecture Notes in Computer Science 4939. Springer. ISBN 978-3-540-78439-5.

2008. Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen. "SWIFFT: a modest proposal for FFT hashing." Pages 54–72 in: Kaisa Nyberg (editor). Fast software encryption, 15th international workshop, FSE 2008, Lausanne, Switzerland, February 10–13, 2008, revised selected papers. Lecture Notes in Computer Science 5086. Springer. ISBN 978-3-540-71038-7.

2008. Chris Peikert, Brent Waters. "Lossy trapdoor functions and their applications." Pages 187–196 in: Richard E. Ladner, Cynthia Dwork (editors). Proceedings of the 40th annual ACM symposium on theory of computing, Victoria, British Columbia, Canada, May 17–20, 2008. ACM Press. ISBN 978-1-60558-047-0.

2008. Chris Peikert, Vinod Vaikuntanathan. "Noninteractive statistical zero-knowledge proofs for lattice problems." Pages 536–553 in: David Wagner (editor). Advances in cryptology—CRYPTO 2008, 28th annual international cryptology conference, Santa Barbara, CA, USA, August 17–21, 2008, proceedings. Lecture Notes in Computer Science 5157. Springer. ISBN 978-3-540-85173-8.

2008. Chris Peikert, Vinod Vaikuntanathan, Brent Waters. "A framework for efficient and composable oblivious transfer." Pages 554–571 in: David Wagner (editor). Advances in cryptology—CRYPTO 2008, 28th annual international cryptology conference, Santa Barbara, CA, USA, August 17–21, 2008, proceedings. Lecture Notes in Computer Science 5157. Springer. ISBN 978-3-540-85173-8.

2009. Joel Alwen, Chris Peikert. "Generating shorter bases for hard random lattices." http://www.cc.gatech.edu/~cpeikert/pubs/shorter.pdf

2009. Jonathan Katz, Vinod Vaikuntanathan. "Smooth projective hashing and password-based authenticated key exchange from lattices." http://www.cs.umd.edu/~jkatz/papers/lattice-PAK.pdf

Lattice-basis-reduction algorithms

1983. Ravi Kannan. "Improved algorithms for integer programming and related lattice problems." Pages 193–206 in: Proceedings of the 15th annual ACM symposium on theory of computing, 25–27 April, 1983, Boston, Massachusetts, USA. ACM Press.

1986. Laszlo Babai. "On Lovász lattice reduction and the nearest lattice point problem." Combinatorica 6, 1–13. MR 88a:68049.

1987. Claus-Peter Schnorr. "A hierarchy of polynomial time lattice basis reduction algorithms." Theoretical Computer Science 53, 201–224. MR 89h:11085.

1990. Jeffrey C. Lagarias, Hendrik W. Lenstra, Jr., Claus-Peter Schnorr. "Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice." Combinatorica 10, 333–348. MR 92a:11075.

1994. Claus-Peter Schnorr, M. Euchner. "Lattice basis reduction: improved practical algorithms and solving subset sum problems." Mathematical Programming 66, 181–199. MR 95j:90064. 1991 version: MR 1136071. Pages 68–85 in: L. Budach (editor). Fundamentals of computation theory. Proceedings of the eighth international conference (FCT '91) held in Gosen, September 9–13, 1991. Lecture Notes in Computer Science 529. Springer. ISBN 3-540-54458-5. MR 92g:68007.

1995. Claus-Peter Schnorr, Horst Helmut Hörner. "Attacking the Chor-Rivest cryptosystem by improved lattice reduction." MR 96k:94014. Pages 1–12 in: Louis C. Guillou and Jean-Jacques Quisquater (editors). Advances in cryptology—EUROCRYPT '95. Proceedings of the international conference on the theory and application of cryptographic techniques held in Saint-Malo, May 21–25, 1995. Lecture Notes in Computer Science 921. Springer. ISBN 3-540-59409-4. MR 96f:94001.

2000. Philip Klein. "Finding the closest lattice vector when it's unusually close." Pages 937–941 in: Proceedings of the eleventh annual ACM-SIAM symposium on discrete algorithms. Held in San Francisco, CA, January 9–11, 2000. ACM Press. ISBN 0-89871-453-2. MR 2000m:68010.

2001. Miklós Ajtai, Ravi Kumar, Dandapani Sivakumar. "An overview of the sieve algorithm for the shortest lattice vector problem." MR 2003c:11074. Pages 1–3 in: Joseph H. Silverman (editor). Cryptography and lattices. Proceedings of the 1st international conference (CaLC 2001) held in Providence, RI, March 29–30, 2001. Lecture Notes in Computer Science 2146. Springer. ISBN 3-540-42488-1. MR 2002m:11002.

2001. Miklós Ajtai, Ravi Kumar, Dandapani Sivakumar. "A sieve algorithm for the shortest lattice vector problem." MR 2005k:68224. Pages 601–610 in: Proceedings of the thirty-third annual ACM symposium on theory of computing. Held in Hersonissos, 2001. ACM Press. ISBN 1-58113-349-9. MR 2005j:68008.

2003. Claus P. Schnorr. "Lattice reduction by random sampling and birthday methods." MR 2005c:68108. Pages 145–156 in: Helmut Alt, Michel Habib (editors). STACS 2003. Proceedings of the 20th annual symposium on theoretical aspects of computer science held at the Freie Universitaet Berlin, Berlin, February 27–March 1, 2003. Lecture Notes in Computer Science 2607. Springer. ISBN 3-540-00623-0. MR 2005b:68025.

2003. Avrim Blum, Adam Kalai, Hal Wasserman. "Noise-tolerant learning, the parity problem, and the statistical query model." Journal of the ACM 50, 506–519. MR 2005m:68106. Older version: 2000. MR 2115279. Pages 435–440 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 Press. ISBN 1-58113-184-4. MR 2005i:68003.

2006. Claus-Peter Schnorr. "Fast LLL-type lattice reduction." Information and Computation 204, 1–25. MR 2006k:11129.

2006. Nicolas Gama, Nick Howgrave-Graham, Henrik Koy, Phong Q. Nguyen. "Rankin's constant and blockwise lattice reduction." Pages 112–130 in: Cynthia Dwork (editor). Advances in cryptology—CRYPTO 2006. Proceedings of the 26th annual international cryptology conference held in Santa Barbara, CA, August 20–24, 2006. Lecture Notes in Computer Science 4117. Springer. ISBN 978-3-540-37432-9. MR 2422188.

2007. Guillaume Hanrot, Damien Stehlé. "Improved analysis of Kannan's shortest lattice vector algorithm." Pages 170–186 in: Alfred Menezes (editor). Advances in cryptology—CRYPTO 2007, proceedings of the 27th annual international cryptology conference held in Santa Barbara, CA, August 19–23, 2007. Lecture Notes in Computer Science 4622. Springer. ISBN 978-3-540-74142-8.

2008. Nicolas Gama, Phong Q. Nguyen. "Finding short lattice vectors within Mordell's inequality." Pages 207–216 in: Richard E. Ladner, Cynthia Dwork (editors). Proceedings of the 40th annual ACM symposium on theory of computing, Victoria, British Columbia, Canada, May 17–20, 2008. ACM Press. ISBN 978-1-60558-047-0.

2008. Nicolas Gama, Phong Q. Nguyen. "Predicting lattice reduction." Pages 31–51 in: Nigel P. Smart (editor). Advances in cryptology—EUROCRYPT 2008, 27th annual international conference on the theory and applications of cryptographic techniques, Istanbul, Turkey, April 13–17, 2008. Lecture Notes in Computer Science 4965. Springer. ISBN 978-3-540-78966-6.

2008. Phong Q. Nguyen, Thomas Vidick. "Sieve algorithms for the shortest vector problem are practical." Journal of Mathematical Cryptology 2, 181–207. MR 2433251.

2008. Johannes Buchmann, Richard Lindner, Markus Rückert. "Explicit hard instances of the shortest vector problem." Pages 79–94 in: Johannes Buchmann, Jintai Ding (editors). Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008, proceedings. Lecture Notes in Computer Science 5299, Springer.

2008. Xavier Pujol, Damien Stehlé. "Rigorous and efficient short lattice vectors enumeration." Pages 390–405 in: Josef Pieprzyk (editor). Advances in cryptology—ASIACRYPT 2008, 14th international conference on the theory and application of cryptology and information security, Melbourne, Australia, December 7–11, 2008. Lecture Notes in Computer Science 5350. Springer. ISBN 978-3-540-89254-0.

2009. Phong Q. Nguyen, Damien Stehlé. "Low-dimensional lattice basis reduction revisited." MR 2571909. ACM Transactions on Algorithms 5, article 46, 48 pages. 2004 version: MR 2006a:11085. Pages 338–357 in: Duncan Buell (editor). Algorithmic number theory, proceedings of the 6th international symposium (ANTS-VI) held at the University of Vermont, Burlington, VT, June 13–18, 2004. Lecture Notes in Computer Science 3076, Springer. ISBN 3-540-22156-5. MR 2005m:11002.

2009. Phong Q. Nguyen, Damien Stehlé. "An LLL algorithm with quadratic complexity." MR 2538842. SIAM Journal on Computing 39, 874–903. 2005 version: "Floating-point LLL revisited." Pages 215–233 in: EUROCRYPT 2005. Ronald Cramer (editor). Advances in cryptology—EUROCRYPT 2005. Proceedings of the 24th annual international conference on the theory and applications of cryptographic techniques held in Aarhus, May 22–26, 2005. Lecture Notes in Computer Science 3494. Springer. ISBN 3-540-25910-4. MR 2008e:94035.

2010. Daniele Micciancio, Panagiotis Voulgaris. "Faster exponential time algorithms for the shortest vector problem." SODA 2010.

2010. Nicolas Gama, Phong Q. Nguyen, Oded Regev. "Lattice enumeration using extreme pruning." EUROCRYPT 2010.

2010. Daniele Micciancio, Panagiotis Voulgaris. "A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations." STOC 2010.

The impact of quantum computers

2004. Oded Regev. "Quantum computation and lattice problems." SIAM Journal on Computing 33, 738–760. Older version: 2002. Pages 520–529 in: Proceedings of the 43rd symposium on foundations of computer science (FOCS 2002), 16--19 November 2002, Vancouver, BC, Canada, proceedings. IEEE. ISBN 0-7695-1822-2.

Hardness of lattice problems

1998. Miklós Ajtai. "The shortest vector problem in L[2] is NP-hard for randomized reductions (extended abstract)." Pages 10–19 in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, Dallas, Texas, USA, May 23–26, 1998. ACM Press. ISBN 0-89791-962-9.

1999. Jin-Yi Cai, Ajay Nerurkar. "Approximating the SVP to within a factor (1+1/dim^epsilon) is NP-hard under randomized reductions." Journal of Computer and System Sciences 59, 221–239. MR 2001j:68045.

2000. Oded Goldreich, Shafi Goldwasser. "On the limits of nonapproximability of lattice problems." Journal of Computer and System Sciences 60, 540–563. MR 2001e:68081. Older version: 1998. Pages 1–9 in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, Dallas, Texas, USA, May 23–26, 1998. ACM Press. ISBN 0-89791-962-9.

2001. Daniele Micciancio. "The hardness of the closest vector problem with preprocessing." IEEE Transactions on Information Theory 47, 1212–1215. MR 2002m:68047.

2001. Daniele Micciancio. "The shortest vector in a lattice is hard to approximate to within some constant." SIAM Journal on Computing 30, 2008–2035. MR 2003f:68050. Older version: 1998. Pages 92–98 in: 39th annual symposium on foundations of computer science, FOCS '98, November 8–11, 1998, Palo Alto, California, USA. IEEE.

2003. Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra. "Approximating CVP to within almost-polynomial factors is NP-hard." Combinatorica 23, 205–243. MR 2004h:68046.

2005. Subhash Khot. "Hardness of approximating the shortest vector problem in lattices." Journal of the ACM 52, 789–808. Older version: 2004. Pages 126–135 in: 45th symposium on foundations of computer science (FOCS 2004), 17–19 October 2004, Rome, Italy, proceedings. IEEE. ISBN 0-7695-2228-9.

2005. Dorit Aharonov, Oded Regev. "Lattice problems in NP \cap coNP." Journal of the ACM 52, 749–765. Older version: 2004. 45th symposium on foundations of computer science (FOCS 2004), 17–19 October 2004, Rome, Italy, proceedings. IEEE. ISBN 0-7695-2228-9.

2006. Subhash Khot. "Hardness of approximating the shortest vector problem in high l^p norms." Journal of Computer and System Sciences 72, 206–219. MR 2007b:68066.

2007. Ishay Haviv, Oded Regev. "Tensor-based hardness of the shortest vector problem to within almost polynomial factors." Pages 469–477 in: Uriel Feige (editor). STOC'07—proceedings of the 39th annual ACM symposium on theory of computing. Held in San Diego, CA, June 11–13, 2007. ISBN 978-1-59593-631-8. MR 2367396.

2007. Oded Regev. "On the complexity of lattice problems with polynomial approximation factors." http://www.cs.tau.ac.il/~odedr/

2008. Chris Peikert. "Limits on the hardness of lattice problems in l^p norms." Computational Complexity 17, 300–351.

2009. Vadim Lyubashevsky, Daniele Micciancio. "On bounded distance decoding, unique shortest vectors, and the minimum distance problem." Pages 577–594 in: Shai Halevi (editor). Advances in cryptology—CRYPTO 2009. Proceedings of the 29th annual international cryptology conference held in Santa Barbara, CA, August 16–20, 2009. Lecture Notes in Computer Science 5677. Springer. ISBN 978-3-642-03355-1.

Surveys

2002. Daniele Micciancio, Shafi Goldwasser. Complexity of lattice problems: a cryptographic perspective. The Kluwer International Series in Engineering and Computer Science 671. Kluwer. ISBN 0-7923-7688-9. MR 2004m:94067.

2003. Phong Q. Nguyen, Jacques Stern. "The two faces of lattices in cryptology." Pages 146–180 in: Joseph H. Silverman (editor). Cryptography and lattices. Proceedings of the 1st international conference (CaLC 2001) held in Providence, RI, March 29–30, 2001. Lecture Notes in Computer Science 2146. Springer. ISBN 3-540-42488-1. MR 2002m:11002.

2004. Oded Regev. "Lattices in computer science." Lecture notes. http://www.cs.tau.ac.il/~odedr/teaching/lattices_fall_2004/index.html

2006. Oded Regev. "Lattice-based cryptography." MR 2422159. Pages 131–141 in: Cynthia Dwork (editor). Advances in cryptology—CRYPTO 2006. Proceedings of the 26th annual international cryptology conference held in Santa Barbara, CA, August 20–24, 2006. Lecture Notes in Computer Science 4117. Springer. ISBN 978-3-540-37432-9. MR 2422188.

2007. Daniele Micciancio. "Cryptographic functions from worst-case complexity assumptions." http://www-cse.ucsd.edu/~daniele/papers/LLL25.html

2009. Daniele Micciancio, Oded Regev. "Lattice-based cryptography." Pages 147–191 in: Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen (editors). Post-quantum cryptography. Springer. ISBN 978-3-540-88701-0.

2010. Phong Q. Nguyen, Brigitte Vallée (editors). The LLL algorithm: survey and applications. Springer. ISBN 978-3-642-02294-4.

Version