完全置换多项式的研究进展*

许小芳, 曾祥勇, 徐运阁

湖北大学数学与统计学学院应用数学湖北省重点实验室, 武汉430062

完全置换多项式专栏

1 引言

有限域 Fq上多项式f(x) 诱导的从 Fq到 Fq的函数f:c→f(c) 是双射, 则称f(x) 为 Fq上的置换多项式.若f(x) 和f(x)+x都是 Fq上的置换多项式, 则称f(x) 为 Fq上的完全置换多项式[1].若f(x) 和f(x)−x都是 Fq上的置换多项式, 则称f(x) 为 Fq上的正形置换多项式[2].注意,f(x) 是完全置换多项式当且仅当 −f(x) 是正形置换多项式, 并且这两个术语在偶特征有限域上是一致的.对于偶特征有限域, 早期的一些文献采用“正形置换多项式” 这个名称[3–5], 近年来主要使用术语“完全置换多项式”[6–8], 所以本文采用名称“完全置换多项式”.本文主要关注有限域Fpm或向量空间Fmp上完全置换多项式(或称为完全置换)的相关理论研究.

完全置换多项式的研究由来已久, 其概念是Mann 在1942 年构造正交拉丁方时提出的[9].有限域上完全置换多项式的详细研究始于Niederreiter 和Robinson[1], 其应用非常广泛, 特别是在密码学领域.1995 年, 美国Teledyne 电子技术公司Mittenthal 首次利用偶特征域上完全置换多项式来设计非线性动力替换装置并构造密码算法[3,10].随后, Vaudenay 证明了添加完全置换的Lai-Massey 结构具有更好的伪随机性[11].人们还利用完全置换多项式来设计对称密码中的S 盒[12]、流密码Loiss[13]、Hash 函数[14,15]、拟群[16–18]以及构造具有良好密码学性质的密码函数[19–22].此外, 基于完全置换所构造的分组密码算法SMS4 是我国第一个商用分组密码标准, 且被推荐用于无线局域网WAPI 中[23,24].在组合数学领域,完全置换多项式与正交拉丁方联系紧密[9,25,26].另外, 完全置换多项式还被用于设计校验位系统[27].由于有限域上完全置换多项式的广泛应用, 近年来完全置换多项式的研究已成为一个热点问题.到目前为止,完全置换多项式的研究已取得了较大进展, 大多集中在完全置换多项式的构造.然而, 具有显式表示的完全置换多项式类非常少, 主要是稀疏型完全置换多项式和形如axpm+bx+h(xpm±x) 的完全置换多项式类.除此之外, 构造的方法也不多, 主要是基于经典密码结构、布尔函数组以及已有完全置换的递归构造.与完全置换的构造相比, 完全置换多项式的代数次数、圈结构等相关密码学性质的研究结果更少.因此, 加强完全置换多项式的构造以及相关密码学性质研究具有重要的理论和实际意义.

本文对近二十多年来有限域 Fpm或向量空间 Fmp上完全置换多项式的相关理论研究进行了总结.第2 节介绍有限域上完全置换多项式存在性的相关结论.第3 节总结完全置换多项式构造方面的主要研究进展, 第4 节和第5 节分别给出完全置换多项式的圈结构以及代数次数的相关研究成果.第6 节简要介绍广义完全置换多项式的相关研究.最后是本文的小结.

2 完全置换多项式的存在性

由于判断一个多项式的完全置换性是非常困难的, 完全置换多项式存在性相关结论在实际应用中可以有效地缩小搜索范围.吕述望等对有限群上完全置换多项式的存在性进行了综述和讨论, 详情见文献[28].本节仅介绍文献 [28]中没有收录的域Fpn上完全置换多项式存在性的相关结论.在已有文献中, 主要考虑特定次数或特定形式完全置换多项式的存在性.

早在1968 年,文献[29]提出了一个与次数有关的完全置换多项式不存在性猜想,Cohen[30]在1990 年证明了该猜想, 具体结论如下.

定理 1[30]若n⩾2 且素数p满足p>(n2−3n+4)2, 则 Fp上不存在次数为n的完全置换多项式.

Niederreiter 和Robinson[1]讨论了完全置换多项式的约化次数, 给出了如下存在性结论.

定理 2[1]当q>5 时, 有限域 Fq上存在约化次数大于1 的完全置换多项式.

随后, 人们开始关注 F2n上完全置换多项式的存在性问题.文献 [31]和 [32]通过Hermite 准则给出了F2n上完全置换多项式的如下不存在性结论.

定理 3n为正整数,d为大于1 的正整数, 有下面结论成立:

(1) 若d>1 且d|2n−1, 则 F2n上不存在d次完全置换多项式[31];

(2) F2n上不存在2 次完全置换多项式[31];

(3) 若n⩾3, 则 F2n上不存在 2n−1−1 次完全置换多项式[31];

(4) 当n≡0,1(modd) 时, F2n上不存在 2d−1 次完全置换多项式[32].

在文献 [32]的基础上, 文献 [33]给出了n模d的各种情况下 F2n上不存在 2d−1 次完全置换多项式的充分条件, 其中随后, 文献 [34]指出文献 [33]中结论的不足之处, 得到了 F2n上不存在2d−1 次完全置换多项式的充分条件以及存在2d次完全置换多项式的必要条件, 具体结论如下:

定理 4[34]设f(x) =αu(x2d−1+a2d−2x2d−2+ ···+a1x) 是 F2n上的多项式, 其中α为 F2n的本原元,u∈Z2n−1.设n=kd+r,e=d−r, 则:

(1) 当r=0,1 时,f(x) 不是 F2n上的完全置换多项式;

(2) 当 1

