Paper 2025/387 Original: eprint.iacr.org/2025/387 ↗

Generic Composition: From Classical to Quantum Security

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.