Jintai Ding – University of Cincinnati

Public key cryptosystems (PKC) are a critical part of the foundation of modern communication systems, in particular, the Internet. However Shor’s algorithm shows that the existing PKC like Diffie-Hellmann key exchange, RSA and ECC can be broken by a quantum computer. To prepare for the coming age of quantum computing, we need to build new public key cryptosystems that can resist quantum computer attacks. In this lecture, we present a practical and provably secure (authenticated) key exchange protocol based on the learning with errors problems, which is conceptually simple and has strong provable security properties. This new construction was established in 2011-2012. These protocols are indeed practical. We will explain that all the existing LWE based key exchanges are variants of this fundamental design. In addition, we will explain how to use the signal function invented for KE for authentication schemes.