定理 5[34]设f(x) =αu(x2d+a2d−1x2d−1+ ···+a1x) 是 F2n上的多项式, 其中α为 F2n的本原元,u∈Z2n−1.设n=kd+r,e=d−r, 若f(x) 是 F2n上的完全置换多项式, 则:

(1) 当r=0,1 时, 必有a2d−1=0;

(2) 当 1

另外, 文献 [35]证明了有限域 F16上不存在9 次完全置换多项式.文献 [36]给出了与次数有关的正形置换不存在性结论, 根据正形置换与完全置换的关系, 下面定理说明了6 次完全置换的不存在性.

定理 6[36]偶特征有限域上不存在6 次完全置换.另外,m>2 时, F3m上不存在6 次完全置换.

此外, 文献[1]通过讨论二项式axk+bx的完全置换性给出了一些存在性相关结论.

定理 7[1]设q是素数的方幂, 则

(1) 当奇数q⩾13 或q=7 时, 有限域 Fq上一定存在形如的完全置换多项式;

(2) 令k>2, 若k不是素数的方幂, 当q⩾(k2−4k+6)2时, Fq上不存在形如axk+bx的完全置换多项式, 其中

(3) 令k> 2, 若k是素数p的方幂且p不等于 Fq的特征, 当q⩾ (k2−4k+6)2时, Fq上不存在形如axk+bx的完全置换多项式, 其中

(4) 令k>2, 若k和q都是素数p的方幂, 则存在形如axk∈Fq[x]的完全置换多项式.

文献[1,37]还给出了二项式axk+bxj∈Fq[x]不构成置换的一些充分条件, 进而在相同的条件下可知axk+bxj不构成完全置换多项式.另外, 当q=pm且p3 时, 文献 [38]指出对任意的v∈Fq3,v−1xq2+q+2不是 Fq3上的完全置换.

除上述研究之外, 文献[39]和[40]还给出了与置换多项式的Carlitz 秩 (Carlitz rank) 相关的完全置换不存在性结论.由于很难确定一个置换多项式的Carlitz 秩, 与Carlitz 秩相关的完全置换多项式不存在性结论的应用受到限制.

3 完全置换多项式的构造

完全置换多项式的构造是密码学中的热点问题, 目前已有一些成熟的构造方法以及完全置换多项式类.本节从构造方法以及多项式的形式来给出已有完全置换的分类, 包括基于线性完全置换的非线性完全置换、基于密码结构、布尔函数组、特殊函数的完全置换多项式、完全置换多项式的递归构造、完全置换的合成逆以及稀疏型完全置换多项式和形如axpm+bx+h(xpm±x) 的完全置换多项式.

3.1 基于线性完全置换的上非线性完全置换

1995 年, Mittenthal[3]指出通过有限个方程利用组合的方法可以构造上的线性完全置换.随后,Dai、Golomb 和Gong[5]利用正形矩阵介绍了一种非冗余构造算法生成上所有线性完全置换, 解决了上线性完全置换的构造问题.线性完全置换的其它相关问题参考文献[41–45].用于分组密码体制的完全置换需要满足的一个基本要求是非线性性, 所以研究非线性完全置换的构造具有重要的意义.

Mittenthal[10]指出上线性完全置换可以用 2n个等式表示, 在保证等式成立的前提下通过改变等式左端两列中元素的顺序, 能够得到非线性完全置换的过程称为构造性腐化(constructive corruption).专利[10]从最大线性完全置换 (详见定理45) 出发在陪集分解的基础上通过构造性腐化来生成非线性完全置换.由于可腐化陪集的选择方法有很多, 所以基于陪集分解的构造方法具有较大的灵活性.

随后, 谷大武和肖国镇[46]指出专利 [10]中最大线性完全置换选取不当时基于陪集分解的构造方法有可能失效, 并对该构造进行了适当的改进, 新的方法可以构造更多的非线性完全置换.

另外,Golomb、Gong 和Mittenthal[4]从最大线性完全置换出发构造移位拉丁方,在移位拉丁方的每一行和每一列中选择没有重复的元素来构造了一个截集(transversal)进而生成非线性完全置换.文献[4]中基于移位拉丁方截集的非线性完全置换构造算法并不是最优的, 但当n较大时比穷举搜索法有效.

专利 [10]和文献 [4]的发表吸引了很多国内学者关注基于拉丁方的完全置换构造问题[47–51]以及相关引文.令人遗憾的是, 这些构造所得非线性完全置换的代数表达式很难确定, 并且当n较大时所需内存较大, 在工程上难以实现.

3.2 基于密码结构的完全置换

流密码中的移位寄存器、分组密码中的Feistel 结构、MISTY 结构以及它们的组合常被用于构造完全置换多项式.

1995 年, Mittenthal[3]率先将极大长度的线性反馈移位寄存器与最大线性完全置换联系起来.随后,冯登国和刘振华[52]从不可约多项式出发利用线性反馈移位寄存器来构造线性完全置换.

使用任意轮函数的Feistel 结构可构造双射, 因此, Feistel 结构及其推广是创建非线性密码函数(特别是完全置换多项式)的常用技术.吕述望等[28]对完全置换的构造以及应用进行了研究, 给出了省略轮密钥的1 轮和2 轮Feistel 结构所对应的完全置换.

定理 8[28]设p是任一素数, 令p(z) 为有限域 Fpm上的置换多项式.则的映射

定理 9[28]令p1(z),p2(z) 为 F2m上的两个置换多项式.则

下面的结论是1 轮Feistel 结构的推广形式.

定理 10[28]令pi(z)(i=1,2,··· ,k− 1) 为 F2m上的多项式.若上的置换多项式, 则

