A Practical Key Exchange for the Internet using Lattice Cryptography Vikram Singh∗

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 regard-ing error sampling, and give a possibly cleaner mechanism for reconciliation of the shared secrets. Then we present Peikert’s Diffie-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