GMM型高维输出严格几乎最优弹性密码函数构造_张卫国.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(2):246263密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618GMM 型高维输出严格几乎最优弹性密码函数构造*张卫国1,胡姚达1,董雪雯21.西安电子科技大学 综合业务网理论及关键技术实验室,西安 7100712.武汉船舶通信研究所,武汉 430200通信作者:胡姚达,E-mail:hyd_摘要:在流密码的设计中,非线性组合部件应选用具有高非线性度的弹性密码函数.高非线性度可以保障密码系统不易遭受最佳仿射逼近攻击,而弹性可以使系统能够抵抗相关攻击.使用高维向量输出的弹性函数,可以增加密码系统的加解密速度,但难以提高函数的非线性度.本文基于三类向量阵列,给出两个 GMM 型弹性函数的构造方案.所构造的函数具有严格几乎最优非线性度和较高的向量输出维数,很好地实现了非线性度、弹性阶和向量输出维数三者之间的折中.采用本文的函数构造方案,对某些给定的 n,m,t,可以构造出一系列具有目前已知最高非线性度的(n,m,t)弹性函数.关键词:对称密码;多输出布尔函数;弹性;非线性度;不相交码中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000591中文引用格式:张卫国,胡姚达,董雪雯.GMM 型高维输出严格几乎最优弹性密码函数构造J.密码学报,2023,10(2):246263.DOI:10.13868/ki.jcr.000591英文引用格式:ZHANG W G,HU Y D,DONG X W.Constructions of GMM type strictly almost optimalresilient vectorial Boolean functions with high-dimensionJ.Journal of Cryptologic Research,2023,10(2):246263.DOI:10.13868/ki.jcr.000591Constructions of GMM Type Strictly almost Optimal ResilientVectorial Boolean Functions with High-dimensionZHANG Wei-Guo1,HU Yao-Da1,DONG Xue-Wen21.State Key Laboratory of Integrated Services Networks,Xidian University,Xian 710071,China2.Wuhan Marine Communication Research Institute,Wuhan 430200,ChinaCorresponding author:HU Yao-Da,E-mail:hyd_Abstract:In the design of a stream ciphers,the algebraic form of the nonlinear combining functionshould be resilient with high nonlinearity.High nonlinearity ensures the resistance of the cipher againstbest affine approximation attacks,while resiliency offers resistance against correlation attacks.By usingvectorial resilient functions as the combining functions,the speed of the encryption and decryptionof the ciphers can be increased,and yet it is difficult to improve the nonlinearity of the resilientfunctions.This paper presents two constructions of generalized Maiorana-McFarland(GMM)typestrictly almost optimal resilient vectorial Boolean functions with high-dimension based on three kindsof vector arrays.A good tradeoffis gained among the parameters of nonlinearity,resiliency order and*基金项目:国家自然科学基金(61972303,62272360)Foundation:National Natural Science Foundation of China(61972303,62272360)收稿日期:2022-09-26定稿日期:2023-01-30张卫国 等:GMM 型高维输出严格几乎最优弹性密码函数构造247vector-output dimension.It is shown that(n,m,t)resilient functions with best known nonlinearitycan be constructed for some values of n,m and t.Key words:symmetric cipher;vectorial Boolean functions;resiliency;nonlinearity;disjoint linearcodes1引言对称密码系统的核心非线性逻辑结构可抽象为代数上的布尔函数,常称这种场景下的布尔函数为密码函数.布尔函数的密码性质决定着对称密码系统的安全性,其代数结构的复杂程度也影响着系统实现的简易性.对称密码系统分为流密码系统和分组密码系统.在分组密码系统中,主要的非线性结构被称为 S 盒(substitution box),可看作是多输出布尔函数.多输出布尔函数还可用于流密码系统中,对提高系统的加解密速度具有显著效果.用于流密码系统中的布尔函数应具有多种密码学性质,以抵抗现有各种主流攻击:Berlekamp-Massey算法攻击1,2、线性攻击3,4、相关攻击5,6、(快速)代数攻击7,8等.为了抵抗这些攻击,要求布尔函数具有高代数次数、高非线性度、适当的弹性阶、高(快速)代数免疫阶等密码性质.实现这些性质的优化折中是一个困难的问题,尤其是在弹性和非线性度之间存在很强的制约关系.弹性布尔函数的非线性度的紧上界是尚未解决的公开难题.若在多输出布尔函数上综合考虑弹性阶、非线性度和输出维数等指标,问题将变得更加复杂.1985 年,Chor 等人9和 Bennett 等人10分别独立地提出弹性函数和(N,J,K)-函数的概念.这两个概念是等价的,分别是在比特提取问题11、容错分布式计算、减少信道窃听者信息、量子密钥分发12等应用背景下被提出和应用的.在流密码领域,Siegenthaler13于 1984 年提出相关免疫函数的概念.相关免疫函数被提出时是定义在 Fn2上的单输出布尔函数,这一概念后来被推广到多输出情形.当提到平衡(多输出)相关免疫函数时,它和弹性函数是一回事,如今一般采用弹性函数这一概念.其具体定义如下:设 F:Fn2|Fm2,其中 n m 1.对 X Fn2,固定 X 中任意 t 个变元,若 Fm2中的向量在(n,m)函数F(X)的 2nt个输出函数值中出现的次数都相同,则称 F 是 t 阶弹性的,或(n,m,t)弹性函数.最早被发现的(n,m,t)弹性函数,m 2,是线性弹性函数,可由 n,m,t+1 线性码构造而得.文献 9,10 中证明了(n,m,t)弹性函数的存在性和 n,m,t+1 线性码的存在性是等价问题,并猜想若存在非线性(n,m,t)弹性函数,则必存在同一参数的线性弹性函数.1995 年,Stinson 和 Massey14证明了这一猜想是错误的.例如,当 r 3 为奇数,存在非线性(2r+1,2r+1 2r 2,5)弹性函数,但不存在同样参数的线性弹性函数;还发现存在(64,12,27)弹性函数,但它也不是线性的.文献 14 中的结论很重要,但并没有考虑弹性函数的非线性度.1997 年,Zhang 和 Zheng15较早考虑了高非线性度弹性函数的设计问题.他们证明了把一个(n,m,t)弹性函数 F 和 Fm2上的置换函数 G 进行复合运算,所得函数 P=G F 也是一个(n,m,t)弹性函数.当 F 是线性(n,m,t)弹性函数时,上述结论当然也成立.此时,P 和 G 的代数次数相同(总可达到 m1),P 的非线性度 NP是 G 的非线性度 NG的 2nm倍,即 NP=2nmNG.为了使 P 的非线性度尽可能高,我们选 G 为 Fm2上非线性度是 2m1 2m/2的置换函数.此时,NP=2n1 2nm/2,可以看出 NP随着 m 的增大而增大.由于在 m 3 时 Fm2上才有非线性置换,可知在 t 1 时,2n2 NP 2n1 2(n+1)/2.2000 年,Johansson 和 Pasalic16,17借助 u,m,d 不相交码构造出代数次数不超过 nu+1,非线性度是 2n1 2nu的 Maiorana-McFarland(MM)型(n,m,d 1)弹性函数,其中 n u m 2.这一构造方法可以实现非线性度和弹性的较好折中,但要依赖于能找到的 u,m,d 不相交码的数量.文献 16,17 中没能解决不相交码的构造问题,而是建议用搜索的方式,这在 u 和 m 相对较大时是不可行的.2004 年,Niederreiter 和 Xing18基于代数函数域构造不相交码,得到 Fq上 u,m,d 不相交码的一个下界.这种办法得到的 u,m,d 不相交码很少,例如,只得到 24 个二元 18,4,6 不相交码.2005年,Charpin 和 Pasalic19在射影空间上构造出 u,m,d 不相交码,这种方法只在 m|u 时可行.例如,可以构造出 249 个 12,4,3 不相交码,8 个 8,4,3 不相交码.进一步可由这两组不相交码“拼接”出248Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.20232498=1992 个 20,8,3 不相交码,按照文献 17 中的方法就可以得到非线性度是 237219的(38,8,2)弹性函数.2001 年,鉴于当时还不能构造足够多的不相交码实现弹性和非线性度之间的优化折中,Pasalic 和Maitra20,21回避了这一问题,只采用单个 u,m,t+1 线性码通过 MM 构造法得到非线性度是 2n12(n+um1)/2的(n,m,t)弹性函数,这里要求 n u+3m.例如,可以构造出非线性度是 235 218的(36,8,1)弹性函数和非线性度是 235 219的(36,8,2)弹性函数.同年,Cheon22借助一个 u,m,d 线性码构造出(u+D+1,m,d 1)弹性函数,其中 D 为非负整数.此时,函数的代数次数为 D,非线性度至少为 2u+D 2n2u+D+1+2u1.当 D u 时,这一非线性度下界总是负数,因而只有在 D 足够大时才有参考价值.由这一方法得到的弹性函数的代数次数 D 可以超过输出维数 m.2002 年,Gupta 和 Sarkar23,24通过简单修改文献 15 中方法所构造的弹性函数,得到代数次数大于 m 的(n,m,t)弹性函数.通过改进文献 20,21 中的方法,构造出较高非线性度的(n,m,t)弹性函数.例如,可以得到非线性度是 235916220的(