Cryptology ePrint Archive: Report 2015/138

A Practical Key Exchange for the Internet using Lattice Cryptography

Vikram Singh

Abstract: In [21], Peikert presents an efficient and provably secure set of lower level primitives for practical post-quantum cryptography. These primitives also give the first lattice-based scheme to provide perfect forward secrecy, and thus represent a major advancement in providing the same sort of security guarantees that are now expected for modern internet traffic protection. However, the presentation in [21] might prove a bit daunting for the slightly less mathematical reader. Here we provide what we hope will be a clear and self-contained exposition of how the algorithm can be implemented, along with sample code and some initial analysis for potential parameter sizes.

We focus on the simpler case, as chosen by Bos et al in [1], of cyclotomic rings whose degree is a power of two. We describe the necessary arithmetic setup and choices regarding error sampling, and give a possibly cleaner mechanism for reconciliation of the shared secrets. Then we present Peikert's Diffe-Hellman-like key exchange algorithms along with security, correctness and implementation analysis. We demonstrate parameter choices that outperform [1] by a factor of up to 13 for equivalent security.

Category / Keywords: Lattice, Ring-LWE, Ring Learning With Errors, Key Exchange, IKE, TLS

Date: received 19 Feb 2015, last revised 22 Oct 2015

Contact author: vs77814 at gmail com

Available format(s): PDF | BibTeX Citation

Note: Added performance timings from benchmarking code.

Version: 20151022:132001 (All versions of this report)

Short URL: ia.cr/2015/138

Discussion forum: Show discussion | Start new discussion