Paper 2026/2614

Tight Post-Quantum Multi-Key Security of the FX Construction

Abstract

The FX construction (FX) is one of the simplest key-length extension schemes for block ciphers, introduced by Kilian and Rogaway as a generalization of DESX. By extending the key length without modifying the underlying block cipher, FX can improve security against adversaries that perform quantum computation but are restricted to classical queries to the keyed construction. Recently, Shiba and Iwata showed in their ToSC 2026 paper that FX with an $n$-bit block and a $\kappa$-bit internal key is secure up to approximately $2^{(n+\kappa-\log_2\mu)/3}$ total classical and quantum oracle queries in the quantum ideal cipher model, where $\mu\leq2^\kappa$ is the number of independently keyed instances. In this paper, we improve this bound to approximately $2^{(n+\kappa)/3}$ total oracle queries in the same model against fully adaptive adversaries, for every $\mu\geq1$ and $1\leq\kappa\leq2n$. The known attack based on the offline Simon's algorithm can target a single keyed instance and matches our bound in the exponent. Thus, the exponent of the total query complexity required to break FX is independent of the number of keyed instances in this parameter regime.