International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Authenticated Key Exchange and Key Encapsulation Without Random Oracles

Tatsuaki Okamoto
Search ePrint
Search Google
Abstract: This paper presents a new paradigm to realize cryptographic primitives such as authenticated key exchange and key encapsulation without random oracles under three assumptions: the decisional Diffie-Hellman (DDH) assumption, target collision resistant (TCR) hash functions and a class of pseudo-random functions (PRFs), {\pi}PRFs, PRFs with pairwise-independent random sources. We propose a (PKI-based) two-pass authenticated key exchange (AKE) protocol that is comparably as efficient as the existing most efficient protocols like MQV and that is secure without random oracles (under these assumptions). Our protocol is shown to be secure in the (currently) strongest security definition, the extended Canetti-Krawczyk (eCK) security definition introduced by LaMacchia, Lauter and Mityagin. We also show that a variant of the Kurosawa-Desmedt key encapsulation mechanism (KEM) using a {\pi}PRF is CCA-secure. This scheme is secure in a stronger security notion, the chosen public-key and ciphertext attack (CPCA) security, with using generalized TCR (GTCR) hash functions. The proposed schemes in this paper are redundancy-free (or validity-check-free) and the implication is that combining them with redundancy-free symmetric encryption (DEM) will yield redundancy-free (e.g., MAC-free) CCA-secure hybrid encryption.
  title={Authenticated Key Exchange and Key Encapsulation Without Random Oracles},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / key exchange, public-key cryptography, key encapsulation,  pseudo-random function},
  note={This is a revised and full version of the extended abstract published in the proceedings of Asiacrypt 2007 as an invited talk manuscript. 13865 received 18 Dec 2007},
  author={Tatsuaki Okamoto},