黃景廉，張椿玲

(西北民族大學(xué)電氣工程學(xué)院，甘肅蘭州730030)

旋轉(zhuǎn)對稱布爾函數(shù)的最高非線性度與最優(yōu)代數(shù)免疫

黃景廉，張椿玲

(西北民族大學(xué)電氣工程學(xué)院，甘肅蘭州730030)

文章研究旋轉(zhuǎn)對稱布爾函數(shù)的最高擴(kuò)散次數(shù)、最高非線性度和代數(shù)免疫性等問題.利用導(dǎo)數(shù)和e-導(dǎo)數(shù)證明了元數(shù)為偶數(shù)的完全2次齊次旋轉(zhuǎn)對稱布爾函數(shù)的非線性度達(dá)到布爾函數(shù)的最大非線性度.又利用導(dǎo)數(shù)從n次擴(kuò)散性角度，證明了旋轉(zhuǎn)對稱Bent函數(shù)的存在性，即驗(yàn)證了最大非線性度旋轉(zhuǎn)對稱布爾函數(shù)的存在性.另外，利用導(dǎo)數(shù)證明了最優(yōu)代數(shù)免疫旋轉(zhuǎn)對稱布爾函數(shù)的存在性，并給出了用Bent函數(shù)構(gòu)造最優(yōu)代數(shù)免疫旋轉(zhuǎn)對稱布爾函數(shù)的方法.利用導(dǎo)數(shù)還得出了一類旋轉(zhuǎn)對稱布爾函數(shù)的相關(guān)免疫性.

旋轉(zhuǎn)對稱布爾函數(shù)；Bent函數(shù)；導(dǎo)數(shù)；非線性度；相關(guān)免疫性；最優(yōu)代數(shù)免疫

0 引言

代數(shù)免疫性、最優(yōu)代數(shù)免疫、非線性度、最高非線性度、擴(kuò)散性、高次擴(kuò)散性、相關(guān)免疫性都是密碼函數(shù)非常重要的安全性質(zhì).對這些性質(zhì)的研究一直都在進(jìn)行，特別是近年來提出的抵抗代數(shù)攻擊的代數(shù)免疫性[1]，更是當(dāng)前的研究熱點(diǎn)[2～7].除此之外，其他密碼學(xué)性質(zhì)，如擴(kuò)散性、相關(guān)免疫性和非線性度等，在構(gòu)造布爾函數(shù)時也需要考慮.

Bent函數(shù)和旋轉(zhuǎn)對稱布爾函數(shù)都是密碼學(xué)中的重要函數(shù)，是密碼學(xué)界一直在認(rèn)真研究的對象[8～14].旋轉(zhuǎn)對稱布爾函數(shù)中是否也含有Bent函數(shù)，如何用Bent函數(shù)構(gòu)造出最優(yōu)代數(shù)免疫旋轉(zhuǎn)對稱布爾函數(shù)等問題是需要研究的重要問題.如果以導(dǎo)數(shù)和e-導(dǎo)數(shù)作為研究工具，這些問題就較容易解決.本文將利用導(dǎo)數(shù)和e-導(dǎo)數(shù)來討論旋轉(zhuǎn)對稱布爾函數(shù)的非線性度、擴(kuò)散性、代數(shù)免疫性、旋轉(zhuǎn)對稱Bent函數(shù)的存在性和結(jié)構(gòu)、最優(yōu)代數(shù)免疫旋轉(zhuǎn)對稱布爾函數(shù)的存在性及構(gòu)造等問題.

1 預(yù)備知識

布爾函數(shù)的導(dǎo)數(shù)是人們熟知的[15].需要給出布爾函數(shù)e-導(dǎo)數(shù)的概念.對e-導(dǎo)數(shù)與導(dǎo)數(shù)的關(guān)系及e-導(dǎo)數(shù)的性質(zhì)，可參閱參考文獻(xiàn)[16～18].

定義3[15]n元布爾函數(shù)f(x)=f(x1,x2,…，xn)∈GF(2)GF(2)n對r(1≤r≤n)個變元xi1,xi2,…，xir(1≤i≤n)的導(dǎo)數(shù)(偏導(dǎo)數(shù))表示和定義為

?f(x)/?(xi1,xi2,…，xir)

(1)

當(dāng)r=1時，式(1)即為f(x)=f(x1,x2,…，xn)對單個變元xi的導(dǎo)數(shù)，記為df(x)/dxi(i=1,2,…,n).經(jīng)簡單的計(jì)算化簡，可得到如下便于使用的形式：

