Construction of two classes of multi-output k-rotation symmetric Boolean functions*
旋转对称函数(rotation symmetric function,RSF)最初也叫做幂等函数,由Filiol 和Fontaine[1]首次提出。1999年,Pieprzyk 与Qu[2]在研究Hash 算法压缩函数的快速计算时,首次使用RSF。这类函数具有运算速度快、结构简单等特点。此外,旋转对称布尔函数还具有一些优良的密码学性质[3-5]。2008年,Kavut 和Yücel[6]将旋转对称布尔函数推广到k-旋转对称布尔函数,推广后的函数不仅具备旋转对称布尔函数的优良性质,而且数量更多。因此,构造具有特殊密码学性质的k-旋转对称布尔函数具有重要的理论意义。
近年来,许多学者对旋转对称布尔函数的平衡性、相关免疫性和弹性进行了深入的研究。Siegent‐haler[7]首先提出m 阶相关免疫函数,并证明了一个函数为m 阶相关免疫函数的充分条件;Chor 等[8]在计算机科学基础研讨会上提出弹性函数的概念;Stinson[9]给出了弹性函数(平衡的相关免疫函数)与正交表大集之间的关系;基于此,杜蛟课题组[10-15]分别研究了变元个数为p、pq、pr、4p 的1 阶弹性单输出RSF 的构造与计数问题;Pang 等[16]同样利用弹性函数与正交表大集之间的关系,将构造1 阶弹性旋转对称布尔函数的问题转化为求解方程组的问题,给出了任意变元的1 阶弹性单输出旋转对称布尔函数的一般构造方法。
多输出布尔函数可以用来设计分组密码的S盒,是分组加密算法的重要部分,具有一些特殊密码学性质的多输出布尔函数在密码体制中发挥着重要作用。2009年,元彦斌和赵亚群[17]首次提出多输出RSF 的概念,并研究了多输出RSF 的广义Walsh谱和广义自相关函数的性质,以及函数满足平衡性、相关免疫性的充要条件;2017年,杜蛟等[18]讨论了当输入变元n= 2r(r∈Z+),多输出旋转对称布尔函数满足平衡和弹性的条件时,所对应的输出变量维数的取值范围,给出了8 元多输出旋转对称1 阶弹性函数的具体构造并对其计数;2018年,Du 等[19]又通过解方程组的方法,当多输出旋转对称布尔函数满足平衡及1 阶弹性条件时,给出了对于变元n=pr(p 为奇素数,r∈Z+),相应的输出变量维数的取值范围,并证明了其存在性;2020年,田晔晨等[20]对Du等[19]的结果进行推广,将结果推广到多输出k-旋转对称布尔函数,通过对轨道进行划分,证明了几类平衡多输出k-旋转对称布尔函数与1 阶弹性多输出k-旋转对称布尔函数的存在性。
到目前为止,还没有文章给出任意变元的平衡与弹性多输出k-旋转对称布尔函数的存在性及构造方法。基于循环群在空间
上的作用,通过轨道划分以及构造正交表的方法,本文对田晔晨等[20]的结果进行推广,将输入变元n 和旋转阶数k 推广到任意正整数,给出了具有平衡及弹性的旋转对称布尔函数存在的充分条件以及具体的构造方法。
记
为二元域F2 上的n 维向量空间。定义映射F:
为n 元m 输出布尔函数,简记为(n,m)函数,即
F(X)=( f1(X),f2(X),…,fm(X)),
式中fi:
为n 元布尔函数[16]。若n元m 输出布尔函数F(X),对于
,都有|F−1(Y)|=2n−m,则称F(X)为平衡函数。特别地,当m=1 时,F(X)=f1(X)为单输出布尔函数。
考虑循环群
在
上的作用。对于
,定义
其中k-循环移位变换为
定义1[18] 设F(X)为F2 上的(n,m)函数,1≤k≤n 且k|n。若对于
,都有
式中⋅表示向量内积,则称F(X)为F2 上的n 元m 输出k-旋转对称布尔函数,记作(n,m)k-RSBF。
循环群
把
分为若干个大小不同的轨道。由X=(x1,x2,…,xn)生成的轨道记为
式中k|n。记|Gn,k(X)|为轨道Gn,k(X)的大小,易知|Gn,k(X)|为
的因子。因为
所以对于∀Y=(y1,y2,…,yn)∈Fn2,有
定义2[18] 若|Gn,k(X)|=d,记
则称
为Gn,k(X)对应的轨道矩阵。
设 F(X)是一个(n,m)k-RSBF,
F−1(Y)是由一定数量的轨道组成。由于F(X)在同一轨道上的取值相等,因此轨道矩阵对分析F−1(Y)具有重要意义。
引理1.1[20] 设hd,k 为
作用在
上得到的长度为d 的轨道的个数,则
式中μ(⋅)为莫比乌斯函数。
记
,则由
生成的轨道为
且
为Gn,k(X)的共轭轨道。若
,则称Gn,k(X)为自共轭轨道。因为自共轭轨道的向量中的分量是0、1 各半,因此当n 为奇数时不存在自共轭轨道。同时,由于自共轭轨道中的向量均是成对出现的,因此自共轭轨道的大小|Gn,k(X)|为偶数。
已有研究中,Dalai 等[21]、高光谱和刘文芬[22]分别给出了k=1 时,自共轭轨道的计数公式。田晔晨等[20]对其进行推广,得到了k 为n 的任意因子时,自共轭轨道的计数公式。
引理1.2[20] 设
为
作用在
上得到的长为d 的自共轭轨道个数,则
定义3[23] 设
为F2 上的矩阵,若
中的每个向量在由A 的任意m(1≤m≤n)列所构成的子矩阵中出现的次数相同,则称A 是一个(ω,n,2,m)正交表,简记作OA(ω,n,2,m)。
引理1.3[24-25] 一个(n,m)函数是d 阶相关免疫的当且仅当对于
中向量构成的矩阵均为OA(|F−1(Y)|,n,2,d)。一个(n,m)函数是d阶弹性的当且仅当对于
,由F−1(Y)中向量构成的矩阵为OA(2n−m,n,2,d)。
本节讨论对于任意的正整数n,平衡(n,m)k-RSBF 存在的充分条件及其构造方法。
引理2.1[20] 若平衡(n,m)k-RSBF 存在,则平衡(n,m−1)k-RSBF 也存在。
定理2.1 设
为素数,ri∈Z+),当
(pi 为奇素数,1≤si≤r)i时,对∀2≤m≤k,平衡(n,m)k-RSBF 存在。
证明 由引理2.1 知,只需要证明平衡(n,k)k-RSBF 存在。
设hd,k 为
作用于
上所得长度为d 的轨道个数,由引理1.1 得轨道分布如下:
则有
其中,
由于2 与p 互素,由欧拉定理知
因此
均为整数。将每
个轨道合并,则长为
的
个轨道被划分为2k 个集合,记这2k 个集合为
且![]()
。
将所有不同长度的轨道按照如上方式划分,令
则
即所有输入向量按照轨道被分为了2k 个集合。
令一个集合作为同一输出向量的原像集合,即构造1 个
上的n 元k 输出的函数F(X),其中,
即得到平衡(n,k)k-RSBF。由引理2.1,对∀2≤m≤k,平衡(n,m)k-RSBF 均存在。
注 对于任意长为d 的所有hd,k 个轨道,若满足2m|hd,k 且最短轨道至少可以划分为2m 个集合(即
为奇素数方幂且m≤k),那么平衡(n,m)k-RSBF存在。
定理2.1 给出了对于任意正整数n,当
为奇素数方幂时,平衡(n,m)k-RSBF 存在的充分条件。下面考虑当
的值为2 的方幂时,平衡(n,m)k-RSBF的存在情况。
定理2.2 设n 为偶数,当
时,对∀2≤m≤n−r,平衡(n,m)k-RSBF 存在。
证明 只需证明平衡(n,n−r)k-RSBF 存在。
设hd,k 为
作用在
上得到的长度为d 的轨道个数,由轨道计数公式可得轨道分布为
对上述轨道进行如下划分:
(1)将大小为1 的轨道两两任意合并,得到a0=
个大小为2 的集合,至此共得到a0+ h2,k 个大小为2 的集合;
(2)将(1)中得到的大小为2 的集合两两任意合并后得到
个大小为4 的集合,至此共得到
个大小为4 的集合;
……
(r)将(r-1)中大小为2r−1 的集合两两任意合并后得到
个大小为2r 的集合,至此共得到
个大小为2r 的集合。
记第(r)步中得到的2n−r 个集合为
从而可以构造出F2 上n 元n−r 输出的函数F(X),其中,
则F(X)为平衡(n,n−r)k-RSBF。由引理2.1 知,对∀2≤m≤n−r,平衡(n,m)k-RSBF 存在。
注 当
时,如果最长轨道的长度最大为2n−m,即此时满足m≤n−r,那么就可通过递归的方法对轨道进行划分,逐步将2n个输入向量划分为2m个大小为2n−m 的集合。令同一集合的向量对应同一函数值,即构造出平衡(n,m)k-RSBF。
本节讨论对任意正整数n,1 阶弹性(n,m)k-RSBF 存在的充分条件及其构造性证明。
引理3.1[20] 若1 阶弹性(n,m)k-RSBF 存在,则1 阶弹性(n,m−1)k-RSBF 也存在。
定理3.1 设
是素数,ri∈Z+),当
(pi 为奇素数,1≤si≤ri)时,对于∀2≤m≤k−1,1 阶弹性(n,m)k-RSBF存在。
证明 由引理3.1,只需要证明1阶弹性(n,k−1)k-RSBF 存在。
设hd,k 为
作用于
上得到的长度为d 的轨道个数,由轨道计数公式,计算得函数的轨道分布为
由定理2.1 证明可知,
均为整数。设长为
个轨道为
由于
为奇数,因此不存在自共轭轨道。令
由正交表定义知,U 中的元素均为正交表
,且
从而长为
的
个轨道被分为了
个大小为
的集合,且集合中的向量构成正交表
将上述
个集合每
个合并,则长为
的
个轨道被划分为2k−1 个集合,并且集合中的向量构成正交表
记这2k−1 个集合为
将所有不同长度的轨道按照上述方式划分,令
,则
所有输入向量按照轨道被分为了2k−1 个集合:
令一个集合作为输出向量的原像集,即构造1 个
上的n 元k−1 输出的函数F(X),其中
则F(X)为1 阶弹性(n,k−1)k-RSBF.由引理3.1,对∀2≤m≤k−1,1 阶弹性(n,m)k-RSBF 存在。
例3.1 设n=22⋅3,k=4,∀2≤m≤3,则1 阶弹性(n,m)k-RSBF 存在。
只需要说明1 阶弹性(12,3)4-RSBF 存在。其构造方法如下:
将2n=212=4 096 个输入向量通过循环群
作用后划分为若干轨道,由轨道计数公式得
将长为1 的16 个轨道中互为共轭的轨道两两任意合并,得到8 组正交表OA(2,6,2,1);将长为3的1 360 个轨道中互为共轭的轨道两两任意合并,得到680 组正交表OA(6,6,2,1);再将这680 组正交表任意每85 组合并得到8 组OA(512,6,2,1)。
至此所有4 096 个输入向量被划分为8 组正交表OA(512,6,2,1)。记为V1,V2,…,V8。
从而可以构造出12 元3 输出函数F=( f1,f2,f3),其中
由于篇幅限制,函数的真值表省略。
通过Matlab 进行仿真测试,可以验证F(X)为1 阶弹性(12,3)4-RSBF。通过MATLAB 计算,上述方式构造出来的1 阶弹性(12,3)4-RSBF 的非线性度为1 868。
注 对于任意长为d 的所有hd,k 个轨道,若满足
且最短轨道可以划分为2m 个OA(2,n,2,1)(即
的值为奇素数方幂且m≤k−1),那么1 阶弹性(n,m)k-RSBF 存在。定理3.1 利用共轭轨道的性质以及弹性函数与正交表之间的关系,通过构造出正交表,给出了对于任意正整数n,当
的值为奇素数的方幂时,1 阶弹性(n,m)k-RSBF 存在的充分条件。下面考虑当
为2 的方幂时,1 阶弹性(n,m)k-RSBF 存在的充分条件。
定理3.2 设n 为偶数,当
时,对∀2≤m≤n−r−1,1 阶弹性(n,m)k-RSBF 存在。
证明 由引理3.1 知,只需证明1 阶弹性(n,n−r−1)k-RSBF 存在。
用循环群
作用于空间
上,将
划分为若干轨道,设hd,k 为长度为d 的轨道个数,由轨道计数公式,计算不同轨道长度个数如
设长为 2s(0≤s≤r)的
个轨道为
令
对上述轨道按照如下方式划分:
(1)s=0,U0 中均为可构成OA(2,n,2,1)的元素,且|V0|=0,则长为20=1 的h1,k 个轨道被分为了
个集合,每个集合中的元素均构成OA(2,n,2,1)。再把a0个集合两两任意合并为
个集合,则集合中的元素均可构成正交表OA(4,n,2,1)。
(2)s=1,U1 中均为可构成OA(4,n,2,1)的元素,V1 的大小为偶数,将V1 中的轨道两两任意合并,则长为21 的h2,k 个轨道被分为了
个集合,每个集合均可构成OA(4,n,2,1),至此共得到a1=
个可构成OA(4,n,2,1)的集合,再两两任意合并,得到
个其元素可构成OA(8,n,2,1)的集合。
……
(r+1)s=r,Ur 中元素均为OA(2⋅2r,n,2,1),Vr 的大小为偶数,将Vr 中的轨道两两任意合并,则长度为2r 的
个轨道被分为了
个集合,集合中的元素均构成OA(2r+1,n,2,1)。至此,所有的输入向量集合被划分为了
个可构成OA(2r+1,n,2,1)的集合。
记第(r+1)步得到的2n−r−1 个集合为
从而可以构造出
上n 元n−r−1 输出的函数,其中
则F(X)为1 阶弹性(n,n−r−1)k-RSBF。由引理3.1 知,∀2≤m≤n−r−1,1 阶弹性(n,m)k-RSBF存在。
例3.2 设n=2⋅3,k=3,∀2≤m≤4,则1 阶弹性(n,m)k-RSBF 存在。
只需说明1 阶弹性(6,4)3-RSBF 存在。其具体构造方法如下:
将2n=26=64 个输入向量空间用循环群作用划分为若干轨道,由轨道计数公式,得
将长1 的8 个轨道,互为共轭的轨道两两合并为4 组正交表OA(2,6,2,1),再两两任意合并为2 组正交表OA(4,6,2,1);将长为2 的28 个轨道中自共轭轨道两两任意合并,互为共轭的轨道两两合并,得到14 组正交表OA(4,6,2,1)。至此所有64 个输入向量被划分为16 组正交表OA(4,6,2,1)。记这16 个集合为V1,V2,…,V16。
从而可以构造出6 元4 输出的函数G=(g1,g2,g3,g4),其中
函数G(X)的真值表(十六进制表示)为
g1:013E5E6E767A7C80,
g2:1F031DADB5B8C0F8,
g3:678F870A50E1F1E6,
g4:2A15AE5DBA75A854。
通过Matlab 进行仿真测试,可以验证G(X)为1 阶弹性(6,4)3-RSBF。通过Matlab 计算,上述方式构造出来的1 阶弹性(6,4)3-RSBF 的非线性度为8。
注 当
时,如果最长轨道至多可以划分为1 个OA(2n−m,n,2,1),那么就可以通过递归,逐步将2n 个输入向量划分为2m 组,使得每组均为OA(2n−m,n,2,1),将同一组中向量赋予同一输出值,即构造出1 阶弹性(n,m)k-RSBF。
本文基于循环群
在空间
上的作用,利用轨道划分及构造正交表的方法,分别给出了对于任意正整数n,当
为奇素数方幂和2 的方幂时,满足平衡性和1 阶弹性的多输出旋转对称布尔函数存在的充分条件及其构造性证明。推广了田晔晨等[20]结果,得到了对一般的n 和k,n 维m 输出k-RSBF 存在的充分条件,并且对所构造出来的函数进行了仿真测试。通过研究这一类特殊的多输出布尔函数,进而去寻找密码学性质优良的多输出布尔函数,不论是在理论上,还是在实践上都具有重要意义。目前有关多输出k-旋转对称函数构造的研究相对较少,对于具有良好密码学性质的多输出旋转对称布尔函数,比如代数免疫度、非线性度和相关免疫性方面,还有许多工作要做。对于这些特性的研究将是今后工作的一个课题。
[1]FILIOL E,FONTAINE C.Highly nonlinear balanced boolean functions with a good correlation-immunity[C]//NYBERG K.Advances in Cryptology-Eurocrypt’98:international conference on the theory and application of cryptographic techniques.Lecture Notes in Computer Science,vol 1403.Heidelberg:Springer,1998:475-488.
[2]PIEPRZYK J,QU C X.Fast hashing and rotationsymmetric functions[J].Journal of Universal Computer Science,1999,5(1):20-31.
[3]KAVUT S,MAITRA S,SARKAR S,et al.Enumeration of 9-variable rotation symmetric Boolean functions having nonlinearity>240[C]//BARUA R,LANGE T.Progress in Crytology-INDOCRYPT 2006.Lecture Notes in Computer Science,vol 4329.Heidelberg:Springer,2006:266-279.
[4]KAVUT S,YÜCEL M D.Search for Boolean functions with excellent profiles in the rotation symmetric class[J].IEEE Transactions on Information Theory,2007,53(5):1743-1751.
[5]STĂNICĂ P,MAITRA S.Rotation symmetric Boolean functions-count and cryptographic properties[J].Discrete Applied Mathematics,2008,156(10):1567-1580.
[6]KAVUT S, YÜCEL M D.Generalized rotation symmetric and dihedral symmetric Boolean functions−9 variable boolean functions with nonlinearity 242[C]//BOZTAS, LU H F.Applied algebra, algebraic algorithms and error-correcting codes:17th international symposium.Lecture Notes in Computer Science,vol 4851.Heidelberg:Springer,2007:321-329.
[7]SIEGENTHALER T.Correlation-immunity of nonlinear combining functions for cryptographic applications[J].IEEE Transactions on Information Theory,1984,30(5):776-780.
[8]CHOR B,GOLDREICH O,HASTED J,et al.The bit extraction problem or t-resilient functions[C]//26th Annual Symposium on Foundations of Computer Science.SFCS 1985.Portland:IEEE,1985:396-407.
[9]STINSON D R.Resilient functions and large sets of orthogonal arrays[J].Congressus Numerantium,1993,92:105-110.
[10]杜蛟,温巧燕,张劼,等.素数元旋转对称弹性布尔函数的构造与计数[J].通信学报,2013,34(3):6-13.
[11]DU J,WEN Q,ZHANG J,et al.Construction and counting of 1-resilient rotation symmetric Boolean functions on pq variables[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,2013,96A(7):1653-1656.
[12]DU J,PANG S,WEN Q,et al.Construction and count of 1-resilient rotation symmetric Boolean functions on pr variables[J].Chinese Journal of Electronics,2014,23(4):816-820.
[13]DU J,WEN Q,ZHANG J,et al.Constructions of resilient rotation symmetric Boolean functions on given number of variables[J].IET Information Security,2014,8(5):265-272.
[14]DU J,FU S,QU L,et al.New constructions of qvariable 1-resilient rotation symmetric functions over Fp[J].Science China Information Science,2016,59(079102):1-3.
[15]PANG S,XU W,DU J,et al.Construction and count of 1-resilient rotation symmetric Boolean functions on 4p variables[J].Chinese Journal of Electronics,2017,26(6):1276-1283.
[16]PANG S,WANG X,WANG J,et al.Construction and count of 1-resilient rotation symmetric Boolean functions[J].Information Sciences,2018,450:336-342.
[17]元彦斌,赵亚群.多输出旋转对称函数的密码学性质[J].通信学报,2009,30(11A):1-7.
[18]杜蛟,尚玉婧,赵金玲,等.8 元多输出旋转对称弹性函数的构造与计数[J].通信学报,2017,38(7):47-55.
[19]DU J,FU S J,QU L J,et al.The existence of a class of balanced multi-output rotation symmetric Boolean functions[J].Chinese Journal of Electronics,2018,27(5):995-1001.
[20]田晔晨,孙玉娟,李路阳.多输出弹性k-旋转对称布尔函数的存在性与构造[J].密码学报,2020,8(1):96-109.
[21]DALAI D K,MAITRA S,SARKAR S.Results on rotation symmetric bent functions[J].Discrete Mathematics,2009,309(8):2398-2409.
[22]高光普,刘文芬.关于旋转对称布尔函数线性结构的几点注记[J].电子与信息学报,2012,34(9):2273-2276.
[23]CAMION P,CARLET C,CHARPIN P,et al.On correlation-immune functions[C]//FEIGENBAUM J.Advances in Cryptology-CRYPTO’91.Lecture Notes in Computer Science,vol 576.Heidelbery:Springer,1991:86-100.
[24]CAMION P,CANTEAUT A.Correlation-immune and resilient functions over a finite alphabet and their applications in cryptography[J].Designs,Codes and Cryptography,1999,16(2):121-149.
[25]GOPALAKRISHNAN K, STINSON D R.Three characterizations of non-binary correlation-immune and resilientfunctions[J].Designs, Codesand Cryptography,1995,5(3):241-251.