Multi-Key Security in the Quantum World: Revisiting Tweakable Even-Mansour and FX
Rentaro Shiba, Tetsu Iwata
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, Ω(2Κ/3) classical and quantum queries are needed, regardless of the number of target Κ-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 (Κ + n)-bit secret key in the Q1 model, Ω(2(Κ+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, Ω(2(Κ + n - u)/3) classical and quantum queries are needed, when 2u ( 2Κ) independent keys are in use.
IACR Transactions on Symmetric Cryptology•Jun 11, 2026•2 citations