郭夢(mèng)飛, 孫玉娟, 李路陽(yáng)

1.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 西安710071

2.密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100878

3.西安郵電大學(xué)通信與信息工程學(xué)院, 西安710121

1 引言

Bent 函數(shù)的概念由 Rothaus 于 1976 年提出[1], 它是非線性度最高的布爾函數(shù), 具有最好的抗線性攻擊的能力.遺憾是它不具有平衡性, 不能直接應(yīng)用于密碼系統(tǒng)中, 因此構(gòu)造具有高非線性度的平衡函數(shù)是密碼函數(shù)設(shè)計(jì)中重要的研究方向之一.半bent 函數(shù)的概念在 1994 年的亞密會(huì)上被提出[2], 它是非線性度最優(yōu)的 Plateaued 函數(shù) (三譜值函數(shù))[3], 這類(lèi)函數(shù)可以是平衡的, 可以具有偶數(shù)個(gè)變?cè)? 也可以具有奇數(shù)個(gè)變?cè)团紨?shù)元.對(duì)于變?cè)獋€(gè)數(shù)n 為奇數(shù)的半bent 函數(shù)可用于構(gòu)造具有低互相關(guān)值的序列簇, 該序列被稱(chēng)為Gold[4], 并且這種序列在密碼學(xué)和碼分多址(CDMA) 通信系統(tǒng)中具有廣泛的應(yīng)用.在Gold 的開(kāi)創(chuàng)性工作之后, 許多研究者致力于尋找新的半 bent 序列家族.近些年來(lái)已經(jīng)有了很多關(guān)于半 bent 函數(shù)的研究, 2004 年 Carlet 在 [5]中對(duì)布爾函數(shù)的二次構(gòu)造進(jìn)行研究, 并利用 bent 函數(shù)與半 bent 函數(shù)的間接和構(gòu)造了新的半 bent 函數(shù).2005 年 Charpin 和 Pasalic 從有限域上直接構(gòu)造了二次半 bent 函數(shù)[6].2009 年 Sun 和 Wu 給出了變?cè)獮榕紨?shù)的一些具體的二次半 bent 構(gòu)造和二級(jí)半 bent 構(gòu)造[7].2011 年 Mesnager 證明了零和二元 Kloosterman 和的四個(gè)值可以在偶數(shù)維變?cè)蠘?gòu)造半 bent 函數(shù)[8].2018 年Xie 和Luo 在[9]中, 從有限域上的利用多項(xiàng)式給出了二次半bent 函數(shù)的新構(gòu)造結(jié)構(gòu).在現(xiàn)有的關(guān)于半 bent 函數(shù)構(gòu)造的參考文獻(xiàn)中, 大部分都是從有限域上利用跡函數(shù)和冪函數(shù)導(dǎo)出半 bent 函數(shù)且變?cè)獋€(gè)數(shù)是偶數(shù), 也有很多利用已知函數(shù)進(jìn)行二次構(gòu)造而得.當(dāng)變?cè)獮槠鏀?shù)時(shí), 通過(guò)直接構(gòu)造半bent 函數(shù)的方法很少.本文從向量空間的角度出發(fā), 利用向量空間上的不相交線性碼直接構(gòu)造了一類(lèi)變?cè)獋€(gè)數(shù)為奇數(shù)的半 bent 函數(shù), 其構(gòu)造思路來(lái)自 PS 類(lèi) bent 函數(shù)[10].該構(gòu)造方式實(shí)現(xiàn)簡(jiǎn)單, 只需得到不相交線性碼和其對(duì)偶碼的生成矩陣便能給出函數(shù)的表達(dá)式, 并且可以快速的計(jì)算出函數(shù)真值.

此外, 多輸出布爾函數(shù) (向量值函數(shù)) 在特定的流密碼系統(tǒng)中使用, 可以使密鑰流的生成速率大大提高, 因此其實(shí)際中的應(yīng)用更多.目前關(guān)于多輸出函數(shù)的構(gòu)造大部分都是從有限域上開(kāi)展, 在向量空間上利用不相交線性碼構(gòu)造多輸出布爾函數(shù)文獻(xiàn)很少, 見(jiàn)文獻(xiàn)[11,12], 并且這些文獻(xiàn)中多輸出布爾函數(shù)的輸出維數(shù)最大只能達(dá)到輸入維數(shù)的一半, 且輸入變?cè)S數(shù)必須是偶數(shù).本文將利用不相交線性碼構(gòu)造一類(lèi)具有高非線性度平衡的 (n, n ?k) 多輸出布爾函數(shù), 其中n/3 < k < n/2, 保證了在一定的非線性度條件下, 其輸出維數(shù)大于輸入維數(shù)的一半, 且輸入變?cè)木S數(shù)可以為奇數(shù)也可以為偶數(shù).

