Lattice Cryptography & Reduction

• Papers
  • Generating Hard Instances of Lattice Problems (Miklos Ajtai)
  • Collision-Free Hashing from Lattice Problems (Oded Goldreich, Shafi Goldwasser, and Shai Halevi, ECCC Report TR96-042)
  • Public-Key Cryptosystems from Lattice Reduction Problems (Oded Goldreich, Shafi Goldwasser, Shai Halevi, ECCC Report TR96-056)
  • A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence (Miklos Ajtai, Cynthia Dwork, ECCC Report TR96-065, Revision 01, Comment 01)
  • Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem (Oded Goldreich, Shafi Goldwasser, and Shai Halevi, ECCC Report TR97-018)
  • A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications (Phong Nguyen and Jacques Stern, ECCC Report TR98-010)
  • A Lattice-Based Public-Key Cryptosystem (Cai, Cusick, SAC 98)
  • Cryptanalysis of the Ajtai-Dwork Cryptosystem (Phong Nguyen, Jacques Stern, Crypto 98)
  • The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant (Daniele Micciancio, ECCC Report TR98-016)
  • Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97 (Phong Nguyen, Crypto '99)
  • Tensor-Based Trapdoors for CVP and Their Application to Public Key Cryptography (R.Fischlin, J.-P. Seifert, 1999)
  • New Lattice Based Cryptographic Constructions (Oded Regev, STOC 2003)
  • Worst-case to Average-case Reductions based on Gaussian Measures (Daniele Micciancio, Oded Regev, STOC 2004)
  • Representing hard lattices with O(n log n) bits (Miklos Ajtai, STOC 2005)
  • On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (Oded Regev, STOC 2005)
  • Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices (Chris Peikert, Alon Rosen, TCC 2006)
  • Generalized compact knapsacks are collision resistant (Vadim Lyubashevsky, Daniele Micciancio, ICALP 2006)
    • Full version
  • Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors (Chris Peikert, Alon Rosen, STOC 2007)
  • Asymptotically efficient lattice-based digital signatures (Vadim Lyubashevsky and Daniele Micciancio, TCC 2008)
  • Lattice-based identification schemes secure under active attacks (Vadim Lyubashevsky, PKC 2008)
  • Trapdoors for Hard Lattices and New Cryptographic Constructions (Craig Gentry, Chris Peikert, Vinod Vaikuntanathan, STOC 2008)
  • Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems (Chris Peikert, Vinod Vaikuntanathan, Crypto 2009)
  • Limits on the Hardness of Lattice Problems in l_p Norms (Chris Peikert, Computational Complexity 2008)
  • Generating Shorter Bases for Hard Random Lattices (Joel Alwen, Chris Peikert, STACS 2009)
  • Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem (Chris Peikert, STOC 2009)
  • On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem (Vadim Lyubashevsky and Daniele Micciancio, Crypto 2009)
  • Faster exponential time algorithms for the shortest vector problem (Panagiotis Voulgaris, Daniele Micciancio, ECCC 2009-065)
• Overviews
  • Lattice-based Cryptography (Oded Regev, tutorial at Crypto 2006)
  • Lattices (Definition by Micciancio)
  • Lattice-based Cryptography (Danile Micciancio, Oded Regev, in "Post-Quantum Cryptography", 2009)
• Links/.../surveys on Lattice-Based Cryptography
  • Using Lattice Problem in Cryptography (Oded Goldreich, Shafi Goldwasser and Shai Halevi)
  • Challenge
  • Generating Hard Instances of Lattice Problems (Miklos Ajtai, ECCC Report TR96-007)
  • Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions (Daniele Micciancio, ECCC TR04-095)
  • Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices (Chris Peikert, Alon Rosen, ECCC TR05-158)
  • Trapdoors for Hard Lattices and New Cryptographic Constructions (Craig Gentry and Chris Peikert and Vinod Vaikuntanathan, STOC 2008)
  • Finding Short Lattice Vectors within Mordell's Inequality (Nicolas Gama and Phong Q. Nguyen, STOC 2008)
• @NTRU
• @Lattice reduction
• Research groups
  • Lattice-based cryptography (MIT page)
• Lecture Courses
  • Lattices in Cryptography and Cryptanalysis (Course by Daniele Micciancio)
  • Lattices and Their Application to Cryptography (Cynthia Dwork, Stanford, 1998)
• Books
  • Complexity of Lattice Problems: A Cryptographic Perspective (Daniele Micciancio and Shafi Goldwasser, 2002)

  ---

  
  
  Cryptology Pointers by Helger Lipmaa
  Got any suggestions or additional links? Mail to <lipmaa>research.cyber.ee
  NB! If you find any broken links, please be kind and report them to me together with their current location!
  
  (C) Helger Lipmaa 1997-2009.