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$\times$, 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.6$\times$, and (even under heavy load) server throughput only decreases by factors of 1.5$\times$ and 1.2$\times$ 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.
Category / Keywords: public-key cryptography / key exchange, lattice-based cryptography, LWE Date: received 27 Jun 2016, last revised 27 Jun 2016 Contact author: mironov at google com Available format(s): PDF | BibTeX Citation Version: 20160628:211043 (All versions of this report) Short URL: ia.cr/2016/659 Discussion forum: Show discussion | Start new discussion