定義4[16～18]n元布爾函數(shù)f(x)=f(x1,x2,…，xn)∈GF(2)GF(2)n對r(1≤r≤n)個變元xi1,xi2,…，xir(1≤i≤n)的e-導(dǎo)數(shù)(e-偏導(dǎo)數(shù))表示和定義為

ef(x)/e(xi1,xi2,…，xir)

(2)

當(dāng)r=1時，式(2)即為f(x)=f(x1,x2,…，xn)對單個變元xi的e-導(dǎo)數(shù)，記為ef(x)/exi(i=1,2,…,n).經(jīng)簡單的計(jì)算化簡，可得到如下便于使用的形式：

定義5 若f(x)∈GF(2)GF(2)n對所有α∈GF(2)n(1≤wt(α)≤k,k∈I+)，都有wt(f(x+α)+f(x))=2n-1，則稱f(x)滿足k次擴(kuò)散準(zhǔn)則，或f(x)是k次擴(kuò)散函數(shù).

Bent函數(shù)是密碼學(xué)中重要的函數(shù)，也能用擴(kuò)散準(zhǔn)則來定義,即稱函數(shù)f(x)∈GF(2)GF(2)n為Bent函數(shù)，當(dāng)且僅當(dāng)f(x)是n次擴(kuò)散函數(shù).

定義6 對任意滿足1≤wt(ω)≤m的n元向量ω=(ω1,ω2，…，ωn)∈GF(2)n，函數(shù)f(x)=f(x1,x2,…，xn)∈GF(2)GF(2)n都有wt(f(x)+ωx)=2n-1(ωx=ω1x1+ω2x2+…+ωnxn)，則稱f(x)為m階相關(guān)免疫函數(shù)，m稱為階數(shù).

根據(jù)上述定義，可容易得到引理1～引理3.

引理1 布爾函數(shù)f(x)∈GF(2)GF(2)n是k次擴(kuò)散函數(shù)的充分必要條件，對一切1≤r≤k，都有

wt(?f(x)/?(xi1,xi2,…，xir))=2n-1(i∈I+,r∈I+,1≤i1≤i2≤…≤ik≤k≤n).

引理2 對任意布爾函數(shù)f(x)∈GF(2)GF(2)n，有

f(x)=f(x)?f(x)/?(xi1,xi2,…，xir)+ef(x)/e(xi1,xi2,…，xir)

=f(x)df(x)/dxj+ef(x)/exj

(1≤i≤n,1≤r≤n,1≤i1≤i2≤…≤ir≤n,j∈I+)

2 完全2次齊次旋轉(zhuǎn)對稱布爾函數(shù)與Bent函數(shù)、相關(guān)免疫函數(shù)

定理1先討論完全2次齊次旋轉(zhuǎn)對稱布爾函數(shù).

證明 由引理2，并經(jīng)簡單計(jì)算推導(dǎo)，有

所以有

所以有

證畢.

對n為偶數(shù)，1≤r≤n，當(dāng)r為奇數(shù)時，有

而當(dāng)r為偶數(shù)時，有

推論2 偶數(shù)元完全2次齊次旋轉(zhuǎn)對稱布爾函數(shù)是n次擴(kuò)散函數(shù).

定理2 元數(shù)n≥5且n為奇數(shù)時，完全2次齊次旋轉(zhuǎn)對稱布爾函數(shù)是相關(guān)免疫函數(shù).

證畢.

3 旋轉(zhuǎn)對稱布爾函數(shù)與最優(yōu)代數(shù)免疫函數(shù)

高非線性度是提高密碼系統(tǒng)抵抗線性攻擊能力的布爾函數(shù)的重要性質(zhì).定理3首先討論利用2可分解為2個函數(shù)乘積的H布爾函數(shù)，構(gòu)造出具有較高非線性度的相關(guān)免疫H布爾函數(shù)的問題.

證畢.

推論3 兩個完全齊次旋轉(zhuǎn)對稱布爾函數(shù)的乘積也必是完全齊次旋轉(zhuǎn)對稱布爾函數(shù).

證畢.

(1)

證畢.

4 結(jié)語

[1] Courtois, N., and Meier, W. Algebraic attacks on stream ciphers with linear feedback[C]. Advances in Cryptology-EUROCRYPT 2003, Warsaw, Poland, 2003, LNCS, 2656:345-359.

[2] Carlet C and Zeng X Y. Further properties of several classes of Boolean functions with optimum algebraic immunity[J].Designs, Codes and Cryptography, 2009, 52(3): 303-338.