本文內(nèi)容安排: 第 1 節(jié)介紹了構(gòu)造背景及主要構(gòu)造的基本思想.第 2 節(jié)主要介紹了布爾函數(shù)和線性碼部分的基礎(chǔ)知識(shí).第 3 節(jié)主要是具體的半 bent 函數(shù)構(gòu)造和證明, 以及多輸出布爾函數(shù)的構(gòu)造和證明.第4 節(jié)則是對(duì)本文工作的總結(jié)和下一步工作展望.

2 基礎(chǔ)知識(shí)

定義 1設(shè) Xn∈, 函數(shù) f(Xn) 是從到 F2的映射, 則函數(shù) f(Xn) 就是一個(gè) n 元布爾函數(shù).

一般來(lái)說(shuō), 布爾函數(shù)具有多種表達(dá)方式, 如真值表、序列、代數(shù)正規(guī)型、矩陣等方法.其中最常用的是代數(shù)正規(guī)型表示:

其中, 代數(shù)正規(guī)型中各項(xiàng)的系數(shù) λb∈ F2, 且 b=(b1,··· ,bn)∈.

令 Bn表示所有 n 元布爾函數(shù)的集合, f(Xn) ∈Bn.設(shè)函數(shù)的自變量 Xn= (x1,x2,··· ,xn) ∈,常數(shù)向量 α =(α1,α2,··· ,αn)∈, 這兩個(gè)向量的內(nèi)積的定義如下:

則布爾函數(shù)f 在α 點(diǎn)處的Walsh 譜的計(jì)算公式為:

定義 #supp(f)={Xn|f(Xn)=1, Xn∈} 為 f 的支撐集, #supp(f) 指的是 f 的漢明重量, 一個(gè) n 元的函數(shù) f 是平衡函數(shù)當(dāng)且僅當(dāng) #supp(f) = 2n?1, 或是 Wf(0n) = 0.這里 0n表示 n 長(zhǎng)的 0 向量.

定義 2一個(gè) n 元的布爾函數(shù) f 被稱(chēng)為半bent 函數(shù), 當(dāng)且僅當(dāng)對(duì)任意 α ∈

定義 3一個(gè)n 元的布爾函數(shù)f 的非線性度表示為Nf, 衡量了函數(shù)f 到所有仿射函數(shù)的最小距離,

其中A(n) 表示所有n 元仿射函數(shù)的集合, l 表示集合A(n) 中任意一個(gè)仿射函數(shù).經(jīng)過(guò)推導(dǎo), 得出Nf的計(jì)算公式為:

根據(jù) Parseval 恒等式[13],

所以任意一個(gè)布爾函數(shù)f 的非線性度Nf都滿足:

定義 4(n,m) 多輸出布爾函數(shù) F =(f1,··· ,fm) 的非線性度 NF定義為

其中 fi∈ Bn, c=(c1,··· ,cm) ∈, 即

定義 5對(duì)于一個(gè) [n,m]線性碼的集合 C = {C0,C1,··· ,CN?1}, 如果 0 ≤ i < j ≤ N ?1, 線性碼集合C 滿足條件

設(shè) S 和 T 是線性空間 V 的子空間, 稱(chēng)所有能表示成 x+y, 而 x ∈S, y ∈T 的向量組成的子集為 S與 T 之和, 并記為 S+T.且它們的和 S+T 也是V 的子空間.

引理 1[14](維數(shù)公式) 設(shè)S 和T 是線性空間V 的兩個(gè)子空間, 則

其中dim S 表示線性空間S 的維數(shù).

3 主要構(gòu)造

3.1 n為奇數(shù)時(shí) [n,k]不相交線性碼的構(gòu)造

本節(jié)將設(shè)計(jì)新的不相交線性碼, 為半bent 函數(shù)的構(gòu)造作鋪墊.文獻(xiàn)[15]給出了一種不相交線性碼劃分方式.參考這篇文章, 當(dāng)n 為奇數(shù)時(shí), 可以將按照下述方式進(jìn)行劃分.

構(gòu)造 1設(shè)n=2k+1,令中任意元素都可以寫(xiě)成(x,y).如果α 表示有限域 F2k+1中的一個(gè)本原元, 則 (1,α,··· ,αk) 就是有限域 F2k+1中的一組基.定義一個(gè)雙射 π : F2k+1→則 π 的映射關(guān)系可以表示為:

令 Gi(0 ≤ i ≤ 2k+1?2) 是 [n, k]生成矩陣, 其表達(dá)形式為

G2k+1?1是 [n,k]生成矩陣, 其表達(dá)形式為

