Paper 2014/070

Lattice Cryptography for the Internet

Chris Peikert


In recent years, \emph{lattice-based} cryptography has been recognized for its many attractive properties, such as strong provable security guarantees and apparent resistance to quantum attacks, flexibility for realizing powerful tools like fully homomorphic encryption, and high asymptotic efficiency. Indeed, several works have demonstrated that for basic tasks like encryption and authentication, lattice-based primitives can have performance competitive with (or even surpassing) those based on classical mechanisms like RSA or Diffie-Hellman. However, there still has been relatively little work on developing lattice cryptography for deployment in \emph{real-world} cryptosystems and protocols. In this work we take a step toward that goal, by giving efficient and practical lattice-based protocols for key transport, encryption, and authenticated key exchange that are suitable as ``drop-in'' components for proposed Internet standards and other open protocols. The security of all our proposals is provably based (sometimes in the random-oracle model) on the well-studied ``learning with errors over rings'' problem, and hence on the conjectured worst-case hardness of problems on ideal lattices (against quantum algorithms). One of our main technical innovations (which may be of independent interest) is a simple, low-bandwidth \emph{reconciliation} technique that allows two parties who ``approximately agree'' on a secret value to reach \emph{exact} agreement, a setting common to essentially all lattice-based encryption schemes. Our technique reduces the ciphertext length of prior (already compact) encryption schemes nearly twofold, at essentially no cost.

Note: Minor updates; diagram of reconciliation mechanism.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. PQCrypto 2014
lattice cryptographyefficiencykey encapsulationtransportauthenticated key exchangestandards
Contact author(s)
cpeikert @ cc gatech edu
2014-07-17: last of 3 revisions
2014-02-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Peikert},
      title = {Lattice Cryptography for the Internet},
      howpublished = {Cryptology ePrint Archive, Paper 2014/070},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.