Douglas Stebila

Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE

Performance of Apache HTTP server using post-quantum key exchange, measured in connections per second, connection time in milliseconds, and handshake size in bytes.

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.7x, but remain under 12 KiB in each direction. Our protocol is competitive when used for serving web pages over TLS; when partnered with ECDSA signatures, latencies increase by less than a factor of 1.6x, and (even under heavy load) server throughput only decreases by factors of 1.5x and 1.2x when serving typical 1 KiB and 100 KiB pages, respectively. To achieve these practical results, our protocol takes advantage of several innovations. These include techniques to optimize communication bandwidth, dynamic generation of public parameters (which also offers additional security against backdoors), carefully chosen error distributions, and tight security parameters.

Keywords: key exchange, lattice-based cryptography, LWE

Reference

Joppe Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, Douglas Stebila. Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE. In Proc. 23rd ACM Conference on Computer and Communications Security (CCS) 2016, pp. 1006-1018. ACM, October 2016. © The authors.

Download

Code

• C implementation of the learning with errors key exchange protocol: GitHub

Presentations

• 2017-04-30: TLS:DIV workshop (collocated with EuroS&P / Eurocrypt 2017). (PDF slides)
• 2016-09-21: 4th ETSI/IQC Workshop on Quantum-Safe Cryptography, Toronto, Canada. (PDF slides)

BibTeX

@inproceedings{CCS:BCDMNNRS16,
 	Author = {Joppe Bos and Craig Costello and L{\' e}o Ducas and Ilya Mironov and Michael Naehrig and Valeria Nikolaenko and Ananth Raghunathan and Douglas Stebila},
 	Booktitle = {Proc. 23rd ACM Conference on Computer and Communications Security (CCS) 2016},
 	Doi = {10.1145/2976749.2978425},
 	Month = {October},
 	Publisher = {ACM},
 	Title = {Frodo: Take off the ring! Practical, quantum-secure key exchange from {LWE}},
 	Year = {2016}
 }

Funding

• Australian Research Council (ARC) Discovery Project grant DP130104304
• Natural Sciences and Engineering Research Council (NSERC) of Canada Discovery grant
• Commission of the European Communities through the Horizon 2020 program under project number 645622 (PQCRYPTO)