Post-Quantum Security of Tweakable Even-Mansour, and Applications

The tweakable Even-Mansour construction yields a tweakable block cipher from a public random permutation. We prove post-quantum security of tweakable Even-Mansour when attackers have quantum access to the  random permutation but only classical access to the secretly-keyed construction, the relevant setting for most real-world applications. We then use our results to prove post-quantum security—in the same model—of the symmetric-key schemes Chaskey (an ISO-standardized MAC), Elephant (an AEAD finalist of NIST's lightweight cryptography standardization effort), and a variant of Minalpher (an AEAD second-round candidate of the CAESAR competition).