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.
Category / Keywords: cryptographic protocols / lattice cryptography, efficiency, key encapsulation/transport, authenticated key exchange, standards Original Publication (with major differences): PQCrypto 2014 Date: received 31 Jan 2014, last revised 16 Jul 2014 Contact author: cpeikert at cc gatech edu Available format(s): PDF | BibTeX Citation Note: Minor updates; diagram of reconciliation mechanism. Version: 20140717:020257 (All versions of this report) Short URL: ia.cr/2014/070 Discussion forum: Show discussion | Start new discussion