随后, 文献[16,17]在讨论基于Feistel 结构分组密码的拟群表示以及拟群构造时, 利用交换群 (G,+)上双射构造了几类群 (Gn,+) 上的完全置换, 其中n⩾2.当G=Fpm时, 可得到上的完全置换, 以如下结论为例, 其余见文献[16,17].

定理 11[16]取常数a,b,c∈ Fpm.若p(x) 是 Fpm上的双射, 则

当a=b=c=0 时, Ωa,b,c,p就退化为定理8 中的完全置换 Ωp.显然, Ωa,b,c,p仿射等价于 Ωp.

另外, 文献 [18,53]在讨论基于Feistel 结构的Camellia、Four-Cell、GOST、MIBS、Skipjack 等分组密码的拟群表示时得到了五类上的完全置换和两类上的完全置换, 希望能够通过对应的代数结构来分析相应的分组密码.

最近, 受Feistel 结构和MISTY 结构的启发, 文献 [6]运用省略轮密钥的Feistel 结构, L-MISTY 结构以及R-MISTY 结构的1, 2, 3 轮组合, 得到了很多上完全置换多项式的构造.先给出这三种结构对应的三个映射 Ωp, Φp和 Ψp, 其中 Ωp与定理8 中表述一致.

定义 1[6]令p(z) 为 Fpm到其自身的多项式.的映射 Ωp, Φp和 Ψp定义为

定理 12[6]当p(z) 是 Fpm上的置换时, 定义1 中映射 Ωp, Φp和 Ψp是上的完全置换多项式.

2 轮构造可看作是映射 Ωpi, Φpi和 Ψpi(其中i= 1,2)的合成, 文献 [6]给出了九个合成映射构成完全置换的充分条件, 下面仅列出其中易于实现的七个完全置换.

定理 13[6]令p1(z),p2(z) 为 F2m上的两个置换多项式.则 {Ψp2◦Ωp1,Ωp2◦Φp1,Ψp2◦Φp1,Ωp2◦Ωp1,Φp2◦Ωp1,Ωp2◦Ψp1,Φp2◦Ψp1} 中任一映射是上的完全置换.

通过Feistel 结构和MISTY 结构的3 轮复合, 总共得到完全置换多项式的14 种构造, 这些构造所需要满足的条件大多比较类似, 在此仅列出以下两类, 其余见文献[6].

定理 14[6]取F2m上的两个置换多项式p1(z)+z,p3(z) 以及多项式p2(z).若多项式p2(z)+p3(z)是置换, 则 Φp3◦Ωp2◦Ωp1是上的完全置换.

定理 15[6]取有限域 F2m上的置换多项式p2(z) 和完全置换多项式p3(z).若p1(z) 是F2m上的完全置换多项式, 则映射 Φp3◦Ψp2◦Φp1是上的完全置换多项式.

相对而言, 定理15 的条件更容易实现, 而定理14 中需要找到两个 F2m上的 (置换) 多项式使得它们的和仍然是置换.如下定理表明MISTY 结构可以有效构造此类置换.

定理 16[6]令g1(z) 和g2(z) 是 Fq上的多项式, 其中q是 2 的方幂.取定义1 中映射 Φg1和 Ψg2.若g1(z) 和g2(z) 是 Fq上的完全置换多项式, 则多项式 Φg1, Ψg2和 Φg1+Ψg2是上的置换.

此外, 对任意的素数幂q, 文献[6]利用Feistel 结构的推广形式构造了一类上的完全置换多项式.

定理 17[6]取有限域 Fpm上的多项式p1(z),p2(z),p3(z), 其中p2(z) 是置换多项式.若对任意的γ∈Fpm,多项式p1(z)−p3(z+γ)是 Fpm上的置换,则多项式F(x1,x2)=(p1(−x2)−x1−p3(p2(p1(−x2)−x1)−x2),p2(p1(−x2)−x1)−x2) 是上的完全置换.

注意, 函数F(x1,x2) 与1 轮Feistel 结构所对应的映射 Ωp关系密切.另外, 定理17 的第一个条件并不容易满足.当p3(x) 为线性化多项式时, 可以找到大量满足该条件的p1(x).当p1(x),p3(x) 都不是线性化多项式时, 文献[6]给出了满足该条件的单项式p1(x),p3(x).

对任意的素数幂q以及不小于2 的整数n, 文章讨论的2 轮构造通过适当地调整可以得到很多 Fnq上的完全置换多项式, 由于这些结论的证明具有相似性, 这里仅给出如下结论.

定理 18[6]取 Fq上的置换多项式p1(z),p2(z), ··· ,pn(z), 其中q=pm, 则满足条件

的多项式G(x)=(G1(x),G2(x),··· ,Gn(x)) 是上的完全置换.特别地, 当p=n=2 时, 函数G(x)是2 轮Feistel 结构所对应的映射 Ωp2◦Ωp1.

与文献[16–18,28,53]中基于密码结构的完全置换相比, 文献[6]中除了对应于1 轮、2 轮Feistel 结构的 Ωp和 Ωp2◦Ωp1以外其余的构造均是新的.文献 [6]不仅得到了大量的完全置换多项式类, 还研究了所构造完全置换多项式的代数次数(详见第5 节).

本节所介绍的完全置换建立在经典密码结构基础上, 具有易于软硬件实现的特点, 值得进一步研究.

3.3 基于布尔函数组的完全置换

通过选取特殊的布尔函数组(或完全置换的坐标分量函数)可以有效地进行上完全置换的构造.冯登国和刘振华在文献[52]中提出了基于布尔函数组的构造方法.

定理 19[52]任取n−2 元布尔函数h2(x3,x4,··· ,xn),n−3 元布尔函数h3(x4,x5,··· ,xn),···, 1 元布尔函数hn−1(xn).令

则P(x)=(f1,f2,··· ,fn) 是上的完全置换.