G2k+1是 [n,k+1]生成矩陣, 其表達(dá)形式為

定理 1設(shè) n 為奇數(shù), n = 2k+1.則上述構(gòu)造的 Gi(0 ≤ i ≤2k+1) 生成的空間 Ei組成一個(gè)不相交碼集, 且劃分

證明:令 E0,E1,··· ,E2k+1?1, E2k+1是由上述生成矩陣生成的碼空間.

(1) 當(dāng) 0 ≤ i < j ≤ 2k+1?2 時(shí), 此時(shí) Gi, Gj的前 k 位是一個(gè)單位陣, 后 k+1 位是一個(gè)由 F2k+1中本原元表示 k 個(gè)線性無(wú)關(guān)向量, 對(duì)任意 0 ≤i

(2) 當(dāng) 0 ≤ i ≤ 2k+1? 2, 2k+1? 1 ≤ j ≤ 2k+1時(shí), 則 Gj的前 k 位或者后 k+1 位是全 0 矩陣, 顯然 Ei∩Ej={0};

(3) 當(dāng) 2k+1? 1 ≤ i < j ≤ 2k+1時(shí), Gj前 k 部分為 0 矩陣, Gi后 k+1 部分為 0 矩陣, 所以Ei∩Ej={0}, 且互相對(duì)偶, 因此上述構(gòu)造組成一個(gè)不相交碼集.

3.2 半bent函數(shù)構(gòu)造

令n=2k+1, 可以利用上述構(gòu)造1 中的不相交碼構(gòu)造一類(lèi)新的半bent 函數(shù).

構(gòu)造 2設(shè) E0,E1,··· ,E2k+1是由上述生成矩陣 G0,G1,··· ,G2k+1生成的碼空間, 所以對(duì)任意 0 ≤i

定理 2設(shè)f(Xn) 是構(gòu)造 2 所構(gòu)造的函數(shù), 則函數(shù) f(Xn) 是一個(gè)半 bent 函數(shù).

證明:令是上述不相交碼的對(duì)偶空間, 則對(duì)任意

(3) ω ·Xk+1是一個(gè)線性函數(shù), 且當(dāng) αk+1= ω 時(shí), 必有 α ∈ S.因?yàn)?αk+1= ω 的 α 取值共有2k個(gè), 且每個(gè) α 都會(huì)出現(xiàn)在2 個(gè)不同的所以上述定義的集合

(4) 下面來(lái)計(jì)算函數(shù)f 的譜值

又 αk+1·Xk+1≡ 0, 則

所以 Wf(α)=U1+U2+U3=0.

i.若 α 的后 k+1 位等于 ω 時(shí), 有 U1=2k, U2= ?2k, U3=2k+1, 所以 Wf(α)=2k+1.

ii.若 α 的后 k + 1 位不等于 ω, 有 U1+ U2∈ {0,±2k+1}, U3= 0, 所以 Wf(α) ∈{0,±2k+1}.

綜上 Wf(α) ∈ {0,±2k+1}, Nf= 2n?1? 2k+1?1= 2n?1? 2(n?1)/2, 所以 f(Xn) 是一個(gè)半 bent 函數(shù).

下面將給出一個(gè)例子, 對(duì)構(gòu)造2 進(jìn)行更詳細(xì)的闡述和解釋.

例 1設(shè) n=5, k =2.選擇有限域 F23上的一個(gè)本原多項(xiàng)式 h(x)=x3+x+1, 令 β 是本原多項(xiàng)式的一個(gè)根, 則可以將劃分為23+1 個(gè)不相交碼空間, 及其對(duì)偶空間生成矩陣如下

則B ={0,1,2,3,4,5,6,7}, B1={1,2,4,7}, B2={0,3,5,6}.

因此可以得出上述構(gòu)造的函數(shù)f 的真值表, 同時(shí)根據(jù)真值表易得出f 的譜值分布.見(jiàn)表1.

表1 f 的真值表和譜值分布Table 1 Truth table and Walsh spectra of f

根據(jù)表1 易驗(yàn)證

(1) 若 α 的后 3 位等于 ω 時(shí), Wf(α)=23.

(2) 若 α 的后 3 位不等于 ω, Wf(α)∈ {0,±23}.

綜上 Wf(α) ∈ {0,±23}, Nf=25?1? 23?1=12.所以 f 是一個(gè)半 bent 函數(shù).

注1對(duì)上述構(gòu)造和證明, 需要做出以下幾點(diǎn)說(shuō)明.

i 公式(2) 中集合B1是選取下標(biāo)小的對(duì)偶碼的下標(biāo)集; 公式(3) 中集合B2是選取下標(biāo)大的對(duì)偶碼的下標(biāo)集;

