Public-Key Cryptosystems from Lattice Reduction Problems

Authors: Oded Goldreich, Shafi Goldwasser and Shai Halevi.

Reference: Advances in Cryptology - CRYPTO '97. Lecture Notes in Computer Science, vol. 1294, Pages 112-131, Springer-Verlag, 1997.

Abstract: We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured computational difficulty of lattice-reduction problems, providing a possible alternative to existing public-key encryption algorithms and digital signatures such as RSA and DSS.

Keywords: Public-Key Cryptosystems, Lattice Reduction Problems

Availability: An early version is available as either MIT-LCS-TR-703, or Theory of Cryptography Library: Record 96-16. A more updated version is available as Compressed PostScript (59 Kbyte).

Shai Halevi's home page.