Paper 2016/659
Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE
Joppe Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila
Abstract
Lattice-based cryptography offers some of the most attractive primitives
believed to be resistant to quantum computers. Following increasing
interest from both companies and government agencies in building quantum
computers, a number of works have proposed instantiations of practical post-quantum key exchange protocols based on hard problems in ideal lattices, mainly based on the Ring Learning With Errors (R-LWE) problem. While
ideal lattices facilitate major efficiency and storage benefits over their
non-ideal counterparts, the additional ring structure that enables these
advantages also raises concerns about the assumed difficulty of the underlying problems.
Thus, a question of significant interest to cryptographers, and
especially to those currently placing bets on primitives that will withstand
quantum adversaries, is how much of an advantage the additional ring structure
actually gives in practice.
Despite conventional wisdom that generic lattices might be too slow and
unwieldy, we demonstrate that LWE-based key exchange is quite practical: our
constant time implementation requires around 1.3ms computation time for each
party; compared to the recent NewHope R-LWE scheme, communication sizes
increase by a factor of 4.7
Note: Full version of ACM CCS 2016 proceedings paper. Updated with correct communication sizes in Table 4.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Major revision. ACM CCS 2016
- DOI
- 10.1145/2976749.2978425
- Keywords
- key exchangelattice-based cryptographyLWE
- Contact author(s)
- mironov @ google com
- History
- 2017-02-27: last of 3 revisions
- 2016-06-28: received
- See all versions
- Short URL
- https://ia.cr/2016/659
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/659, author = {Joppe Bos and Craig Costello and Léo Ducas and Ilya Mironov and Michael Naehrig and Valeria Nikolaenko and Ananth Raghunathan and Douglas Stebila}, title = {Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from {LWE}}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/659}, year = {2016}, doi = {10.1145/2976749.2978425}, url = {https://eprint.iacr.org/2016/659} }