[3] Carlet C. A method of construction of balanced functions with optimum algebraic immunity[C]. Proceedings of the First International Workshop on Coding and Cryptography, Fujian, 2007，25-43.

[4] Li Y, Yang M, and Kan H B. Constructing and counting Boolean functions on even variables with maximum algebraic immunity[J]. IEICE Transactions on Fundamentals, 2010, 93-A(3): 640-643.

[5] Rizomiliotis P. On the resistance of Boolean functions against algebraic attacks using univariate polynomial representation[J]. IEEE Transactions on Information Theory, 2010, 56(8):4014-4024.

[6] Tu Z R and Deng Y P. A class of 1-resilient function with high nonlinearity and algebraic immunity[R]. Ryptography ePrint Archive, Report，2010, 2010/179.

[7] Wang Q, Peng J, Kan H, et al.. Constructions of cryptographically significant Boolean functions using primitive polynomials[J]. IEEE Transactions on Information Theory, 2010, 56(6): 3048-3053.

[8] 李春雷，張煥國，曾祥勇等. 一類Bent函數(shù)的二階非線性度下界[J]. 計(jì)算機(jī)學(xué)報, 2012, 35(8):1588-1593.

[9] Sarkar S, Gangopadhyay S. On the second order nonlinearity of a cubic Maiorana-McFarland Bent Functions[J]. International Journal of Foundations of Computer Science, 2010, 21(3):243-254.

[10] Su S H, Tang X H. Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity[J]. Designs, Codes and Cryptography, 2014, 71(2): 183-199.

[11] 陳銀冬, 張亞楠, 田威. 具有最優(yōu)代數(shù)免疫度的偶數(shù)元旋轉(zhuǎn)對稱布爾函數(shù)的構(gòu)造[J]. 密碼學(xué)報,2014, 1(5): 437-448.

[12] Sarkar S, Maitra S. Construction of rotation symmetric Boolean functions with optimal algebraic immunity[J]. Computation Systems, 2009, 12(3): 267-284.

[13] Fu S, Qu L, Li C, et al. Balanced rotation symmetric Boolean functions with maximum algebraic immunity[J]. IET Information Security, 2011, 5(2): 93-99.

[14] 董德帥, 李超, 屈龍江等. 偶變元MAI 旋轉(zhuǎn)對稱布爾函數(shù)[J]. 國防科技大學(xué)學(xué)報, 2012, 34(4): 85-89.

[15] 溫巧燕,鈕心忻,楊義先. 現(xiàn)代密碼學(xué)中的布爾函數(shù)[M].北京:科學(xué)出版社,2000.

[16] Li, W., Wang, Z., Huang, J..The e-derivative of boolean functions and its application in the fault detection and cryptographic system[J]. Kybernetes, 2011, 40(5-6):905-911.

[17] 黃景廉,王卓. H布爾函數(shù)的相關(guān)免疫性與重量的關(guān)系[J]. 通信學(xué)報, 2012, 33(2):110-118.

[18] 趙美玲. 基于布爾e導(dǎo)數(shù)的特殊邏輯函數(shù)檢測方法[J]. 浙江大學(xué)學(xué)報(理學(xué)版), 2014, 41(4):424-426.

The Hghest Nonlinearity and Optimal Algebraic Immunity of Rotation Symmetric Boolean Functions

HUANG Jing-lian，ZHANG Chun-ling

(College of Electrical Engineering, Northwest University for Nationalities, Lanzhou 730030, China)

The problems of RSBFs including the highest degree of propagation, the highest nonlinearity and algebraic immunity were studied in this article. Using the derivative and the e-derivative of the Boolean functions, the nonlinearity of quadratic homogeneous RSBFs was proved with even variables reaches the highest one of Boolean functions. Additionally, the existence of rotation symmetric Bent functions was verified using the derivative from n-degree propagation. That indicated that the existence of RSBFs with the highest nonlinearity had been proved. Moreover the paper proved that the existence of RSBFs with the optimal algebraic immunity, and provided the method of constructing RSBFs with the optimal algebraic immunity using Bent functions. The correlation immunity of a class of RSBFs using the derivative was also obtained.

RSBFs; Bent function; Derivative; Nonlinearity; Ccorrelation immunity; Optimal algebraic immunity

2015-05-20

黃景廉(1968—)，女，四川南充人，教授，主要從事計(jì)算機(jī)網(wǎng)絡(luò)通訊安全方面的研究.

O231；TP309

A

1009-2102(2015)02-0001-07