International Association
for Cryptologic Research

We study the post-quantum security of authenticated encryption (AE)schemes, designed with classical security in the mind. Under superposition attacks, many CBC-MAC variants have been broken, and AE modes employing those variants, such as EAX and GCM, thus fail at authenticity. As we show, the same modes are IND-qCPA insecure, i.e., fail to provide privacy under superposition attacks. However, a constrained version of GCM is IND-qCPA secure, and a nonce-based variant of the CBC-MAC is secure under superposition queries. Further, the combination of classical authenticity and classical chosen-plaintext privacy thwarts attacks with superposition chosen-ciphertext and classical chosen-plaintext queries -a security notion that we refer to as IND-qdCCA. And nonce-based key derivation allows to generically turn an IND-qdCCA secure scheme into an IND-qCCA secure scheme.