另外他们还给出了由低阶完全置换拼接构造高阶完全置换的方法.

定理 20[52]取上的完全置换多项式fi(xi), 则F(x1,x2,··· ,xs) = (f1(x1),f2(x2),··· ,fs(xs))是上的完全置换.

定理20 所得到的完全置换有明显的缺点, 即F(x1,x2,··· ,xs) 可以分解为变量间没有关系的几个部分, 因而容易遭受攻击.为了提高其安全性, 文献[54–56]在定理20 的基础上增加元素之间的交叉, 给出了几种推广形式, 以如下定理来说明.

定理 21[54]设F(x1,x2,··· ,xn) 为上的完全置换,G(y1,y2,··· ,ym) 为上的完全置换, 取的函数H1(y1,y2,··· ,ym) 以及的函数H2(x1,x2,··· ,xn), 则 (F+H1,G) 和(F,G+H2) 是上的完全置换.

定理 22[59]设P1=(g1,g2,··· ,gn−2),P2=(h1,h2,··· ,hn−2) 为上的完全置换, 令

则P=(f1,f2,··· ,fn) 是上的完全置换.

定理 23[60]设P1(x1,x2,··· ,xn−2)=(f1,f2,··· ,fn−2) 为上的完全置换, 令

则P=(f1,f2,··· ,fn) 是上的完全置换.

另外, 文献[61]在研究M-M 型函数(Maiorana-McFarland 型布尔函数)与高原函数(plateaued function)关系的基础上, 使用上三组具体的基, 给出了一类上所有坐标分量为M-M 型函数的完全置换多项式.通过计算机模拟发现文献[61]所构造的完全置换在n较小时存在线性结构, 易受到攻击.随后, 采用文献 [61]的思想, 文献 [7]利用向量空间的任意一组基以及高原函数, 给出了完全置换多项式的一般构造.与文献[61]中的构造相比, 文献 [7]中的构造是基于任意一组基给出的, 且仅有部分坐标分量为M-M 型函数而另一部分坐标分量为布尔函数与高原函数的组合, 可以得到更多的完全置换多项式.此外, 通过计算机模拟发现文献[7]的构造中存在不包含线性结构的完全置换, 因而有望从该构造中找到安全性较高的完全置换多项式类.

本节所讨论的完全置换大多数是用坐标分量形式来表示的, 主要通过证明坐标分量函数的所有非零线性组合是平衡函数来说明其置换性.它们一般都具有简洁的分量表达式, 但在Fpn上的单变元表达式非常复杂.

3.4 基于特殊函数的完全置换多项式

本节主要介绍与Dikson 多项式、平面函数(planar mapping)、线性变换算子(linear translator)以及幂零线性化多项式(nilpotent linearized polynomial)相关的完全置换多项式.

1987 年, Mullen 和Niederreiter[62]讨论了Dikson 多项式Dk(x,a) 的完全置换性质.

定理 24[62]令且a,b,c∈ Fq, 其中若满足下面任一条件:

则bDk(x,a)+cx是Fq上的完全置换多项式.

最近, 文献[63]利用Dickson 多项式的合成逆给出了两个特殊完全置换多项式.

定理 25[63]取正整数m,k满足m=6k±1, 令da(x) 表示 F5m上Dickson 多项式D7(x,a) 的合成逆, 则对任意的δ∈ F5m,d1(−x5−x+δ) 和d−1(x5+x+δ) 都是 F5m上的完全置换多项式.

Muratović-Ribić 和Pasalic 发现平面函数的导函数与完全置换多项式之间存在密切的关系, 可以利用平面函数的导函数来构造完全置换多项式[64].

定理 26[64]设h是 Fpn上的平面函数且它在处的导函数为fa(x) =h(x+a)−h(x).令则对任意的有:

(1)g1,a(x) 和gp−1,a(x) 是 Fpn上的完全置换多项式;

(2)gt,a(x)+ ···+gp−1,a(x) 是 Fpn上的完全置换多项式, 其中 1tp− 2;

(3)g1,a(x)+ ···+gt,a(x) 是 Fpn上的完全置换多项式, 其中 1tp− 2;

另外, 文献[64]还提出了几乎平面函数(almost planar mapping)的概念并利用该函数来构造完全置换多项式.

定理 27[64]设f1(x),··· ,fn(x) 是 Fq上的平面函数.取任意函数构造的映射

其中xi∈ Fq.则F是几乎平面函数.特别地, 令fa(x) =F(x+a)−F(x), 则对任意的是上的完全置换多项式.

文献[64]中给出的基于平面函数和几乎平面函数所构造的完全置换多项式依赖于某个置换的合成逆,但是计算置换合成逆的困难性可能导致其应用受限.

下面先给出Fpm到其子域上线性变换算子的定义.

定义 2[65]取正整数m,n, 令f(x) 是的函数.取以及若对任意的x∈ Fpmn以及u∈ Fpm, 有f(x+uγ)−f(x)=ub, 则称γ为f(x) 在 Fpmn上相对于 Fpm的b-线性变换算子.

文献[65]得到了线性变换算子与完全置换多项式的如下联系.

定理 28[65]取奇素数p, 令f(x) 是 Fpmn到 Fpm的函数.若γ为f(x) 在 Fpmn上相对于 Fpm的b-线性变换算子, 则x+γf(x) 是Fpmn上的完全置换多项式当且仅当b/∈{−1,−2}.

随后, Akbary、Ghioca 和Wang[66]将线性变换算子的定义推广为 Fpm到其子集上.利用推广的线性变换算子, 定理28 中的条件可以进一步扩展, 得到了如下包含定理28 中结论的一类完全置换多项式.

