Quantum-Resistant Authenticated Encryption Variants of GCM

Common authenticated encryption schemes are generally believed to remain secure in the post-quantum setting where adversaries with local quantum power interact classically with the users. This is apart from a square root loss in the security bound due to Grover's algorithm. This changes dramatically when one switches to a fully quantum setting where the adversary is allowed to interact with the users in superposition, called IND-qCCA security. Here, many well-known schemes become completely insecure, including the widely deplyoed Galois/Counter mode (GCM). Here we propose a modification to GCM and to its counterpart GCM-SIV that resurrects IND-qCCA security in the quantum setting for nonce-respecting adversaries. The key observation is to replace the universal hash functions GHASH and PolyVal in GCM and GCM-SIV by pairwise-independent versions.