Paper 2026/1312

Post-Quantum Security of Tweakable Key-Alternating Feistel Ciphers in the Multi-Key Setting

Abstract

In this paper, we prove the post-quantum security of the Tweakable Key-Alternating Feistel cipher (TKAF) with a public random function in the Q1 model, under the assumption that the adversary is given quantum access to the internal primitive. Specifically, our target is the TKAF studied in the classical setting by Yan et al. (ACNS 2020), where the tweak is injected into the round-key XOR via a hash function of $\epsilon$-AXU family. Our proof draws on the post-quantum security proof for the (non-tweakable) key-alternating Feistel ciphers by Basak et al. (ASIACRYPT 2025), and adapts it to the tweakable setting and further to the multi-key setting, where an adversary can access multiple classical oracles. As a result, we prove that the 3-round TKAF is post-quantum TPRP-secure and the 4-round TKAF is post-quantum STPRP-secure. Specifically, under the assumption that the adversary is given classical access to $\ell$ independently specified oracles, at least $\mathrm{\Omega} (2^{n/3}/\ell^{2/3})$ classical and quantum queries or $\mathrm{\Omega}(\epsilon^{-1/2})$ classical queries are required to break the post-quantum TPRP security of the 3-round TKAF and to break the post-quantum STPRP security of the 4-round TKAF.