Paper 2014/589

Authenticated Key Exchange from Ideal Lattices

Jiang Zhang and Zhenfeng Zhang and Jintai Ding and Michael Snook

Abstract

Authenticated key exchange (AKE) protocols, such as IKE and SSL/TLS, have been widely used to ensure secure com- munication over the Internet. We present in this paper a practical and provably secure AKE protocol from ideal lat- tices, which is conceptually simple and has similarities to the Diffie-Hellman based protocols such as HMQV (CRYP- TO 2005) and OAKE (CCS 2013). Our protocol does not rely on other cryptographic primitives—in particular, it does not use signatures—simplifying the protocol and resting the security solely on the hardness of the ring learning with er- rors (RLWE) problem. The security is proven in a version of the Bellare-Rogaway model, with enhancements to cap- ture weak Perfect Forward Secrecy. We also present concrete choices of parameters for different security levels. A proof- of-concept implementation shows our protocol is a practical candidate post-quantum key exchange protocol.