尤启迪, 钱 新, 周 旋, 袁 野, 吴兆阳

1. 清华大学 计算机科学与技术系, 北京100084

2. 北京卫星信息工程研究所, 北京100086

1 引言

广义Feistel 结构是用来设计分组密码算法的基本结构之一, 该类结构继承了Feistel 结构[1]加解密一致的特点, 同时使得轮函数设计更加灵活、轻量. 在1989 年美密会上, 郑等人[2]总结了三类广义Feistel 结构, 并记为Type-1、Type-2 和Type-3 型广义Feistel. 后来, 其他类型的广义Feistel 或者非平衡的Feistel 结构被提出[3-5]. 基于广义Feistel 结构设计的密码算法有很多,包括分组密码CAST-256[6]、CLEFIA[7]、SMS4[8], 密码置换函数Simpira[9], 以及哈希函数MD5[10]和SHA-1[11]等. 近来, 广义Feistel 结构还被用于设计适用于多方安全计算、同态加密等场景的分组密码算法[12].

随着量子计算、量子理论的发展迅速, 量子信息科学的发展为密码学的发展也带来了一定挑战.Grover[13]提出了一种无序数据库的标准搜索算法, 以Grover 算法为代表的量子搜索算法以及推广算法的计算复杂度是经典算法的平方加速, 可用于加速密钥的搜索, 对所有密码产生了一定威胁; Shor 算法[14,15]可用于分解大整数、求解离散对数, 其计算复杂度是对经典算法的指数加速, 可用于相关公钥密码中的数学难题的加速求解,对RSA、ECC 等为代表的公钥密码产生了一定威胁. Kuwakado 和Morii[16]首先利用Simon 算法[17]构造了3 轮Feistel 结构的多项式时间量子区分器. 随后, Even-Mansour 算法的量子密钥恢复攻击[18]、各种MAC 算法的伪造攻击[19]、AEZ 的量子破解[20]、FX 结构的密钥恢复攻击[21], 以及Feistel 结构的量子密钥恢复攻击[22-26]和量子安全性证明[27]等相继被提出. 广义Feistel的结构的量子分析首先由董晓阳等[28]提……