FX 密钥长度扩展构造量子 Q1 安全性证明

The FX construction FX_k,k′[E](x) = E_k (x k^′) k^′ transforms a blockcipher E : {0, 1}^κ×{0, 1}ⁿ → {0, 1}ⁿ with κ-bit keys into a blockcipher with (κ+n)-bit keys. It is the most efficient key-length extension method. Built on an earlier work on the so-called Even-Mansour construction (EUROCRYPT 2022), Alagic et al. (Eprint 2022) provided a post-quantum security proof for a tweakable variant of the FX construction. Unfortunately, as admitted by the authors, their proof approach did not yield satisfactory bounds on the (original) FX. This paper presents a patch to their proof, which yields the desired (κ + n)/3-bit tight post-quantum security bound. The proposed patch mainly revises the distribution of an intermediate value in Alagic et al.’s proof, and this avoids certain bad events that led to worse bounds. This path requires a context-dependent extension of Alagic et al.’s resampling lemma, which may be of some conceptual novelty.