Generic Composition: From Classical to Quantum Security

Nathalie Lang; Jannis Leuther; Stefan Lucks

Paper 2025/387

Generic Composition: From Classical to Quantum Security

Nathalie Lang

, Bauhaus University, Weimar

Jannis Leuther

, Bauhaus University, Weimar

Stefan Lucks

, Bauhaus University, Weimar

Abstract

Authenticated encryption (AE) provides both authenticity and privacy. We investigate the security of generically composing unauthenticated encryption and authentication in a quantum setting where adversarial queries as well as the responses to those may be in superposition. This extends the work from Bellare and Namprempre in 2000, who considered the classical setting. First, we disprove a claim made by Soukharev et al. at PQCrypto 2016. Namely, we show that a chosen-plaintext (IND-qCPA) secure symmetric encryption scheme and a plus-one unforgeable message authentication code (MAC) exist, such that their generic (Encrypt-then-MAC) composition fails to achieve chosen-ciphertext (IND-qCCA) security. On the other hand, we show that a stronger MAC (namely a qPRF) suffices for the composed scheme to be IND-qCCA secure. Furthermore, the IND-qCCA notion proposed in related work assumes a randomized encryption operation. We propose to replace the randomness by a nonce, and to authenticate associated data, in addition to the message.

Note: Major Revision on Nov. 7, 2025

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: Post-Quantum Authenticated Encryption Generic Composition
Contact author(s): nathalie lang @ posteo de
jannis leuther @ uni-weimar de
stefan lucks @ uni-weimar de
History: 2025-11-07: revised; 2025-02-28: received; See all versions
Short URL: https://ia.cr/2025/387
License: CC BY

BibTeX

@misc{cryptoeprint:2025/387,
      author = {Nathalie Lang and Jannis Leuther and Stefan Lucks},
      title = {Generic Composition: From Classical to Quantum Security},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/387},
      year = {2025},
      url = {https://eprint.iacr.org/2025/387}
}