Key exchange protocol enables two users to exchange keys in untrusted channels without sharing secret materials in advance.
The first and celebrated key exchange protocol is the Diffie-Hellman key exchange protocol which is also a fundamental construction in public key cryptography. It is simple and elegant, and, after its invention, countless applications based on Diffie-Hellman key exchange protocol or the Diffie-Hellman problem were proposed. The Diffie-Hellman protocol offers an alternative algorithm to RSA for cryptographic key exchange. The Diffie-Hellman protocol generates more secure session keys that can't be recovered simply by knowing the user's private key, a protocol security feature called forward security.
The motivation of this talk is to build simple Diffie-Hellman like key exchange protocols based on lattices.
Lattice-based public key cryptography has become a promising potential alternative to public key cryptography based on traditional number theory assumptions. One building block of lattice-based cryptography, especially in encryption, is the learning with errors (LWE) problem. After the introduction of LWE problem by Regev. Many lattice-based primitives based on LWE have been discovered. What motivates the work in this talk is to try to build a simple key exchange protocol using the basic idea of Diffie-Hellman protocol
but based on the LWE and RLWE problem. As far as we know
there is not yet until very recently any provably secure key exchange protocols based on the LWE problem as a direct generalization of the Diffie-Hellman key exchange protocol, which is elegant in terms of its simplicity. Our work was finished in 2012.
Recent works on LWE-based Key exchange protocols including new hope used by Google Chrome Canary are all variants of our protocol with minor modifications but some with significant contributions in concrete implementations.
The key idea behind our new construction is the associative law of matrix multiplication (AxB)xC= Ax(BxC). Surely in order to make the system provably secure, we need to introduce the small errors to achieve our goal. The main contribution of our work is to use this simple
idea to build a simple and provably secure key exchange scheme. The idea of such an "noise" or "approximate" KE appeared long time ago like the work of Buchmann and Williams and recently the work using coding theory. A new fundamental contributions of ours, which is something very different from the DH KE is that we developed a new idea of "signal functions" as a additional tool needed to round the approximate value to a shared secret without affecting the security.
Furthermore, we extend our construction further based on the RLWE problem. Our construction is a significant additional step in showing how versatile the LWE assumption can be.