定理 29[66]取奇素数p以及 Fpm的子集S且满足 2S=S, 令f(x) 是 Fpm到S的满射.若γ为f(x) 在 Fpm上相对于S的b-线性变换算子, 则x+γf(x) 是 Fpm上的完全置换多项式当且仅当

另外, 文献[67]在研究包含迹函数的置换多项式时提出了一类属于定理28 和定理29 特例的完全置换多项式.

定理 30[67]取奇素数p,令γ∈Fpm且满足中任意的h(x),有是Fpm上的完全置换多项式.

3.5 完全置换多项式的递归构造

本节主要介绍完全置换多项式的递归构造, 即通过已有置换或完全置换来构造新的完全置换多项式.

文献[1]中给出了由已知完全置换得到更多完全置换的基本方法.

定理 31[1]设f(x) 是Fpm上的完全置换多项式, 则:

(1)f(x+a)+b是 Fpm上的完全置换, 其中a,b∈Fpm;

(2)af(a−1x) 是 Fpm上的完全置换, 其中

(3)f−1(x) 是 Fpm上的完全置换.

由定理31 中(1)和(2)所构造的完全置换与原完全置换是仿射等价的, 利用(3)中合成逆来构造新的完全置换详见3.6 节.

下面介绍的递归构造是文献[69]和文献[25]在研究置换以及完全置换多项式时分别独立给出的.

定理32[25,69]取正整数m和正奇数n.假设L(x)是F2m上的线性化多项式.若对某些v∈F2mF2有xL(x)+vx是 F2m上的完全置换多项式, 则对任意的u∈F2m, 多项式

是F2mn上的完全置换.

在定理32 中取L(x)=0, 可构造如下完全置换多项式, 该构造是文献[70]中完全置换三项式的推广.

推论 1[25,69]取正整数m和正奇数n.对任意元素多项式ux)+vx是 F2mn上的完全置换.

多次使用定理32 和推论1, 可得如下包含多个迹函数的完全置换多项式.

推论 2[69]取正整数m, 正奇数n.假设d1,··· ,ds是互不相同的正整数且满足d1|d2|··· |ds|n, 令则对任意的v∈ F2mF2, 多项式是 F2mn上的完全置换, 其中且d0=1.

此外, 文献[71]运用AGW 准则给出了由子域上置换来构造扩域上完全置换的递归构造.

定理 33[71]对任意素数p, 取正整数r,k且n=rk.取 Fpk上的函数g(x), 若xg(x)+vx对某些构成 Fpk上的置换多项式，则当 gcd(p−1,r) = gcd(r,p) = 1 且a∈ Fpk{0,−1} 时, 多项式是 Fpn上的完全置换.

通过选取适当的g(x), 根据定理33 能构造很多完全置换多项式.例如, 当g(x) = 0 时, 可得如下推论.

推论 3[71]对任意素数p, 令n=rk, 其中r,k为正整数.若 gcd(p−1,r) = gcd(r,p) = 1 且a∈ Fpk{0,−1}, 则是 Fpn上的完全置换多项式.

在推论3 中取p=2 以及奇数r, 所得完全置换是推论1 的特殊情况.

在文献[25,69,71]的基础上, Tuxanidy 和Wang[26]使用AGW 准则来研究完全置换的递归构造.

定理 34[26]p为任意素数, 正整数r,m,n满足gcd(m,r)=gcd(mn,r),p∤n以及 gcd(n,pgcd(m,r)−1)=1.取 Fpm上的函数G(x), 则对任意的多项式

是Fpmn上的完全置换当且仅当xG(x) 是Fpm上的完全置换多项式.

定理34 推广了定理32.在定理34 中取G(x)=b∈Fpm{0,−1}, 可构造如下完全置换多项式.

推论 4[26]对任意素数p, 正整数r,m,n满足 gcd(m,r)=gcd(mn,r),p∤n以及 gcd(n,pgcd(m,r)−1) = 1.则对任意的多项式是 Fpmn上的完全置换.

多次运用定理34, 可以构造如下包含多个迹函数的完全置换多项式.

定理 35[26]取正整数m,n,r.假设d0,d1,··· ,dt是互不相同的正整数且满足 1=d0|d1|··· |dt=n.素数p满足以及取ak∈Fpmdk且令f0∈ Fpm[x], 则

是Fpmn上的完全置换多项式当且仅当f0(x) 是Fpm上的完全置换且满足f0(0)=0.

另外, 文献[8]通过AGW 准则给出了由域F2m上完全置换二项式来构造其扩域上完全置换的递归构造.

定理 36[8]取正整数n=mr且r为奇数.对正整数k, 若其中b=1, 则多项式

是F2n上的完全置换当且仅当g(x)=axk+bx是 F2m上的完全置换.特别地, 取k=2i, 其中i为非负整数,f(x) 是完全置换多项式当且仅当都不是 F2m中的 (k−1) 次幂元.

下面介绍Zha、Hu 和Cao 在文献[72]中提出的Fpn上完全置换多项式的递归构造, 这些构造所依赖多项式的值域为Fpn的子域.

定理 37[72]令n1|n2|···|nh|n, 当i= 1,2,··· ,h时, 取 Fpn[x]上值域在 Fpni中的多项式gi(x).令L(x) ∈ Fpn1 为线性化多项式.取满足且满足Fpni+1(i=1,2,··· ,h− 1).取满足则

是Fpn上的完全置换多项式当且仅当L(x) 是Fpn上的完全置换多项式.

作为定理37 的应用, 给出如下推论.

推论 5[72]取任意素数p, 令正整数n,l,k,s满足且l为偶数.

令θ,β,γ,δ∈ Fpn满足取 Fpk[x]中的线性化多项式L(x), 则

是Fpn上的完全置换多项式当且仅当L(x) 是Fpn上的完全置换多项式.

