Paper 2015/138

A Practical Key Exchange for the Internet using Lattice Cryptography

Vikram Singh

Abstract

In 2014, Peikert presented an efficient and provably secure set of lower level primitives for practical post-quantum cryptography. These primitives also gave 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 might have proved 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, Costello, Naehrig and Stebila in 2014, 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 Diffie-Hellman-like key exchange algorithms along with security, correctness and implementation analysis. We demonstrate parameter choices that outperform Bos et al by a factor of up to 13 for equivalent security.

Note: Updated GitHub repository URL