旋轉(zhuǎn)對稱布爾函數(shù)線性結(jié)構(gòu)的2個公開問題

趙亞群，李旭

（1. 信息工程大學(xué) 四院，河南 鄭州 450002；2. 信息工程大學(xué) 數(shù)學(xué)工程與先進(jìn)計算國家重點(diǎn)實驗室，河南 鄭州 450002）

1 引言

旋轉(zhuǎn)對稱布爾函數(shù)(RSBF, rotation symmetric boolean function)是一類具有特殊代數(shù)結(jié)構(gòu)的布爾函數(shù)，由Pieprzyk和Qu[1]最先提出并應(yīng)用于散列算法中。由于其良好的結(jié)構(gòu)特性和在散列算法中廣泛的應(yīng)用，RSBF受到了極大的關(guān)注，RSBF的密碼學(xué)性質(zhì)一直是研究的熱點(diǎn)問題[2~6]。其中，線性結(jié)構(gòu)是度量布爾函數(shù)安全性的一個重要指標(biāo)，具有非零線性結(jié)構(gòu)的布爾函數(shù)是密碼學(xué)中的一類“弱函數(shù)”。因此，研究RSBF的線性結(jié)構(gòu)對于密碼算法的安全性設(shè)計是很有意義的。

Elsheh在文獻(xiàn)[7]中系統(tǒng)地研究了RSBF的線性結(jié)構(gòu)，證明了 1n- 次RSBF不存在除全0和全1的線性結(jié)構(gòu)，并提出了2個公開問題：對任意的 3n＞ ，n-1次偶變元平衡 RSBF和 n - 2次奇變元 RSBF均不存在非零線性結(jié)構(gòu)。當(dāng) n ≤ 1 0時，Elsheh通過計算機(jī)驗證了這2個公開問題的正確性。在此基礎(chǔ)上，本文進(jìn)一步研究了RSBF的線性結(jié)構(gòu)，完全證明了公開問題1，給出了公開問題2成立的充分條件以及不成立的必要條件。

2 預(yù)備知識

12n1x2,… ,xn)∈F2。記Bn為所有n變元布爾函數(shù)構(gòu)成的集合。

任意一個 Bn中的布爾函數(shù) f ( x)都可以唯一地表示成 F2上的多變元多項式。

其中，aI∈F2，式(1)稱為f( x)的代數(shù)正規(guī)型（ANF,algebraic normal form）。定義布爾函數(shù) f ( x)的代數(shù)次數(shù)deg f為ANF中系數(shù)非零次數(shù)最高的單項式次數(shù)。若deg f≤ 1，則稱 f ( x)為仿射函數(shù)，An表示 Bn中的全體仿射函數(shù)。定義 f( x)∈ Bn的支撐集，那么 f ( x)的漢明重量表示集合M的元素個數(shù))。若wt( f) = 2n-1，則稱 f ( x)為平衡函數(shù)。對任意的x = (x1, x2, … , xn)∈，定義x的支撐集為 W S( x)=那么x的漢明重量 w t( x)=對任意的 I ? ｛ 1, 2, … ,n ｝ ，有

關(guān)于彈性(相關(guān)免疫)函數(shù)的譜特征有如下定義。

引理1[8]設(shè) f ( x)∈ Bn，f( x)具有m階彈性(相關(guān)免疫性)，當(dāng)且僅當(dāng)對任意的 w ∈Fn且

20 ≤ w t( w) ≤ m (1 ≤ w t( w) ≤ m )時，有 S(f)(w) = 0 。

定義 2 設(shè) f ( x)∈ Bn，s∈，記Δsf( x)=f( x) ⊕ f ( x ⊕ s )。若對所有的 x ∈，都有Δf( x)=

sΔsf ( 0)=常數(shù)(0或1)，則稱s為 f ( x)的一個線性結(jié)構(gòu)。

