Lattice-based Cryptography

LATTICE-BASED CRYPTOGRAPHY


Identifying hard computational problems which are amenable for cryptographic use is a very important task. Although hard computational problems seem to be all around us, only very few of those problems were found to be useful for cryptography. A current research direction of ours and others is centered around the design of cryptosystems which are based on geometric problems (in particular, problems on integer lattices).

BOOKS

Goldwasser, S. and Micciancio, D. “Complexity of Lattice Problems: A Cryptographic Perspective.” Kluwer international Series in Engineering and Computer Science, Kluwer Academic Publishers, March 2002.

ARTICLES IN REFEREED CONFERENCES OR JOURNALS

Goldwasser, S., Kalai, Y.T., Peikert, C., and Vaikuntanathan, V. “Robustness of the Learning with Errors Assumption.” Innovations in Computer Science (ICS 2010), pages 230-240, Beijing, China, January 2010.

Goldwasser, S. and Kharchenko, D. “Proof of Plaintext Knowledge for the Ajtai-Dwork Cryptosystem.” Theory of Cryptopgrahy, Second Theory of Cryptography Conference (TCC 2005), volume 3378 of Lecture Notes in Computer Science, pages 529-555, 2005. Springer.

Golderich, O. and Goldwasser, S. “On the Limits of Non-Approximability of Lattice Problems.” J. of Computer and System Sciences, 60(3):540-563, June 2000.

Goldreich, O., Goldwasser, S., and Halevi, S. “Public-Key Cryptosystems from Lattice Reduction Problems.” B. Kaliski, Jr., editor, Advances in Cryptology (Proceedings of CRYPTO 1997, Santa Barbara, CA, August 1997), volume 1294 of Lecture Notes in Computer Science, pages 112-131, 1997. Springer.

Goldreich, O., Goldwasser, S., and Halevi, S. “Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.” B. Kaliski, Jr., editor, Advances in Cryptology (Proceedings of CRYPTO 1997, Santa Barbara, CA, August 1997), volume 1294 of Lecture Notes in Computer Science, pages 105-111, Springer. 1997.