由于Fpn上迹函数的值域为Fpk, 文献[72]进一步利用迹函数给出了几个置换多项式的递归构造, 并指出其构成完全置换需满足的相应条件.

此外, 文献[19]还给出了一种类似于分量表示的递归构造法.

定理 38[19]对任意素数p以及正整数n, 令 {α1,α2,··· ,αn} 是 Fpmn关于 Fpm的一组基.对任意的i= 1,2,··· ,n, 令θi(xi) 为 Fpm上的完全置换多项式.当i= 2,3,··· ,n时, 函数将 (x1,x2,··· ,xi−1) 映射为ψi(x1,x2,··· ,xi−1).则

是 Fpmn上的完全置换多项式, 其中x=x1α1+x2α2+ ···+xnαn∈ Fpmn.

3.6 完全置换多项式的合成逆

Niederreiter 和Robinson[1]指出完全置换多项式的合成逆(简称为逆) 仍然是完全置换多项式, 故可以通过计算已有完全置换的逆来构造新的完全置换.一般情况下, 很难确定完全置换多项式合成逆的显式表示, 且相关研究成果较少.

在某些特殊情况下合成逆的计算难度相对较小, 比如计算完全置换单项式的合成逆.若存在v使得v−1xk构成 Fpm上的完全置换单项式, 则称k为 Fpm上的CPP 指数.假设k是 Fpm上的CPP 指数, 则k−1(modpm−1) 也是 Fpm上的CPP 指数.计算完全置换单项式的合成逆等价于给出k−1的明确表达式.利用欧几里德算法和中国剩余定理, 文献 [69]和 [73]分别独立给出了文献 [70]中三类完全置换单项式的合成逆.另外, 文献[73]和[74]构造完全置换单项式的同时还考虑了它们的逆.部分结论见表1.

除了单项式的合成逆以外, 文献 [69]通过有限域的直和分解将单变元多项式转化为双变元多项式来计算定理32 中完全置换多项式的逆, 得到了完全置换多项式新的递归构造, 该构造依赖于完全置换xL(x) +vx的合成逆.当L(x) = 0 时, 很容易可得推论1 中完全置换多项式逆置换的显式表示[69].随后, Tuxanidy 和 Wang[26]通过计算特殊集合上线性化二项式的逆给出了定理34 中完全置换多项式f(x) 的逆, 所得完全置换多项式的形式十分复杂且依赖于完全置换多项式xG(x) 的逆.此处所介绍的完全置换依赖于特殊完全置换的逆, 并不能直接给出显式表示.

若在分组密码的加密过程中应用完全置换多项式来构建混淆层, 在解密过程中将需要用到完全置换多项式的逆.因此, 确定易于实现完全置换多项式的合成逆是非常有意义的.

3.7 稀疏型完全置换多项式

有限域上稀疏型完全置换多项式, 即项数较少的完全置换, 由于其具有简洁的代数形式且在工程上易于实现而受到人们的广泛关注.本节重点介绍单项、二项以及三项的完全置换多项式.

稀疏型完全置换的研究热点是完全置换单项式.表1 中列出了 Fpm上的部分完全置换单项式.2013 年之前完全置换单项式的研究结果十分少, 主要是线性化完全置换单项式[1,75]和分式型指数完全置换单项式[75–77].2014 年, Tu、Zeng 和Hu[70]利用加法特征和极坐标表示法给出了有限域 F2n上的三类完全置换单项式, 在此将该文献所使用的方法简记为Tu-Zeng-Hu 方法.受该文献的启发, 通过类似方法可以得到一系列稀疏型完全置换多项式[71,73,74,78].从指数形式以及理论基础来看, 完全置换单项式的研究大致分为三类: (1) 基于Tu-Zeng-Hu 方法的完全置换单项式; (2) 分式型指数完全置换单项式; (3) 已有完全置换单项式的合成逆(见3.6 节).

随着文献 [70]的发表, 人们开始考虑利用Tu-Zeng-Hu 方法来证明多项式的置换性以及完全置换性.例如, Xu 和Cao[74]利用该方法研究了奇特征域 Fp2m上单项式v−1xk的完全置换性质, 其中p= 3 时指数k取 3m+2 或 2·3m+3.另外, 文献 [73,79]采用类似的方法给出了 F23k, F24k, F26k以及 Fp4k上的四类完全置换单项式.

表1 Fpm 上的完全置换单项式v−1xkTable 1 Complete permutation monomials v−1xk over Fpm

表2 Fpm 上的完全置换二项式αx+βxkTable 2 Complete permutation binomials αx+βxk over Fpm

完全置换三项式的已有结论格外少, 主要有四类, 具体结果见表3.第1 类给出了域F16上完全置换三项式的所有可能形式[35].第2 类是由Tu、Zeng 和Hu[70]利用AGW 准则得到的F23r上的完全置换三项式, 由它推广的递归构造详见文献 [69].第3 类是文献 [79]通过确定方程解的个数给出的奇特征域 Fp3r上的完全置换三项式.第4 类讨论的是Niho 型指数完全置换三项式, 文章不仅给出了这类三项式构成完全置换的充要条件, 还确定了所构造完全置换的个数, 相对其它完全置换三项式而言, 此类构造可以得到更多的完全置换[8].

表3 Fpm 上的完全置换三项式αx+β1xk1 +β2xk2Table 3 Complete permutation trinomials αx+β1xk1 + β2xk2 over Fpm

表3 中的完全置换三项式都包含1 次项, 文献 [63]从Dickson 多项式出发给出了一类特殊的不含1 次项的完全置换三项式.

