Paper 2023/1380

Tighter Security for Generic Authenticated Key Exchange in the QROM

Jiaxin Pan, Norwegian University of Science and Technology
Benedikt Wagner, Helmholtz Center for Information Security
Runzhi Zeng, Norwegian University of Science and Technology

We give a tighter security proof for authenticated key exchange (AKE) protocols that are generically constructed from key encapsulation mechanisms (KEMs) in the quantum random oracle model (QROM). Previous works (Hövelmanns et al., PKC 2020) gave reductions for such a KEM-based AKE protocol in the QROM to the underlying primitives with square-root loss and a security loss in the number of users and total sessions. Our proof is much tighter and does not have square-root loss. Namely, it only loses a factor depending on the number of users, not on the number of sessions. Our main enabler is a new variant of lossy encryption which we call parameter lossy encryption. In this variant, there are not only lossy public keys but also lossy system parameters. This allows us to embed a computational assumption into the system parameters, and the lossy public keys are statistically close to the normal public keys. Combining with the Fujisaki-Okamoto transformation, we obtain the first tightly IND-CCA secure KEM in the QROM in a multi-user (without corruption), multi-challenge setting. Finally, we show that a multi-user, multi-challenge KEM implies a square-root-tight and session-tight AKE protocol in the QROM. By implementing the parameter lossy encryption tightly from lattices, we obtain the first square-root-tight and session-tight AKE from lattices in the QROM.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Authenticated key exchangekey encapsulation mechanismquantum random oracle modeltight securitylattices
Contact author(s)
jiaxin pan @ ntnu no
benedikt wagner @ cispa de
runzhi zeng @ ntnu no
2023-09-18: approved
2023-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jiaxin Pan and Benedikt Wagner and Runzhi Zeng},
      title = {Tighter Security for Generic Authenticated Key Exchange in the QROM},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1380},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.