基于跡函數的negabent函數構造

趙海霞 李文宇 韋永壯

①(桂林電子科技大學數學與計算科學學院，廣西高校數據分析與計算重點實驗室 桂林 541002)

②(廣西應用數學中心 桂林 541002)

③(廣西密碼學與信息安全重點實驗室 桂林 541002)

1 引言

在現代的對稱密碼體系中，布爾函數是不可替代的重要角色，其抵御攻擊的能力決定著密碼系統的安全性，故對安全性能良好的布爾函數的構造顯得極其重要。非線性度是布爾函數的最重要的性質之一，具有高非線性度的布爾函數能夠有效抵御最佳仿射攻擊。具有最高非線性度的布爾函數被稱為bent函數[1]，這類函數滿足n階擴散準則且其Walsh-Hadamard譜值的絕對值都是相等的，故bent函數是一類密碼學性質較好的布爾函數。然而bent函數也有不足之處，例如bent函數不平衡，且其變元個數只能是偶數。Riera等人[2]提出了與Walsh-Hadamard變換相類似的Nega-Hadamard變換，并借鑒bent函數的譜值定義，將在任意點處Nega-Hadamard譜值的絕對值都為1的函數稱為negabent函數。文獻[3,4]指出negabent函數具有最優的自相關性，存在平衡的negabent函數，且其變元個數可為偶數也可為奇數。與bent函數一樣，negabent函數在密碼學、編碼理論和組合設計中都有廣泛的應用，故negabent函數的性質和構造成為布爾函數研究領域的一個重點問題。

目前，國內外的學者對negabent函數進行了若干的研究。Parker等人[5]討論了既是bent又是negabent函數的構造和分類問題。St?nic?等人[6]描述了nega-Hadamard變換的詳細理論，研究了negabent函數級聯后的結果，并刻畫了M-M類中的bent-negabent函數所具備的特征。Stanica等人[7]繼續證明了n元negabent函數代數次數的上界為，提出了一種利用完全映射多項式構造bentnegabent函數的方法。Su等人[8]給出了函數是negabent的充要條件，基于該充要條件證明了negabent函數至多有4種nega-譜值，并提供了一種構造偶變元bent-negabent的方法。Mandal等人[9]對MM類中的bent-negabent函數的存在性問題進行了研究。Sarkar[10]首次給出了通過跡函數的形式表示negabent函數，刻畫了一類negabent 2次單項式函數，并給出了在M-M類中bent-negabent函數的充要條件。Zhou等人[11]利用跡函數給出了negabent函數的等價定義，分別構造了2次和3次的negabent單項式函數族。Wu等人[12]利用了2次置換的復合逆和3次置換的復合逆構造了一類新的negabent函數。Jiang等人[13]利用完全置換多項式給出了一類2次bent-negabent函數的充要條件，利用布爾函數和向量布爾函數組合的方法，計算了廣義間接和的nega-Hadamard變換。Guo等人[14]分別通過間接與直接的方法對bent-negabent函數進行構造，并研究了多輸出布爾函數的nega-Hadamard譜值。文獻[15]利用基于跡函數定義的Kerdock碼構造了2次bent-negabent函數族。跡函數是有限域上的一類線性函數，利用跡函數不僅可以更好地描述出negabent函數的性質，而且較其他方法而言，利用跡函數構造negabent函數也更加簡便。

本文內容的安排如下：第2節介紹了布爾函數及有限域上的跡函數的基本知識；第3節給出了利用跡函數構造negabent函數的方法，并解決了所構造的negabent函數的計數問題；第4節總結。

2 預備知識

本文用F2表示只有兩個元素0和1的有限域，F2上定義了加法和乘法兩種2元運算，表示2元域上的n維向量空間。n元布爾函數是到F2上的映射[16]，用Bn表示所有的n元布爾函數構成的集合。

定義1[16]設f(x)∈Bn,x=(x1,x2,...,xn)∈，稱多項式

為f(x)的代數正規型(Algebraic Normal Form,A N F)，這里的αe ∈F2,e=(e1,e2,...,en)∈F2n,f(x)的代數次數為deg(f)=max{wt(e)|αe ?=0,e ∈F2n}，其中wt(e)為e的漢明重量，是e的分量中1的個數。代數次數至多為1的函數稱為仿射函數。

設f(x)∈Bn，若|{x ∈F2n|f(x)=0}|=2n-1，則稱該函數是一個平衡的布爾函數。兩個布爾函數f(x)∈Bn,g(x)∈Bn之間的漢明距離為f ⊕g的漢明重量，記作d(f,g)，即d(f,g)=wt(f ⊕g)。

定義4[7]設f(x)∈Bn，若對任意的μ∈，均有|Nf(μ)|=1，則稱函數f(x)為negabent函數。

定義5[17]設Q=Fqn,K=Fq為有限域，定義Fqn上的函數為

稱此函數為Fqn上的跡函數。

跡函數具備下述性質：

定義6[17,18]設Fqn為有限域，多項式z(x)∈Fqn[x]，若由z(x)誘導的多項式函數是Fqn到Fqn上的一個雙射(置換)，則稱z(x)是有限域Fqn上的一個置換多項式。

3 兩類negabent函數的構造

本節使用了有限域上的跡函數構造了兩類negabent函數，并討論了所構造的negabent函數的計數問題。

在第2類negabent函數的構造中，同樣基于引理2中置換多項式的結論，利用跡函數構造negabent函數。與所構造的第1類negabent函數相比較，第2類negabent函數中可調的參數更多，因此由第2種構造方法可獲得更多negabent函數。

命題2當λ ?=1時，定理3中所構造的negabent函數數量的下界為2n-1[(2n-1-2)(2n-1-3)+2n-1-4]。

證明如定理3所示，f(x)中的u,v,m,d互不相同，確定有序數組(u,v,m,d)數量即可得到所構造出的negabent函數數量，將附表中的10元向量歸納可得：由定理3中的方法構造出的negabent函數的計數下界為2n-1[(2n-1-2)(2n-1-3)+2n-1-4]。

本文借鑒文獻[12] 中利用有限域上的跡函數構造negabent函數的思想方法，通過增加可調參數獲得了更多的negabent函數。文獻[12]與本文所構造的negabent函數數量如表1所示。

表1 不同調參方案所構造函數數量

4 結論

Negabent函數作為bent函數的一種拓展，在密碼學與編碼理論中有著廣泛應用，因此構造negabent函數具有重要實際意義。本文將跡函數與置換多項式相結合，提出了兩種構造negabent函數的方法，解決了所構造出來的negabent函數的計數問題。研究結果表明，利用本方法可以獲得大量的negabent函數。