定理 39[63]正整数m,k满足设a是 F5m上的非平方元.若正整数t满足 7t≡1(mod 5m−1), 则 3axt(x2t−a)2=3ax5t−6a2x3t+3a3xt是 F5m上的完全置换.

此外, 文献[1,36,81]还讨论了具体域上次数较低的稀疏型完全置换多项式.

3.8 形如axpm+bx+h(xpm±x)的完全置换多项式

命题 3[8]令f(x)=axpm+bx+h(xpm+x) 且 (a,b)∈Λ, 其中 Λ 见命题2.若满足下面任一条件:

(1)h(x)=u(x)pms−u(x)s, 其中u(x) ∈ Fp2m[x];

则f(x) 是Fp2m上的完全置换多项式.

在命题3 的条件(3)中取c= 1,p= 2, 所构造完全置换多项式与定理40 的结论有交叉.若在定理40 中添加条件a=0,b=0, 则命题3 包含了定理40 中的完全置换, 故命题3 部分推广了定理40.

最近, 文献 [89]研究了形如 (xpm−x+δ)s+axpm+bx的完全置换多项式.与文献 [8]中类似形式完全置换多项式不同的是此处不需要a,b同时不等于0.文献[89]通过确定一些相关方程解的个数, 给出了有限域Fpn上8 类形如 (xpm−x+δ)s+bx的完全置换多项式.对于指数s=i(pm±1)+pj, 给出了Fp2m上几类形如(xpm−x+δ)s+axpm+bx的完全置换多项式.当指数满足条件s=i(2m−1)+1 时,所用的主要证明方法是将F22m上方程解的判断转化为单位圈上方程解的个数判断问题, 此处的证明思想来源于文献[90].当指数为s=i(2m+1)+2j或s=i(3m−1)+3j时, 采用的证明方法是通过AGW 准则将 Fp2m上方程解的判断转化为子域或子集上线性化方程解的判断.文献 [89]不仅得到了大量完全置换多项式, 还推广了类似形式置换多项式的已有结论, 部分结果见表4.

表4 有限域Fpn 上形如(xpm −x+δ)s +axpm +bx 的一些完全置换多项式Table 4 Some CPPs (xpm − x+ δ)s +axpm +bx over Fpn

4 完全置换多项式的圈结构

与完全置换相关的一个问题是确定其圈结构.但由于缺乏有效的研究工具, 完全置换圈结构的研究进展十分缓慢, 人们主要考虑上最大线性完全置换的构造以及刻画.

首先给出圈结构的定义.

定义 3[28]一个置换的轮换表示中各轮换长度及其个数称为置换的圈结构, 记为 {ki× 1,k2×2,··· ,ki×i,···}, 其中ki×i说明该置换的轮换表示中有ki个长度为i的轮换.

定理 44[28]上完全置换的圈结构为 {1 × 1,0 × 2,··· ,0 × (2n− 3),0 × (2n− 2),···}, 即有且仅有一个不动点并且不存在长度为2, 2n−3, 2n−2 以及2n的轮换.

若Fn2上完全置换的圈结构为 {1×1,1×(2n−1)} 则称其为上的最大完全置换.完全置换圈结构的一个重要问题是最大完全置换的构造.Mittenthal[3]最早给出了最大线性完全置换与线性反馈移位寄存器之间的关系.

定理 45[3]F2n中最大线性完全置换的生成函数对应于n级极大长度线性反馈移位寄存器的生成函数.

另外, Golomb、Gong 和Mittenthal[4]根据向量空间与有限域 F2n的对应关系, 给出了 F2n上最大线性完全置换的代数构造法.

定理 46[4]取F2n的本原元α,令正整数s满足且gcd(s, 2n−1)=1.若f(x)=αsx,则f(x) 是F2n上的最大线性完全置换多项式.

据此定理, 文献[4]从矩阵变换和m序列出发给出了上最大线性完全置换的两种实现算法.

在寻找最大非线性完全置换构造方法的过程中, Mittenthal[10]指出最大非线性完全置换与线性完全置换之间存在如下关系.

定理 47[10]任一最大非线性完全置换可以通过构造性腐化由线性完全置换导出.

非常遗憾的是我们仅能从例子上看出从最大线性完全置换出发通过构造性腐化可以得到最大非线性完全置换, 但是专利[10]并没有给出通用的具体算法.如果能构造出无限类最大非线性完全置换将是完全置换圈结构研究的突破性进展.

此外, 文献 [19]在定理38 的基础上构造了一类 Fpn上不含不动点的完全置换多项式, 并指出其圈结构中包含短圈但并没有完全确定其圈结构.根据共轭的置换具有相同的圈结构, 文献 [64]指出定理26 所构造完全置换多项式g1,a(x) 的圈结构为pn−1∗p, 即有pn−1个长度为p的圈.

5 完全置换多项式的代数次数

在密码应用中, 通常希望使用的完全置换多项式具有高的代数次数从而能够抵抗已有的一些攻击.但是完全置换的相关文献重点考虑其构造与计数, 代数次数等密码学性质讨论得很少.

Niederreiter、Robinson 和Wan 在文献 [1,93]中讨论了 Fpn上完全置换多项式的约化次数.

定理 48[1,93]当pn>3 时, Fpn上任一完全置换多项式的约化次数不超过pn−3.

当pn>3 时, 由代数次数的定义以及定理48 知Fpn上任一完全置换多项式的代数次数最多为n(p−1)−1.

另外, 文献 [6]讨论了由Feistel 和MISTY 结构所构造完全置换的代数次数.很容易看出定理12 给出的上完全置换多项式 Ωp, Φp和Ψp的代数次数不超过m(p−1)−1.文献[6]中其余完全置换多项式的代数次数主要取决于函数F(x)=p2(p1(x1)+x2), 下面给出F(x) 的代数次数与p1,p2的关系.