定義 3 設(shè) n為正整數(shù)，對任意的 x = (x1,和0≤k≤n -1，定義，其中，

3 2個關(guān)于RSBF線性結(jié)構(gòu)的公開問題

首先，給出文獻(xiàn)[7]中關(guān)于RSBF的一些基本性質(zhì)。

引理2 設(shè) f ( x)∈ Bn為RSBF，則有如下描述。

1) 若 α ∈F2n為f( x)的一個線性結(jié)構(gòu)，那么對任意的 β ∈Gn( α)， β 仍為f( x)的線性結(jié)構(gòu)。

2) 若deg f = n ，那么 f ( x)不存在非零線性結(jié)構(gòu)。

3) 若deg f = n - 1 ，那么 f ( x)不存在除0和1以外的線性結(jié)構(gòu)。

在文獻(xiàn)[7]的最后，Elsheh通過對n元RSBF的考察，提出了2個關(guān)于RSBF線性結(jié)構(gòu)的公開問題：對任意的 n ＞ 3 ，1) 代數(shù)次數(shù)為 n -1的偶變元平衡RSBF不存在非零線性結(jié)構(gòu)；2) 代數(shù)次數(shù)為 n - 2的奇變元RSBF不存在非零線性結(jié)構(gòu)。

注：由于任意向量均為線性布爾函數(shù)的線性結(jié)構(gòu)，因此，在討論布爾函數(shù)的線性結(jié)構(gòu)時，所涉及的布爾函數(shù)均默認(rèn)為非線性布爾函數(shù)。故文獻(xiàn)[7]提出的2個公開問題中，有 n ＞ 3 的條件。

首先，給出公開問題1的證明。

引理 3[9]設(shè)，那么(i=0或 1)的充分必要條件是對任意的 w ∈且ws= i⊕ 1，都有 S（f）（w）= 0 。

引理4[9]設(shè) f ( x)∈ Bn具有m階相關(guān)免疫性，degf = k ，則k + m ≤ n 。若設(shè) f （ x） 是平衡的，且1≤m ≤ n -2，則 k +m≤n-1。

定理1 設(shè) f ( x)∈ Bn為RSBF(n為偶數(shù)且n＞3)，若deg f = n -1， w t( f) = 2n-1，那么 f ( x)不存在非零線性結(jié)構(gòu)。

證明 根據(jù)引理 2中的 3)，只需證明 1不是f( x)的線性結(jié)構(gòu)。

在討論公開問題2之前，先引入FP(fast point)的概念及其部分性質(zhì)。

定義4[10]設(shè)＜ d eg f-1，則稱c為 f ( x)的一個FP。

可見，非線性布爾函數(shù) f ( x)的任一線性結(jié)構(gòu)均為 f ( x)的一個FP。若c=0，則稱c為 f ( x)的平凡FP；否則，稱c為 f ( x)的非平凡FP。 f ( x)的全體FP構(gòu)成上的一個線性子空間，也就是說，若的2個FP，那么α⊕β仍為f( x)的FP。

引理5[10]設(shè) f ( x)∈ Bn(n≥3)，f( x)的ANF中只含有代數(shù)次數(shù)為 n - 2 的單項式，記其單項式的系數(shù)為存在Bn且 只含有n-2次 項}。對任意的f( x)∈F，f( x)有且只有3個非平凡FP，且其中任意的2個非平凡滿足：

注：下文中出現(xiàn)的 ri,j均表示 n - 2 次單項式的系數(shù)。

定理 2 設(shè) f ( x)∈ Bn，degf=k(k＞1)，令f( x) = g( x) ⊕ h ( x)，其中， g ( x)為 f ( x)中所有代數(shù)次數(shù)為k的單項式之和，那么 f ( x)的任意非零線性結(jié)構(gòu)均為 g （ x）的非平凡FP。

證明 deg f = d egg = k ，deg h ≤k-1。易知，對任意的，有

設(shè) f(x) ∈ Bn為RSBF，degf = n - 2 ，令f( x) = g( x) ⊕ h ( x)，其中， g ( x)為 f ( x)中所有代數(shù)次數(shù)為 n-2的單項式之和，那么 g ( x)和 h( x)均為RSBF，且deg g = n - 2 ，deg h ≤n-3。

