對稱布爾函數算術Walsh變換的快速算法

趙慶蘭， 鄭 東,2

(1.西安郵電大學 通信與信息工程學院， 陜西 西安 710121；2.西安郵電大學 無線網絡安全技術國家工程實驗室， 陜西 西安 710121)

對稱布爾函數算術Walsh變換的快速算法

趙慶蘭1， 鄭 東1,2

(1.西安郵電大學 通信與信息工程學院， 陜西 西安 710121；2.西安郵電大學 無線網絡安全技術國家工程實驗室， 陜西 西安 710121)

為了提高對稱布爾函數算術Walsh變換的實現效率，利用Krawtchouk 多項式研究對稱布爾函數的算術Walsh變換。根據算術Walsh變換的定義討論對稱布爾函數的算術 Walsh變換和Krawtchouk 多項式之間的關系，給出并證明基于Krawtchouk 多項式描述的對稱布爾函數的算術 Walsh變換的簡約表達式。利用得出的簡約表達式和Krawtchouk 多項式的性質即可得出一種實現對稱布爾函數的算術 Walsh變換的快速算法，該算法具有較低的時間復雜度和空間復雜度。

布爾函數；Walsh變換；2-adic數；Krawtchouk多項式

對稱布爾函數是一類特殊的布爾函數，它的輸出函數值只與輸入向量的漢明重量有關，正是由于這個特殊的性質，對稱布爾函數在軟件硬件實現方面能夠使計算復雜度降低，具有廣泛的應用，因而受到研究者的關注[8-10]。對稱布爾函數的經典的Walsh譜是一個對稱實值函數，并且在具有相同漢明重量的向量點具有相同的Walsh變換系數[11]。文獻[12]利用文獻[5]中的定理2證明了對稱布爾函數的算術Walsh譜是對稱實值函數。Krawtchouk多項式是描述對稱布爾函數的經典Walsh變換的重要工具，本文利用Krawtchouk多項式研究對稱布爾函數的算術Walsh譜,并利用Krawtchouk多項式的特殊性質給出了基于Krawtchouk多項式的對稱布爾函數的算術Walsh譜的簡約表達式。

目前尚無文獻討論對稱布爾函數的算術Walsh譜的實現算法，本文借鑒文獻[10]中提出的一種對稱布爾函數的經典Walsh譜的實現算法，利用基于Krawtchouk多項式的對稱布爾函數的算術Walsh譜的簡約表達式和Krawtchouk多項式的性質，提出了一種計算對稱布爾函數的算術Walsh譜的快速實現算法，該算法在實現過程中利用Krawtchouk多項式的性質減少了計算量，該算法的時間復雜度是O(n2)，空間復雜度是O(n)。

1 基礎知識

定義1 令n為正整數，n元布爾函數的定義為

其中IF2={0,1}。記Bn為全體n元布爾函數的集合，且

f的漢明重量記為

wt(f)=|1f|。

另設

則x的漢明重量記為

wt(x)=|{xi:xi=1}|。

定義2 設一個n元布爾函數f的Walsh變換

是一個整數值函數，另取

它們的內積

[x·w]2=x1w1⊕x2w2⊕…⊕xnwn,

那么

成為f在點w的Walsh變換系數，f的所有Walsh變換系數的集合稱為f的Walsh譜。

定義3 稱n元布爾函數f(x)∈Bn為對稱布爾函數,如果對任意n×n階置換矩陣P,恒有

f(x)=f(xP) 。

wt(x)=wt(y)，

都有

f(x)=f(y),

則f是對稱布爾函數。

根據定義每個n元對稱布爾函數f(x)∈Bn可以由一個n+1元向量

來表示,其中分量vf(i)表示重量為i的輸入向量的函數值。

度數為i的Krawtchouk多項式的定義為

(i=0,1,…,n)。

wt(w)=k,

成立下等式

定理1[11]設f(x)∈Bn，Wf(w)表示其Walsh變換，f是n元對稱布爾函數當且僅當Wf(w)是一個對稱實值函數。

對于n元對稱布爾函數f(x)∈Bn,則有

2 算術Walsh變換

關于算術Walsh變換的定義，詳細內容可參考文獻[4-5]。

定義4 令

={0,1,2,…},

布爾函數f的擴展函數

F:n→ IF2,

F(x1,x2,…,xn)=

f(x1mod2,x2mod2,…,xnmod2)。

擴展集合

Pn={F:F(x+2b)=F(x),b∈n}

是Rn的子集,其中

Rn={F:n→IF2}。

Sn=[(t1,t2,…,tn)]/(t1t2…tn-2)

是同構的，其中

[(t1,t2,…,tn)]=

對于任意的x∈n，定義對角線集合

Dx={x+c(1,1,…,1):c∈}。

對于一個固定位于某條對角線上的x∈n，沿著對角線Dx上的所有項的和在同構意義下可定義一個2-adic數

(1)

定義5 對于任意F∈Rn，如果存在一個整數k滿足對于任意

x=(x1,x2,…,xn)∈n

(xi≥k,i=1,2,…,n)，

使得對于任意b∈n,有

