Paper 2026/382

Multi-Key Security in the Quantum World: Revisiting Tweakable Even-Mansour and FX

Abstract

In this paper, we prove the security of symmetric-key constructions in an adversary model called the Q1MK model, which combines the Q1 model, where the adversary makes classical online queries and quantum offline queries, and the multi-key (multi-user) setting. Specifically, under this model, we prove the security of two symmetric-key constructions: the tweakable Even-Mansour cipher (TEM) and the FX construction (FX), as starting points for understanding the post-quantum security of symmetric-key constructions in this adversary model. Our security proofs are based on the hybrid argument technique introduced by Alagic et al. at EUROCRYPT~2022. First, we prove that in order to break TEM in the Q1MK model, $\Omega(2^{\kappa/3})$ classical and quantum queries are needed, regardless of the number of target $\kappa$-bit keys. Then, before turning to the Q1MK security analysis of FX, we revisit the security proof of FX in the standard Q1 model proposed in version 20230317:200508 of ePrint~2022/1097 and tighten it. By the modified proof, we show that in order to break FX with $(\kappa + n)$-bit secret key in the Q1 model, $\Omega(2^{(\kappa+n)/3})$ classical and quantum queries are needed. We then apply this proof to the Q1MK setting, and we show that in order to break FX in the Q1MK model, $\Omega(2^{(\kappa + n - u)/3})$ classical and quantum queries are needed, when $2^u$ ($\le 2^{\kappa}$) independent keys are in use.