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

黃景廉，張椿玲

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

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

黃景廉，張椿玲

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

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

旋轉對稱布爾函數；Bent函數；導數；非線性度；相關免疫性；最優(yōu)代數免疫

0 引言

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

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

1 預備知識

布爾函數的導數是人們熟知的[15].需要給出布爾函數e-導數的概念.對e-導數與導數的關系及e-導數的性質，可參閱參考文獻[16～18].

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

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

(1)

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

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

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

(2)

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

定義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次擴散準則，或f(x)是k次擴散函數.

Bent函數是密碼學中重要的函數，也能用擴散準則來定義,即稱函數f(x)∈GF(2)GF(2)n為Bent函數，當且僅當f(x)是n次擴散函數.

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

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

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

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

引理2 對任意布爾函數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次齊次旋轉對稱布爾函數與Bent函數、相關免疫函數

定理1先討論完全2次齊次旋轉對稱布爾函數.

證明 由引理2，并經簡單計算推導，有

所以有

所以有

證畢.

對n為偶數，1≤r≤n，當r為奇數時，有

而當r為偶數時，有

推論2 偶數元完全2次齊次旋轉對稱布爾函數是n次擴散函數.

定理2 元數n≥5且n為奇數時，完全2次齊次旋轉對稱布爾函數是相關免疫函數.

證畢.

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

高非線性度是提高密碼系統抵抗線性攻擊能力的布爾函數的重要性質.定理3首先討論利用2可分解為2個函數乘積的H布爾函數，構造出具有較高非線性度的相關免疫H布爾函數的問題.

證畢.

推論3 兩個完全齊次旋轉對稱布爾函數的乘積也必是完全齊次旋轉對稱布爾函數.

證畢.

(1)

證畢.

4 結語

[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函數的二階非線性度下界[J]. 計算機學報, 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)代數免疫度的偶數元旋轉對稱布爾函數的構造[J]. 密碼學報,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 旋轉對稱布爾函數[J]. 國防科技大學學報, 2012, 34(4): 85-89.

[15] 溫巧燕,鈕心忻,楊義先. 現代密碼學中的布爾函數[M].北京:科學出版社,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布爾函數的相關免疫性與重量的關系[J]. 通信學報, 2012, 33(2):110-118.

[18] 趙美玲. 基于布爾e導數的特殊邏輯函數檢測方法[J]. 浙江大學學報(理學版), 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—)，女，四川南充人，教授，主要從事計算機網絡通訊安全方面的研究.

O231；TP309

A

1009-2102(2015)02-0001-07