F(x+pb)=F(x),

則F是最終p-周期的。如果對任意

x=(x1,x2,…,xn)∈n，

都有

xi≥k(i=1,2,…,n)，

則F在集合

{x+b:b=(b1,b2,…,bn),0≤bi

上的值稱為F的一個完整的周期。

假設F∈Rn是嚴格2-周期的函數，則由式(1)可得

f(x)+f(x+1n)2+f(x)22+…=

(2)

定義6 對于任意F∈Rn是最終p-周期的,F的不平衡度為

其中

Un={x=(x1,x2,…,xn):

xi∈{0,1},x1=0}。

定義7 一個最終周期的函數F∈Rn的算術Walsh變換定義為實值函數

其中Ta定義為

Ta(b)=[a·b]2(b∈n)。

3 對稱布爾函數的算術Walsh譜

定理2[12]設f(x)∈Bn是n元對稱布爾函數，則f(x)的算術Walsh譜是對稱實值函數。

文獻[5]利用拉格朗日插值方法求出了布爾函數的算術Walsh譜的計算公式，如下述引理。

引理1[5]令f∈Bn，如果[b·1n]2=0，則

如果[b·1n]2=1,則

[f(x)-f(x+1n)][x·b]2。

利用定理2和引理1可以證明如下定理。

定理3 設f(x)∈Bn是n元對稱布爾函數，其向量表示為

如果k為奇數,則有

由定理3和Krawtchouk 多項式的定義我們可以推出如下結論。

推論1 設f(x)∈Bn是n 元對稱布爾函數，其向量表示為

如果k為奇數,則有

證明 利用定理3和

(-1)[x·w]2=1-2[x·w]2

即可證明。

推論1給出了對稱布爾函數的算術Walsh變換的基于Krawtchouk多項式的一般表達式，根據Krawtchouk多項式的性質，還可得出更加簡約的表達式。

定理4[10,15]關于Krawtchouk多項式，成立

K0(k,n)=1,

K1(k,n)=n-2k,

(i+1)Ki+1(k,n)=

(n-2k)Ki(k,n)-(n-i+1)Ki-1(k,n),

Ki(k,n)=(-1)kKn-i(k,n),

Ki(k,n)=(-1)iKi(n-k,n),

特別當n是偶數且k為奇數時，有

而當n是偶數且i為奇數時，有

定理5 設f(x)∈Bn是n元對稱布爾函數，其向量表示為

如果k為奇數,則有

其中

證明 由定理4可知,當k為偶數時,有

Ki(k,n)=Kn-i(k,n),

當k為奇數時, 有

Ki(k,n)=-Kn-i(k,n),

定理得證。

4 算術Walsh譜快速算法

文獻[10]給出了一種計算對稱布爾函數的經典Walsh譜的快速計算算法，算法的時間復雜度是O(n2)，空間復雜度是O(n)。目前尚無文獻討論對稱布爾函數的算術Walsh譜的快速實現算法，利用定理5可得出對稱布爾函數的算術Walsh譜的快速實現算法。

由于定理5的證明利用Krawtchouk多項式的性質簡化了對稱布爾函數的算術Walsh譜的Krawtchouk多項式表達式，因此在計算過程中計算出Ki(k,n)后不需要計算Kn-i(k,n)，進一步減少了求解過程的運算。該算法的時間復雜度是O(n2)，空間復雜度是O(n)。

新算法的主要思想可描述如下。

使用迭代法計算Ki(k,n),不需要存儲每個Ki(k,n)。根據定理4可得

(n-i+1)Ki-1(k,n)],

K0(k,n)=1, K1(k,n)=2-2k,

在每個循環里計算Ki+1(k,n)，只需要暫時存儲Ki(k,n)和Ki-1(k,n)的值，在下一輪的計算中會被新的值覆蓋。

具體算法可描述如下。

輸入 函數變量個數n，對稱布爾函數

vf=(vf(0),vf(1),…,vf(n))。

輸出 對稱布爾函數的算術Walsh譜af。

開始

s=K0(k,n)=1； t=K1(k,n)=n-2k

if (k是偶數) h1=vf(0)vf(n)；

else h1= vf(0)-vf(n)；

if (n-k是偶數) h2=vf(0)vf(n)；

else h2=vf(0)-ff(n)；

if (k是偶數) h1=h1+vf(i)vf(n-i)t;

else h1= h1+[vf(i)-vf(n-i)]t；

if (n-k是偶數)

h2= h2+vf(i)vf(n-i)(-1)it;

else

h2= h2+(vf(i)-vf(n-i))(-1)it;

s=t, t=r;

}

if (n是偶數){

af(k)=2n-2p+q+2h1;

af(n-k)=p-q-h2

}

if (n是偶數) {

h1=vf(0)vf(n);

s=K0(k,n)=1； t=K1(k,n)=n-2k

h1= h1+ vf(i)vf(n-i) t；

s=t, t=r;

}

af(k)=2n-2p+q+2h1

}

結束

5 結語