ii 但需要指出的是集合B1和B2不需要非要這樣規(guī)定, 可以有多種選擇, 只要保證當(dāng) α ∈且α ∈時(shí), 下標(biāo)i 和j 不放入同一個(gè)集合, 即不同時(shí)放入B1或B2即可.

iii 所以當(dāng)n=2k+1 時(shí), 每當(dāng)ω 固定時(shí)可以構(gòu)造出 22k種不同的半bent 函數(shù); 又因?yàn)棣?∈,所以一共可以構(gòu)造出(2k+1?1)×22k種不同的半bent 函數(shù).

3.3 (n, n ?k)多輸出布爾函數(shù)的構(gòu)造

本節(jié)將利用不相交碼和高非線性度置換來(lái)構(gòu)造一個(gè)(n, n ?k) 多輸出布爾函數(shù), 使得在保證一定非線性度的條件下, 輸出變量的個(gè)數(shù)大于輸入變量的個(gè)數(shù)的一半.

構(gòu)造 3令 n/3

令 Gi(0 ≤ i ≤ 2n?k? 2) 是 [n,k]生成矩陣, 其表達(dá)形式為

G2n?k?1 也是 [n,k]生成矩陣, 表達(dá)形式為

G2n?k是 [n,n ? k]生成矩陣, 其表達(dá)形式為

下面開(kāi)始構(gòu)造(n,n ?k) 出多輸出函數(shù), 且使輸出維度大于等于輸入長(zhǎng)度的一半.構(gòu)造方法參考文獻(xiàn)[11,12], 令 E0,E1,··· ,E2n?k是上述生成矩陣的生成空間, 設(shè)定義一個(gè)映射

顯然 φ(y)∈ {0,1,2,··· ,2n?k? 1}.對(duì)任意的上的置換函數(shù) H(y)=(h1(y),h2(y),··· ,hn?k(y)),定義{0,1,2,··· ,2n?k?1} 的子集Ai和其補(bǔ)集如下

易得Ai和的大小滿足|Ai|=2n?k?1.令G(Xn?k)=(g1(Xn?k),g2(Xn?k),··· ,gn?k(Xn?k)) 為一個(gè) (n ? k,n ? k) 置換, 其中 Xn?k=(xk+1,xk+2,··· ,xn).F(Xn)=(f1(Xn),f2(Xn),··· ,fn?k(Xn)),其中分量函數(shù)為

定理 3設(shè)F(Xn) 是構(gòu)造 3 所構(gòu)造的函數(shù), 則函數(shù)F(Xn) 是一個(gè) (n, n ?k) 平衡的多輸出函數(shù), 其輸出維度大于等于輸出的一半, 且非線性度滿足NF≥2n?1?2n?k+NG.

證明:令則 F(Xn) = (f1(Xn),f2(Xn),··· ,fn?k(Xn)), 其分量函數(shù)的非零線性組合可表示為

根據(jù)置換函數(shù)的性質(zhì), c1h1⊕ ···⊕cn?khn?k(y) 總是平衡的, 所以的 walsh 譜值為:

(1) 平衡性: 當(dāng) α=0n時(shí), 顯然 U =0; 又 gc是一個(gè)線性函數(shù), 有 Wgc(0n)=0, 所以 Wfc(0n)=0,即F 是一個(gè)平衡函數(shù).

(2) 輸出維數(shù): 由于 n/3

(3) 非線性度: 因?yàn)?max|U|=2k× 2n?k?k=2n?k, 代入得式 (4)

4 總結(jié)

本文中, 首先基于不相交線性碼構(gòu)造了一類(lèi)新的半 bent 函數(shù); 其次又利用不相交線性碼和高非線性度置換函數(shù)構(gòu)造了多輸出的布爾函數(shù), 并使其輸出維數(shù)大于輸入維數(shù)的一半.本文構(gòu)造的半 bent 函數(shù)相較于現(xiàn)有的半 bent 函數(shù)是完全不同的, 首次在向量空間上利用不相交線性碼直接構(gòu)造了奇數(shù)變?cè)碌陌?bent 函數(shù), 并且其構(gòu)造方法簡(jiǎn)單易于實(shí)現(xiàn).相較于文獻(xiàn) [12], 本文構(gòu)造的多輸出平衡布爾函數(shù)的輸出維數(shù)大于輸入維數(shù)的一半且變?cè)S數(shù)可奇可偶.但還有一些工作下一步需要解決, 怎么把本文中構(gòu)造的單輸出半bent 擴(kuò)展為多輸出半bent 函數(shù)? 當(dāng)0 ≤k ≤n/3 時(shí),怎么構(gòu)造(n, n?k)的多輸出布爾函數(shù)?