命题 4[6]令q=pm其中p是素数且m是正整数.取 Fq[z]/(zq−z) 上的多项式p1(z),p2(z) 和笛卡尔积到有限域 Fq的函数F(x)=p2(p1(x1)+x2), 其中则特别地, 若p1(z),p2(z) 是 Fq上的置换多项式, 则F(x) 的代数次数不超过 2m(p−1)−3.

根据命题4, 文献 [6]中2 轮构造和大部分3 轮构造所得上完全置换多项式的代数次数都小于等于 2m−3.并且, 当n=2 时, 定理18 中完全置换多项式G(x) 的代数次数不超过 2m(p−1)−3[6].此外, 文献[6]还给出了如下具有几乎最优代数次数的完全置多项式.

定理 49[6]令q=pm, 取 Fq[z]中多项式p1(z)=p2(z)=zq−2.若p=2, 则下列完全置换多项式

的代数次数都是2m−3;若p是奇素数,当n=2 时,定理18 中完全置换G(x)的代数次数为2m(p−1)−3.

值得注意的是, 通过选取合适的多项式pi(z)(i= 1,2,3), 3 轮构造中有四个上完全置换多项式的代数次数可以达到2m−2[6].

此外, 文献[60]讨论了偶特征有限域上一些完全置换多项式的代数次数, 部分结论列举如下:

(1) 定理20 中取s=2,p=2,得到的F2n1+n2上完全置换多项式的代数次数不超过max{n1,n2}−1;

(2) 定理21 给出的F2m+n上完全置换多项式的代数次数不超过max{m,n};

(3) 定理19 和定理22 所构造的F2n上完全置换多项式的代数次数不超过n−2;

(4) 定理23 中F2n上完全置换多项式的代数次数达到最大值n−1.

据我们所知, 目前仅有文献[60]中给出的无限类完全置换多项式具有最优的代数次数, 因而需要探索出新的方法来构造更多易于实现且代数次数达到最优的完全置换多项式.

6 广义完全置换多项式

本节介绍几类与完全置换多项式相关的特殊置换多项式, 包含强完全置换多项式、K-完全置换多项式以及b-完全置换多项式, 这几类置换多项式统称为广义完全置换多项式.

令f(x) ∈ Fpm[x], 若f(x),f(x)+x和f(x)−x均是 Fpm上的置换多项式, 则称f(x) 为 Fpm上的强完全置换多项式[94].Evans[94]对有限群上强完全置换的存在性进行了综述.

Shaheen 和 Winterhof[27]研究了形如

随后, Winterhof[84]将几类特殊置换进行统一, 提出了K-完全置换的定义.

定义 4[84]令f(x) 是Fpm上的置换, 符号f(k)(x) 表示f(x) 的k次合成.取若干正整数所构成的集合K={k1,k2,··· ,ks}, 若FK(x)=x+ ∑k∈Kf(k)(x) 是 Fpm上的置换多项式, 则称f(x) 为 Fpm上的K-完全置换多项式.当K={1,2,··· ,k−1}(k⩾2)时, 称K-完全置换多项式为k-强完全置换多项式.

K-正形置换的定义可以类似给出.显然, {1}-完全置换就是通常意义下的完全置换多项式.文献[27]中的置换既是{2}-完全置换又是{2}-正形置换.

Winterhof[84]给出了类似于定理31 的K-完全置换多项式的基本构造方法, 研究了某些线性化多项式和2 阶分圆多项式的K-完全置换性质.K-正形置换的相关内容可参阅文献[30,84,95–97].

此外, 文献[38]和文献[98]分别提出了b-完全置换多项式(b-complete permutation polynomial)和b-完全(b-complete)的概念.

定义 5取 Fpm上的多项式f(x), 令

(1) 若f(x) 和f(x)+bx都是 Fpm上的置换多项式, 则称f(x) 为 Fpm上的b-完全置换多项式[38].

(2) 若f(x) 和bf(x)+x都是 Fpm上的置换多项式, 则称f(x) 为b-完全的[98].

根据定义5, 完全置换多项式即为 1-完全置换多项式, 亦可称相应的置换多项式是 1-完全的.显然,f(x) 是 Fpm上的b-完全置换多项式当且仅当b−1f(x) 是 Fpm上的完全置换多项式[38].另外, Fpm上多项式f(x) 是b-完全的等价于bf(x) 是Fpm上的完全置换多项式[98].

除了b-完全置换多项式, 广义完全置换多项式的研究主要集中在分圆多项式和线性化多项式, 且已知结论不多.鉴于广义完全置换多项式在校验位系统中的应用, 其构造研究尚需深入.

7 总结

本文对完全置换多项式的相关理论进行了综述, 包含完全置换的存在性、完全置换多项式的构造、代数次数、圈结构以及广义完全置换多项式.虽然近二十多年来人们在完全置换多项式的构造方面进行了深入地研究, 已取得了丰富的成果, 但仅有少数的完全置换多项式具有最优或几乎最优的代数次数, 且它们的圈结构等其它密码学性质鲜有人研究.另外, 完全置换的存在性和广义完全置换多项式这两方面的研究成果较少, 还没有引起足够地关注.总而言之, 完全置换多项式在分组密码、校验位系统以及组合设计等方面的理论和应用研究还需深入, 尚存在大量值得继续研究的问题, 比如:

研究问题1: 构造易于实现且具有最优代数次数的完全置换多项式.

研究问题2: 构造最大非线性完全置换多项式.

研究问题3: 分析并确定某些完全置换多项式的圈结构.

研究问题4: 分析并构造具有高非线性度、低差分等良好密码学性质的完全置换多项式.

研究问题5: 选取合适的完全置换多项式并将其用于密码系统的设计.