研究具有特殊密碼學性質的對稱布爾函數的算術Walsh變換的性質和實現算法。首先證明了對稱布爾函數的算術Walsh變換和Krawtchouk 多項式之間的關系，并根據兩者之間的關系和Krawtchouk 多項式的性質提出了一種時間復雜度和空間復雜度較低的對稱布爾函數的算術Walsh譜的快速計算算法。算術Walsh變換作為對經典Walsh變換的進位模擬，是一種全新的研究布爾函數的方法，其本身的性質有待進一步深入的研究。下一步的工作將重點研究算術Walsh變換和布爾函數的其他密碼學性質的聯系，以及與算術Walsh變換相關的某種類型的密碼攻擊。

[1] Carlet C. Boolean Functions for Cryptography and Error Correcting Codes[M]. Cambridge: Cambridge University Press, 2007:4-6.

[2] 溫巧燕,鈕心忻,楊義先. 現代密碼學中的布爾函數[M]. 北京: 科學出版社, 2000:1-3.

[3] Cusick T, Stanica P. Cryptographic Boolean Functions and Applications[M]. San Diego: Academic Press, 2009:1-10.

[4] Klapper A, Goresky M. A With-Carry Walsh Transform (Extended Abstract)[C]//Sequences and Their Applications-SETA 2010, Lecture Notes in Computer Science. Paris: Springer Berlin Heidelberg, 2010: 217-228.

[5] Klapper A, Goresky M. Arithmetic Correlations and Walsh Transforms[J]. IEEE Transactions on Information Theory, 2012, 58(1):479-492.

[6] Klapper A. Arithmetic Walsh Transform of Quadratic Boolean Functions[C]// Sequences and Their Applications-SETA 2012, Lecture Notes in Computer Science. Waterloo: Springer Berlin Heidelberg, 2012:65-76.

[7] Carlet C, Klapper A. On the Arithmetic Walsh Coeffients of Boolean Functions[J/OL].Designs, Codes and Cryptography. (2014-02-30)[2014-05-20].http://cs.engr.uky.edu/～klapper/pdf/AWT-PSF.pdf.DOI:10.1007/s10623-013-9915-3.

[8] Canteaut A, Videau M. Symmetric Boolean Functions[J]. IEEE Transactions on Information Theory, 2005, 51(8):2791-2811.

[9] Braeken A, Preneel B. On the Algebraic Immunity of Symmetric Boolean Functions[C]//Progress in Cryptology - INDOCRYPT 2005: 6th International Conference on Cryptology in India, Bangalore, India, December 10-12, 2005. Berlin: Springer Berlin Heidelberg, 2005: 35-48.

[10] Dalai D K, Maitra S, Sarkar S. Basic Theory in Construct ion of Boolean Functions with Maximum Possible Annihilator Immunity[J]. Design, Codes and Cryptography, 2006, 40(1): 41-58.

[11] Dawson E, Wu Chuankun. on the linear structure of symmetric Boolean functions[J]. Australasian Journal of Combinatorics, 1997(16): 239-243.

[12] 趙慶蘭，鄭東.布爾函數性質Walsh譜與算術Walsh譜[J].科學技術與工程，2013,13(17), 4804-4811.

[13] Koblitz N. p-Adic Numbers, p-Adic Analysis, and Zeta Functions[M]. New York: Springer, 1984:1-5.

[14] Klapper A, Goresky M. Feedback Shift Registers, Combiners with Memory, and 2-Adic Span[J]. Journal of Cryptology, 1997, 10(2): 111-147.

[15] Krasikov I. On integral zeros of Krawtchouk polynomials[J]. Journal of Combinatinal Theory: Series A, 1996,74(1):71-99.

[責任編輯:王輝]

A fast algorithm for computing arithmetic Walsh spectra of symmetric Boolean functions

ZHAO Qinglan1, ZHENG Dong1,2

(1.School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;2.National Engineering Laboratory for Wireless Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to improve the algorithm efficiency for computing the arithmetic Walsh spectra of symmetric Boolean functions, Krawtchouk polynomial is used to study arithmetic Walsh transform of symmetric Boolean functions. Firstly the relationship of Krawtchouk polynomial and arithmetic Walsh transform of symmetric Boolean functions is discussed. Secondly it is proved that the arithmetic Walsh spectra of symmetric Boolean functions has simple expression related to Krawtchouk polynomial. Finally a fast algorithm for computing the arithmetic Walsh spectra of symmetric Boolean functions using properties of Krawtchouk polynomial is presented. This algorithm has low time and space complexity.

Boolean functions, Walsh transform, 2-adic number, Krawtchouk polynomial

10.13682/j.issn.2095-6533.2014.05.008

2014-07-07

國家自然科學基金資助項目(61272037, 61070249)；陜西省自然科學基礎研究計劃基金重點資助項目(2013JZ020);西安郵電大學青年基金資助項目(ZL2013-12)

趙慶蘭(1981-)，女，博士研究生，講師，從事密碼學與信息安全研究。E-mail:qlz@snnu.edu.cn 鄭東(1964-)，男，博士，教授，從事云計算安全與密碼學研究。E-mail: zhengdong@xupt.edu.cn

TN918 .1

A

2095-6533(2014)05-0040-06