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

What it is

Rentaro Shiba and Tetsu Iwata (Nagoya University) give a new security bound for the FX construction, the Kilian–Rogaway generalization of DESX. It was posted as IACR ePrint 2026/2614 on 23 October 2026 and is a preprint, not yet peer reviewed. It tightens their ToSC 2026 result, which was approximately 2^((n+κ−log₂μ)/3) total classical and quantum oracle queries. Here n is the block size, κ the internal key length, and μ ≤ 2^κ the number of independently keyed instances. The new bound drops the log₂μ term and is approximately 2^((n+κ)/3).

Preconditions / Affected

The result holds only under these conditions:

• The quantum ideal cipher model, which treats the block cipher as ideal and does not analyze a specific cipher.
• Adversaries that compute quantumly but make only classical queries to the keyed construction. The abstract presents this as the setting in which FX can help.
• Parameters in the range 1 ≤ κ ≤ 2n, for every μ ≥ 1.

Caveats

The abstract says the offline Simon's algorithm attack can target a single keyed instance and matches the bound in the exponent. So adding more keyed instances does not lower the exponent of the query cost to break FX in this parameter range. The abstract does not cover adversaries who make quantum queries to the keyed construction itself, or any concrete cipher such as AES or DES. It gives no implementation guidance or recommended parameters.