Tighter Security for Generic Authenticated Key Exchange in the QROM

Jiaxin Pan; Benedikt Wagner; Runzhi Zeng

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in ASIACRYPT 2023
Keywords: Authenticated key exchange key encapsulation mechanism quantum random oracle model tight security lattices
Contact author(s): jiaxin pan @ ntnu no
benedikt wagner @ cispa de
runzhi zeng @ ntnu no
History: 2023-09-18: approved; 2023-09-14: received; See all versions
Short URL: https://ia.cr/2023/1380
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1380,
      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{https://eprint.iacr.org/2023/1380}},
      url = {https://eprint.iacr.org/2023/1380}
}