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

Quantum Q1 Security Proof for FX Key-Length Extension Construction

作　　者：郭淳 黄安静 郁昱[4,5] GUO Chun;HUANG An-Jing;YU Yu(School of Cyber Science and Technology,Shandong University,Qingdao 266237,China;Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education,Shandong University,Qingdao 266237,China;CAS Quantum Network Co.Ltd.,Shanghai 201315,China;Department of Computer Science and Engineering,Shanghai Jiao Tong University,Shanghai 200240,China;State Key Laboratory of Cryptology,Beijing 100878,China)

机构地区：[1]山东大学网络空间安全学院,青岛266237 [2]密码技术与信息安全教育部重点实验室,青岛266237 [3]国科量子通信网络有限公司,上海201315 [4]上海交通大学计算机科学与工程系,上海200240 [5]密码科学技术全国重点实验室,北京100878

出　　处：《密码学报（中英文）》2024年第5期1139-1151,共13页Journal of Cryptologic Research

基　　金：国家自然科学基金(62002202);山东省自然科学基金重大基础研究项目(ZR202010220025)。

摘　　要：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.

关 键 词：后量子安全性 可证明安全 密钥长度扩展 FX构造 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]