旋轉對稱布爾函數線性結構的2個公開問題

趙亞群，李旭

（1. 信息工程大學 四院，河南 鄭州 450002；2. 信息工程大學 數學工程與先進計算國家重點實驗室，河南 鄭州 450002）

1 引言

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

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

2 預備知識

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

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

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

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

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

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

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

sΔsf ( 0)=常數(0或1)，則稱s為 f ( x)的一個線性結構。

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

3 2個關于RSBF線性結構的公開問題

首先，給出文獻[7]中關于RSBF的一些基本性質。

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

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

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

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

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

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

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

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

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

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

證明 根據引理 2中的 3)，只需證明 1不是f( x)的線性結構。

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

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

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

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

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

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

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

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

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

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

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

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

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

2f( x)不存在非零線性結構。

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)的線性結構。

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

4 結束語

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

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] 李世取, 曾本勝, 廉玉忠等. 密碼學中的邏輯函數[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.