一類旋轉對稱bent函數的構造

鄭　東,嚴宏超,趙慶蘭

(西安郵電大學 通信與信息工程學院， 陜西 西安 710121)

布爾函數在密碼學[1]中具有廣泛應用[2-5]，可以作為流密碼的非線性組件[4]以及分組密碼的S-盒[6]中的核心組件。

bent函數[7]是Walsh譜取值為±2n/2的一類布爾函數，與仿射函數集合具有最大漢明距離，能夠有效抵抗線性攻擊和最佳仿射逼近攻擊。旋轉對稱(rotation symmetric boolean functions,RotS)布爾函數[5]也稱為冪等函數[8]，當輸入向量循環左移時其輸出值保持不變。利用RotS布爾函數可實現Message Digest系列中的雜湊壓縮算法，還可進行快速Walsh變換[9]。

當變元數n=2m,且m/gcd (m,t)是奇數時(1≤t≤m-1)，可構造出一類二次和三次旋轉對稱bent函數ft(x)[4,10]。代數次數從2到m的2m元旋轉對稱bent函數的構造[11]，首次將旋轉對稱bent函數的代數次數提高至大于3。通過修改代數次數較低的旋轉對稱bent函數，也可得到兩類代數次數為d(3≤d≤m)的旋轉對稱bent函數[12]。

本文將在文獻[4，12]的基礎上，深究旋轉對稱bent函數的性質和構造，給出一個Maiorana-McFarland類[13]函數，并證明該函數為旋轉對稱bent函數。當變元數n=2m(m∈+)為偶數時，所給新函數的代數次數可達m。

1　基礎知識

任一n元布爾函數f均可以用其代數正規型(algebraic normal form,ANF)唯一表示為

(1)

其中，向量

α=(α0,α1,…,αn-1),x=(x0,x1,…,xn-1)，

的系數取值。

定義向量x的支撐集為

supp(x)={i:xi=1}。

其中所含元素“1”的個數稱為向量x的漢明重量，記為w(x)。布爾函數f(x)的支撐集定義為

其中所含元素“1”的個數稱為函數f(x)的漢明重量，記為w(f)。任意的兩個布爾函數f(x)和g(x)的漢明距離滿足

dH(f,g)=w(f+g)。

如果布爾函數的f(x)漢明重量w(f)=2n-1，則稱該布爾函數是平衡的。

(2)

布爾函數f(x)的代數次數是其代數正規型中系數非零的單項式的最大變元個數，記為

當布爾函數f(x)的代數次數deg(f)≤1時，該函數被稱為仿射函數，所有n元仿射函數的集合記為An。如果仿射函數的常數項為0，則被稱其為線性函數。如果f(x)?An，則稱其為非線性函數。

布爾函數與仿射函數的相關聯程度一般用非線性度(nonlinearity,NL)來描述，非線性度值的大小決定著布爾函數抵抗仿射逼近攻擊的能力。非線性度是任意布爾函數f(x)和仿射函數l(x)之間的最小的漢明距離，定義為

由Parseval恒等式可知，當|Wf(α)|=2n/2時，|Wf(α)|取最小值。一般而言，對任意布爾函數f(x)都成立

NL(f)≤2n-1-2n/2。

如果某布爾函數的非線性度達到上界值，則稱其為bent函數。

定義1對任意布爾函數f(x)∈Bn，其Walsh譜值滿足

當且僅當f(x)是bent函數。

bent函數的變量個數只能為偶數。bent函數雖不是平衡函數，但其在布爾函數中非線性度最高。

定義2當n=2m(m∈+)時，變量和滿足

f(x,y)=π(x)y+h(x)

(3)

定義3任給xi∈F2(i=0,1,…,n-1),正整數k滿足0≤k≤n-1，定義

(4)

其中

同理，也可將其擴展到多項式上，定義

其中0≤xi0<…

定義4設f(x)∈Bn,若對任意輸入

都成立

則稱f(x)為旋轉對稱布爾函數。

對RotS布爾函數而言，如果存在代表元，那么包含該代表元的軌道中，所有序列都存在于該函數的ANF中。

示例1當n=4時，給定軌道

{x0x1x2,x1x2x3,x2x3x0,x3x0x1},

那么,該軌道的代表元是x0x1x2。

2　旋轉對稱bent函數的構造

以下在m/gcd(m,t)是奇數(1≤t≤m-1)的情況下，給出一類旋轉對稱bent函數的構造方案，據此所構造函數的代數次數為d(3≤d≤m)，可達到bent函數的最高代數次數。

引理1[12]設n=2m，f(x)∈Bn，且

(1) 對任意下標i(0≤i≤m-1),f(x)滿足

f(x0,…,xi,…,xi+m,…,xn-1)=
f(x,…,xi+m,…,xi,…,xn-1)。

(2) 對任意下標i(0≤i≤m-1)，單項式xixi+m不在f(x)的項中。

(3)f(x)是一個旋轉對稱布爾函數。

那么，存在一個旋轉對稱布爾函數

使得f(x)和γ(y)滿足

f(x0,x1,…,xn-1)=
γ(x0+xm,x1+xm+1,…,xm-1+x2m-1)。

由引理1的條件(3)可知,f(x)是一個旋轉對稱布爾函數，故γ(y)也是一個旋轉對稱布爾函數。

引理2[10]令m和t是任意正整數，且

1≤t≤m-1，r=m/gcd(m,t)。

對任意滿足0≤k≤gcd(m,t)的正整數k，記

xk+m-t mod m=xk+(r-1)t mod m，

且r，m和t滿足

(m-t)≡(r-1)tmodm。

φ(k)(xk,xk+t,…,xk+(r-1)t)=
(xkxk+m-t+xk+t+xk,xk+txk+xk+2t+xk+t,…,xk+(r-1)txk+(r-2)t+xk+xk+(r-1)t)，

(5)

引理3[12]令n=2m，t(1≤t≤m-1)為正整數，且xi∈F2(i=0，1，2，…，n-1)，則

(6)

如果無特別說明，所涉及函數ANF的變量xj的值為jmodn。

定理1令n=2m，且t(1≤t≤m-1)是正整數，m/gcd(m,t)是奇數，布爾函數

則函數

(7)

是bent函數。若γ(y)=γ(y0,y1,…,ym-1)是代數次數為d(3≤d≤m)的旋轉對稱布爾函數，那么,函數f(x)是代數次數為d的旋轉對稱bent函數。

(8)

其中

因m/gcd(m,t)是奇數，故由引理2可知

(π0(a),π1(a),…,πm-2(a),πm-1(a))

當0≤i≤m-1時，對f0(a,y)中的變量a和y分別進行仿射變換

yi=xi+m,ai=xi+xi+m,

可得bent函數

(9)

其中

于是

也是bent函數。

另由引理1可知γ(y)是旋轉對稱的，故函數f(x)也是旋轉對稱的。進而，當n=2m為偶數時，若γ(y)的代數次數為d(3≤d≤m)，那么函數f(x)就是代數次數為d的旋轉對稱bent函數。

3　結語

在變元數n=2m為偶數，且m/gcd(m,t)為奇數的情況下，構造出一類旋轉對稱bent函數，該函數具有任意的代數次數d(3≤d≤m)，且該代數次數的取值可以達到目前已知的旋轉對稱bent函數的最優值，同時證明了該類函數是Maiorana-McFarland類bent函數。