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

Quantum Q1 Security Proof for FX Key-Length Extension Construction

FX构造FX_(k,k′)[E]=E_(k)(x⊕vk′)⊕k′将密钥长度为κ比特的分组密码E:{0,1}^(κ)×{0,1}^(n)→{0,1}^(n)转化为密钥长度为κ+n比特的分组密码,是最高效的密钥长度扩展方法.基于对所谓Even-Mansour构造的前期研究(EUROCRYPT 2022),Alagic等(Eprint 2022)为FX构造的可调变体提供了一个量子Q1模型中的安全性证明.然而,如Alagic等所承认,针对(原始版)FX构造,他们的证明方法未能导出令人满意的安全界.本文提出了对Alagic等证明的修补措施,从而得以证明所期望的(κ+n)/3比特紧致量子Q1安全界.本文的修补主要是改动了Alagic等证明中的一处中间值的分布,从而避免了导致更差安全界的某些不良事件.这个改动要求对Alagic等的“再采样”引理进行“依赖上下文的”扩展,这在概念上可能有一定创新.

The FX construction FX_(k,k′)[E]=E_(k)(x⊕k′)⊕k′transforms a blockcipher E:{0,1}^(κ)×{0,1}^(n)→{0,1}^(n)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.