注：下文中出現(xiàn)的 g ( x)、 h ( x)和 f ( x)均具有如上關(guān)系。

定理 3 設(shè) f ( x) ∈ Bn為RSBF(n為奇數(shù)且n＞ 3 )，若deg f = n - 2 ，那么：

證明 首先，證明 1不是 f ( x)的線性結(jié)構(gòu)。g（ x）為只含有代數(shù)次數(shù)為 n - 2 的單項式的RSBF，不妨設(shè) n - 2 次項出現(xiàn)，又 n為奇數(shù)，那么 n - 2 次項j≤n-1)均出現(xiàn)，即r1+j,i+j=1 (0≤j≤n-1)。

注：在不引起混淆的情況下，若i + j ＞ n ，筆者仍然用i+ j表示（i+ j） modn。

假設(shè)1是 f ( x)的線性結(jié)構(gòu)，由定理2可知，1是 g ( x)的一個非平凡FP。由引理5可知 g ( x)存在其他2個非平凡FP，設(shè)其中的一個為 c ∈F2n，根據(jù)式(3)有

2f( x)不存在非零線性結(jié)構(gòu)。

n 1,1)k)={(0,1,1)k,(1,0,1)k,(1,1,0)k}。事實上，筆者知道，那么 α ∈Gn((0,0,1)k)或Gn((0,1,1)k)。若 α ∈Gn((0,0,1)k)={(0,0,1)k,(0,1,0)k, (1,0,0)k}，有(0,0,1)k⊕ ( 0,1,0)k⊕ ( 1,0,0)k=1仍為 g ( x)的非平凡FP矛盾。可知， α ∈Gn((1,0,0)k)不是f( x)的線性結(jié)構(gòu)。

若 α ∈Gn((0,1,1)k)為f( x)的線性結(jié)構(gòu)，那么Gn((0,1,1)k)為 g ( x)的非平凡 FP。根據(jù)式(3)可得：f( x)中代數(shù)次數(shù)為 n - 2 的單項式的系數(shù)滿足下式

4 結(jié)束語

本文利用了FP的一些性質(zhì)，討論了文獻(xiàn)[7]提出的2個關(guān)于RSBF線性結(jié)構(gòu)的2個公開問題。非線性布爾函數(shù)的線性結(jié)構(gòu)必定為其FP，但布爾函數(shù)的非平凡 FP不一定是其非零線性結(jié)構(gòu)。討論線性結(jié)構(gòu)和FP之間的關(guān)系以及對公開問題2的完全證明將是下一步需要進(jìn)行的工作。

functions with maximum algebraic immunity[J]. Information Security IET, 2011, 5(2):93-99.

[5] STANICA P, MAITRA S. Results on rotation symmetric bent and correlation immune Boolean functions[A]. Fast Software Encryption Workshop (FSE 2004)[C]. Delhi, India, 2004. 161-177.

[6] MAXIMOV A, HELL M, MAITRA S. Plateaued rotation symmetric Boolean functions on odd number of variables[A]. Proceedings of the First Workshop on Boolean Functions: Cryptography and Applications[C]. Rouen, France, 2005.

[7] ELSHEH E. On the linear structures of cryptographic rotation symmetric Boolean functions[A]. Proceedings of the 9th International Conference for Young Computer Scientists(ICYCS '08)[C]. Zhangjiajie,China, 2008. 2085-2089.

[8] XIAO G Z, MASSEY J L. A spectral characterization of correlation-immune function[J]. IEEE Transactions on Information Theory, 1988, 34(3):569-571.

[9] 李世取, 曾本勝, 廉玉忠等. 密碼學(xué)中的邏輯函數(shù)[M]. 北京: 北京中軟電子出版社, 2003.LI S Q, ZENG B S, LIAN Y Z, et al. Logical Functions in Cryptography[M]. Beijing: China National Computer Software and Technology Service Corporation Press, 2003.

[10] DUAN M, LAI X, YANG M, et al. Distinguishing properties of higher order derivatives of Boolean functions[EB/OL]. http://eprint.iacr.org/2010/417, 2011.