Post-Quantum Key Exchange for the Internet and the Open Quantum Safe Project
Douglas Stebila, McMaster University
Most public key cryptography algorithms used on the Internet are based on mathematical problems which could be broken by large-scale quantum computers. This motivates the field of post-quantum cryptography, which aims to construct public key cryptosystems that are believed to be secure even against quantum computers. Since a future quantum computer could retroactively break the confidentiality of today's communications, it is important to begin transitioning public key encryption and key exchange to quantum-resistant algorithms. In this talk, I will discuss two quantum-resistant key exchange algorithms based on hard problems on lattices. The first, called BCNS15, is based on the ring learning with errors (ring-LWE) problem, and can achieve a shared secret key with 8 KiB of communication. The second, called Frodo, is based on the learning with errors (LWE) problem. Using the LWE problem avoids the additional "ideal lattice" structure present in the ring-LWE problem, potentially making LWE a more conservative security choice, but this comes at larger communication: Frodo requires 22 KiB of communication to establish a shared secret. Despite having larger communications, both BCNS15 and Frodo are quite fast, with operations taking around 1-2ms per party. I will explain the basic mathematics of these protocols, and our results on the performance of these protocols and their integration into the Transport Layer Security (TLS) protocol. I will also introduce the Open Quantum Safe project, an open-source software project designed for evaluating post-quantum cryptography candidates and prototyping their use in applications and protocols such as TLS.