Algorithmics and Lattices, some references

Lattice-based Cryptosystems

Back to the main page

Ajtai-Dwork:

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence, Ajtai M. and Dwork C. (1996)
Positive Applications of Lattices to Cryptography, Dwork C. (1997)
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem, Goldreich O. and Goldwasser S. and Halevi S. (1997)
A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications, Nguyen P. and Stern J. (1998)
Cryptanalysis of the Ajtai-Dwork Cryptosystem, Nguyen P. and Stern J. (1998)

GGH, Goldreich-Goldwasser-Halevi:

Public-Key Cryptosystems from Lattice Reduction Problems, Goldreich O. and Goldwasser S. and Halevi S. (1997)
Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97, Nguyen P. (1999)

NTRU:

Lattice Attacks on NTRU, Coppersmith D. and Shamir A. (1997)
NTRU: A Ring-Based Public Key Cryptosystem, Hoffstein J. and Pipher J. and Silverman J.H. (1998)
A Note on Cryptanalysis of the Preliminary Version of the NTRU Signature Scheme, Mironov I. (2001)
NTRU in Constrained Devices, Bailey D.V. and Coffin D. and Elbirt A. and Silverman J.H. and Woodbury A.D. (2001)
NSS: An NTRU Lattice-Based Signature Scheme, Hoffstein J. and Pipher J. and Silverman J.H. (2001)
Dimension Reduction Methods for Convolution Modular Lattices, May A. and Silverman H. (2001)
Key Recovery and Message Attacks on NTRU-Composite, Gentry C. (2001)
Cryptanalysis of the NTRU Signature Scheme, (NSS), from Eurocrypt 2001, Gentry C. and Jonsson J. and Stern J. and Szydlo M. (2001)
NTRUSign: Digital Signatures using the NTRU Lattice, Hoffstein J. and Howgrave-Graham N. and Pipher J. and Silverman J.H. and Whyte W. (2001)
Analysis of the Revised NTRU Signature Scheme R-NSS, Gentry C. and Szydlo M. (2002)
Analysis and Improvements of NTRU Encryption Paddings, Nguyen P. and Pointcheval D. (2002)
Hypercubic Lattice Reduction and Analysis of GGH and NTRUSign Signatures, Szydlo M. (2003)
Hypercubic Lattice Reduction and Analysis of GGH and NTRUSign Signatures, Szydlo M. (2003)
* The Impact of Decryption Failures on the Security of NTRU Encryption, Howgrave-Graham N. and Nguyen P. and Pointcheval D. and Proos J. and Silverman J. and Singer A. and Whyte W. (2003)

Other Lattice-based cryptographic protocols:

Collision-Free Hashing from Lattice Problems, Goldreich O. and Goldwasser S. and Halevi S. (1996)
A Lattice-Based Public-Key Cryptosystem, Cai J.Y. and Cusick T. (1998)
The Modular Inversion Hidden Number Problem, Boneh D. and Halevi S. and Howgrave-Graham N. (2001)
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-way Functions from Worst-case Complexity Assumptions, Micciancio D. (2002)
Improved cryptographic hash functions with worst-case/average-case connection , Micciancio D. (2002)
New Lattice Based Cryptographic Constructions, Regev O. (2002)
A Lattice Based Public Key Cryptosystem Using Polynomial Representations, Paeng S.-H. and Jung B.E. and Ha K.-C. (2003)
Statistical zero-knowledge proofs with efficient provers: lattice problems and more, Micciancio D. and Vadhan S. (2003)

Other articles:

Tensor-Based Trapdoors for CVP and Their Application to Public Key Cryptography, Fischlin R. and Seifert J.P. (1999)
Improving Lattice based cryptosystems using the Hermite Normal Form, Micciancio D. (2001)

Last update: 10/31/2003. Page maintained by Damien Stehlé : damien.stehle@loria.fr