Paper 2012/211

Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices

Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa, and Kazuki Yoneyama

Abstract

An unresolved problem in research on authenticated key exchange (AKE) is to construct a secure protocol against advanced attacks such as key compromise impersonation and maximal exposure attacks without relying on random oracles. HMQV, a state of the art AKE protocol, achieves both efficiency and the strong security proposed by Krawczyk (we call it the CK+ model), which includes resistance to advanced attacks. However, the security proof is given under the random oracle model. We propose a generic construction of AKE from a key encapsulation mechanism (KEM). The construction is based on a chosen-ciphertext secure KEM, and the resultant AKE protocol is CK+ secure in the standard model. The construction gives the first CK+ secure AKE protocols based on the hardness of integer factorization problem, code-based problems, or learning problems with errors. In addition, instantiations under the Diffie-Hellman assumption or its variant can be proved to have strong security without non-standard assumptions such as $\pi$PRF and KEA1. Furthermore, we extend the CK+ model to identity-based (called the id-CK+ model), and propose a generic construction of identity-based AKE (ID-AKE) based on identity-based KEM, which satisfies id-CK+ security. The construction leads first strongly secure ID-AKE protocols under the hardness of integer factorization problem, or learning problems with errors.

Note: A result for the identity-based setting is added.