Cryptology ePrint Archive: Report 2018/928

Generic Authenticated Key Exchange in the Quantum Random Oracle Model

Kathrin Hövelmanns and Eike Kiltz and Sven Schäge and Dominique Unruh

Abstract: We propose FO-AKE a generic construction of two-message authenticated key exchange (AKE) from any passively secure public key encryption (PKE) in the quantum random oracle model (QROM). Whereas previous AKE constructions relied on a Diffie-Hellman key exchange or required the underlying PKE scheme to be perfectly correct, our transformation allows arbitrary PKE schemes with non-perfect correctness. Furthermore, we avoid the use of (quantum-secure) digital signature schemes which are considerably less efficient than their PKE counterparts. As a consequence, we can instantiate our AKE transformation with any of the submissions to the recent NIST post-quantum competition, e.g., ones based on codes and lattices.

FO-AKE can be seen as a generalization of the well known Fujisaki-Okamoto transformation (for building actively secure PKE from passively secure PKE) to the AKE setting. Therefore, as a helper result, we also provide a security proof for the Fujisaki-Okamoto transformation in the QROM for PKE with non-perfect correctness. Our reduction fixes several gaps in a previous proof (CRYPTO 2018), is tighter, and tolerates a larger correctness error.

Category / Keywords: public-key cryptography / Authenticated key exchange, quantum random oracle model, NIST, Fujisaki- Okamoto.

Original Publication (with minor differences): IACR-PKC-2020

Date: received 28 Sep 2018, last revised 29 Jan 2020

Contact author: Kathrin Hoevelmanns at ruhr-uni-bochum de, sschaege at googlemail com, eike kiltz at rub de, unruh at ut ee

Available format(s): PDF | BibTeX Citation

Note: Added missing acknowledgments

Version: 20200129:142809 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]