優(yōu)良布爾函數(shù)的混合禁忌搜索算法

王維瓊，許豪杰，崔萌，謝瓊

（長(zhǎng)安大學(xué)理學(xué)院，陜西 西安 710064）

0 引言

對(duì)稱加密算法為保障數(shù)據(jù)存儲(chǔ)安全和通信網(wǎng)絡(luò)信息傳輸安全提供了有力的理論基礎(chǔ)和技術(shù)支撐。布爾函數(shù)是對(duì)稱加密算法的核心部件，其密碼學(xué)性質(zhì)的好壞直接決定了對(duì)稱密碼算法的安全性。為了抵抗各種攻擊，一個(gè)安全的密碼系統(tǒng)中所使用的布爾函數(shù)需滿足很多性質(zhì)，例如平衡性、高非線性度、低自相關(guān)性、高代數(shù)次數(shù)、高相關(guān)免疫階、高代數(shù)免疫度以及高抵抗快速代數(shù)攻擊能力等。但這些密碼學(xué)性質(zhì)之間存在著復(fù)雜的相互制約關(guān)系，因此，如何找到各方面密碼學(xué)性質(zhì)都較為優(yōu)良的布爾函數(shù)是密碼學(xué)領(lǐng)域的一個(gè)研究重點(diǎn)和難點(diǎn)。

目前，解決該問(wèn)題的方法主要有兩類，一類是借助代數(shù)和組合的理論進(jìn)行構(gòu)造，另一類是利用啟發(fā)式算法進(jìn)行搜索。學(xué)者們?cè)诓紶柡瘮?shù)構(gòu)造方面得到了許多結(jié)果[1-5]。Carlet 等[6]構(gòu)造了一類非線性度下界為且滿足最優(yōu)代數(shù)免疫度和高抵抗快速代數(shù)攻擊能力的n元平衡布爾函數(shù)，遺憾的是該類函數(shù)不具有一階彈性。Tu 等[7]基于PS 類函數(shù)構(gòu)造了一類具有最優(yōu)代數(shù)免疫度、最優(yōu)代數(shù)次數(shù)和高非線性度的平衡布爾函數(shù)，又稱Tu-Deng函數(shù)，而后Tu等[8]對(duì)Tu-Deng函數(shù)進(jìn)行了修改，得到了一類非線性度下界為且滿足一階彈性、最優(yōu)代數(shù)免疫度和最優(yōu)代數(shù)次數(shù)的布爾函數(shù)，但該類函數(shù)未考慮抵抗快速代數(shù)攻擊能力這一指標(biāo)。Zhang 等[9]通過(guò)對(duì)PS-類bent 函數(shù)進(jìn)行修改，構(gòu)造了一類變?cè)獋€(gè)數(shù)為偶數(shù)、非線性度為且滿足一階彈性的布爾函數(shù)，該結(jié)果是目前已知的偶變?cè)浑A彈性函數(shù)非線性度的最優(yōu)結(jié)果，遺憾的是該構(gòu)造方法僅適用于偶數(shù)變?cè)牟紶柡瘮?shù)。已知的構(gòu)造方法普遍存在的問(wèn)題是難以在構(gòu)造時(shí)兼顧所有的密碼學(xué)指標(biāo)，一般是針對(duì)少數(shù)幾個(gè)指標(biāo)來(lái)構(gòu)造函數(shù)，然后通過(guò)對(duì)某個(gè)特例進(jìn)行修改來(lái)滿足其他性質(zhì)。結(jié)合一些理論結(jié)果的啟發(fā)式搜索算法可以彌補(bǔ)構(gòu)造法的這一缺陷，得到代數(shù)構(gòu)造法無(wú)法得到的布爾函數(shù)，例如Saber 等[10]利用啟發(fā)式搜索算法得到了一些非線性度為240、彈性階為3、代數(shù)次數(shù)為5 的9 元布爾函數(shù)；Liu 等[11]利用模擬退火算法得到了一些非線性度為488、彈性階為2、代數(shù)次數(shù)為7 的10 元布爾函數(shù)。遺憾的是，文獻(xiàn)[10-11]中搜索到的布爾函數(shù)雖然足夠優(yōu)良，但是只針對(duì)9 元或10 元的布爾函數(shù)，不具有普適性。Yang 等[12]基于模擬退火算法和爬山算法對(duì)8～14 元的布爾函數(shù)進(jìn)行搜索，賈少帥等[13]基于引力搜索算法對(duì)8 元和9 元的布爾函數(shù)進(jìn)行搜索，都搜索到了具有一階彈性、較高非線性度、最優(yōu)代數(shù)次數(shù)、最優(yōu)（次優(yōu)）代數(shù)免疫度以及次優(yōu)抵抗快速代數(shù)攻擊能力的布爾函數(shù)。利用啟發(fā)式算法研究布爾函數(shù)的成果還有很多[14-18]，在此不再贅述。

本文期望在保證高非線性度和一階彈性這2 個(gè)最重要的密碼學(xué)指標(biāo)的前提下，獲得其他密碼學(xué)性質(zhì)也足夠優(yōu)良的布爾函數(shù)。以高非線性度、低自相關(guān)性、一階彈性為優(yōu)化目標(biāo)，以最優(yōu)代數(shù)次數(shù)、最優(yōu)代數(shù)免疫度、最優(yōu)（次優(yōu)）抵抗快速代數(shù)攻擊能力為約束條件，本文設(shè)計(jì)了新的代價(jià)函數(shù)，并在禁忌搜索（TS,tabu search）算法和爬山（HC,hill climbing）算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種混合禁忌搜索（HTS,hybrid tabu search）算法。應(yīng)用該算法對(duì)8～14 元的布爾函數(shù)進(jìn)行搜索，得到了若干滿足上述所有密碼學(xué)指標(biāo)的布爾函數(shù)。以隨機(jī)生成的平衡布爾函數(shù)作為初始輸入，除了10 元布爾函數(shù)需要嘗試多個(gè)輸入之外，本文算法可以搜索到滿足上述密碼學(xué)性質(zhì)的全部布爾函數(shù)，彌補(bǔ)了一些構(gòu)造方法受限于變?cè)獋€(gè)數(shù)的奇偶性，且構(gòu)造出的函數(shù)只能滿足部分密碼學(xué)性質(zhì)等缺陷。相較于已有的啟發(fā)式搜索算法，本文算法搜索到的布爾函數(shù)的密碼學(xué)性質(zhì)更為優(yōu)良，且數(shù)量更多。

1 預(yù)備知識(shí)

定義1設(shè)F2為二元域?yàn)镕2上的n維向量空間，n元布爾函數(shù)就是從到F2上的一個(gè)映射。

記Bn為所有n元布爾函數(shù)的集合，對(duì)任意的f∈Bn，可以用多種方法來(lái)表示，例如代數(shù)正規(guī)型、真值表等。 f 的代數(shù)正規(guī)型為

當(dāng)deg(f)=1時(shí)，稱 f 為仿射函數(shù)；當(dāng)deg(f)=1且f的常數(shù)項(xiàng)為0 時(shí)，稱f為線性函數(shù)；當(dāng)deg(f) ＞ 1時(shí)，稱f為非線性函數(shù)。

f 的真值表為

定義2對(duì)于任意的n元布爾函數(shù)f，其在處的Walsh 變換定義為

定義3對(duì)于任意的n元布爾函數(shù)f，其非線性度定義為

其中，An表示所有n元仿射函數(shù)的集合，dH(f ,l)=wt(f ⊕ l)表示f和l之間的漢明距離。由非線性度Nf與Walsh 變換的定義不難得出

定理1[20]Xiao-Massey 定理。一個(gè)n元布爾函數(shù)f是m階相關(guān)免疫的，當(dāng)且僅當(dāng)對(duì)任意的

若f滿足m階相關(guān)免疫的同時(shí)還是平衡的，則稱f為m階彈性布爾函數(shù)。

定理2[21]對(duì)任意的m階彈性函數(shù) f∈Bn，其代數(shù)次數(shù)deg(f)與彈性階m之間滿足如下關(guān)系

定義4對(duì)于任意的n元布爾函數(shù)f，其在處的自相關(guān)函數(shù)定義為

度量布爾函數(shù) f∈Bn自相關(guān)性的常用指標(biāo)為絕對(duì)值與平方和[22]，計(jì)算式分別為

不難證明，自相關(guān)平方和指標(biāo)與Walsh 變換之間有如下關(guān)系[23]

定義5設(shè) f ,h∈Bn，若fh=0，則稱h為f的零化子[24]。 f 的所有零化子的集合為

定義6設(shè) f∈Bn，其代數(shù)免疫度定義為[25]AI(f)=min{deg(h) | h∈AN(f) ∪AN(f ⊕1),h ≠ 0,h∈Bn}

FAA(f)越大，f抵抗快速代數(shù)攻擊能力越強(qiáng)。當(dāng)FAA(f)=n時(shí)，稱f抵抗快速代數(shù)攻擊能力為最優(yōu)的；當(dāng)FAA(f)=n-1時(shí)，稱f抵抗快速代數(shù)攻擊能力為次優(yōu)的。

2 混合禁忌搜索算法

禁忌搜索算法由Glover[27]于1986 年提出，并于1989 年和1990 年進(jìn)行進(jìn)一步的完善[28-30]。禁忌搜索算法基于對(duì)人類記憶功能的模仿，是一種迭代型的全局鄰域優(yōu)化算法。如何通過(guò)修改真值表來(lái)得到密碼學(xué)性質(zhì)更好的布爾函數(shù)本質(zhì)上屬于一個(gè)組合優(yōu)化問(wèn)題，而禁忌搜索算法在組合優(yōu)化等領(lǐng)域的成功應(yīng)用為這一問(wèn)題的解決提供了一種新思路。

禁忌搜索算法有許多優(yōu)點(diǎn)，例如選取優(yōu)良解的概率遠(yuǎn)大于選取劣解的概率；通過(guò)“禁忌”來(lái)避免算法陷入局部最優(yōu)；所有候選解的代價(jià)函數(shù)值都弱于當(dāng)前最優(yōu)解時(shí)，會(huì)接受“弱解”等。但同時(shí)禁忌搜索算法也有一定的缺點(diǎn)：一是對(duì)初始解有較強(qiáng)的依賴性；二是迭代過(guò)程是串行的，因此收斂速度較慢。爬山算法可以很好地解決這2 個(gè)問(wèn)題，它是一種基于貪心思想的算法，每次移動(dòng)都只接受比當(dāng)前解狀態(tài)更優(yōu)的解，到達(dá)某個(gè)“峰頂”就停止移動(dòng)。其優(yōu)點(diǎn)是實(shí)現(xiàn)過(guò)程較為簡(jiǎn)單且收斂速度快，缺點(diǎn)是很容易陷入局部最優(yōu)解，因?yàn)樗竭_(dá)的“峰頂”可能并不是全局最優(yōu)解。

結(jié)合TS 算法和HC 算法的優(yōu)點(diǎn)，本文提出了一種搜索能力更強(qiáng)、執(zhí)行速度更快的優(yōu)良布爾函數(shù)搜索算法——HTS 算法。一方面，由HC 算法生成初始解可以解決TS 算法對(duì)初始解的依賴性；另一方面，在TS 算法每次迭代結(jié)束后對(duì)當(dāng)前最優(yōu)解執(zhí)行HC 算法，可以提高HTS 算法的收斂速度。HTS算法流程如圖1 所示。

2.1 HTS 算法細(xì)節(jié)設(shè)計(jì)

2.1.1 鄰域解的選取

滿足平衡性是一階彈性布爾函數(shù)的必要條件。為了保證所生成的鄰域解的平衡性，本文中HTS算法的鄰域移動(dòng)方式采用2 -opt，即交換布爾函數(shù)真值表中2 個(gè)不同值的位置。對(duì)于一個(gè)n元布爾函數(shù)f，其2 -opt鄰域的大小為。若選取整個(gè)鄰域作為候選解，則計(jì)算量相當(dāng)龐大，算法迭代時(shí)間也會(huì)過(guò)長(zhǎng)，因此隨機(jī)性地從2 -opt鄰域中選取一部分解作為候選解是更好的選擇。

2.1.2 禁忌對(duì)象及禁忌表長(zhǎng)度的選取

禁忌對(duì)象通常可以選取解本身或者代價(jià)函數(shù)值等，由于選取代價(jià)函數(shù)值作為禁忌對(duì)象可能會(huì)錯(cuò)失優(yōu)良解，而且布爾函數(shù)真值表本身就是二進(jìn)制編碼形式，因此本文選取布爾函數(shù)本身作為禁忌對(duì)象。禁忌表的更新方式采用先入先出規(guī)則，即禁忌表每次更新時(shí)，將要禁忌的對(duì)象放到禁忌表的末端，而最早進(jìn)入禁忌表的禁忌對(duì)象將從禁忌表中釋放。禁忌長(zhǎng)度就是禁忌表的長(zhǎng)度，即處于禁忌表末端的禁忌對(duì)象在不被特赦的情況下被釋放時(shí)所經(jīng)歷的禁忌表更新次數(shù)。若禁忌長(zhǎng)度過(guò)大，則容易造成算法收斂速度過(guò)慢以及存儲(chǔ)量過(guò)大；若禁忌長(zhǎng)度過(guò)小，則容易使算法在尋優(yōu)時(shí)陷入“迂回”搜索。本文中HTS算法的禁忌長(zhǎng)度為其中num_cs 為候選解的個(gè)數(shù)。

2.1.3 特赦準(zhǔn)則

禁忌搜索算法中的“禁忌”不是絕對(duì)的禁止，當(dāng)存在一個(gè)優(yōu)于當(dāng)前最優(yōu)解的禁忌候選解時(shí)，特赦準(zhǔn)則的作用就是將這個(gè)禁忌候選解解禁，從而實(shí)現(xiàn)更優(yōu)的性能。本文中HTS 算法的特赦準(zhǔn)則是基于代價(jià)函數(shù)值的準(zhǔn)則，即若某個(gè)禁忌候選解的代價(jià)函數(shù)值優(yōu)于當(dāng)前最優(yōu)解，就從禁忌表中解禁此候選解并更新該候選解為當(dāng)前最優(yōu)解。

2.1.4 代價(jià)函數(shù)

代價(jià)函數(shù)決定了算法優(yōu)化的方向，對(duì)算法優(yōu)化的結(jié)果起著至關(guān)重要的作用。以高非線性度、低自相關(guān)性、一階彈性為優(yōu)化目標(biāo)，以最優(yōu)代數(shù)次數(shù)、最優(yōu)代數(shù)免疫度、最優(yōu)（次優(yōu)）抵抗快速代數(shù)攻擊能力為約束條件，本文提出了2 個(gè)代價(jià)函數(shù)。

圖1 HTS 算法流程

懲罰項(xiàng)中K的值不是定值，K值過(guò)大會(huì)導(dǎo)致除一階彈性外的其他密碼學(xué)性質(zhì)變差，K值過(guò)小會(huì)導(dǎo)致一階彈性缺失，因此K值的選取應(yīng)當(dāng)適中。對(duì)任意的滿足wt(α)=1的α 共有n個(gè)，在整個(gè)空間中的占比為可知，當(dāng)n＞ 1時(shí)，這個(gè)比值會(huì)隨著n的增大而減小，因此K值的大小應(yīng)隨著n的增大而增大。經(jīng)過(guò)反復(fù)實(shí)驗(yàn)，K值的選取如表1 所示。

表1 K 值的選取

由于在HTS 算法中使用代價(jià)函數(shù)cost1(f)所得到的一階彈性布爾函數(shù)的非線性度未達(dá)到期望值，因此需要對(duì)代價(jià)函數(shù)進(jìn)行修正。在滿足一定條件的情況下，線性變換[31]可以在保持非線性度以及自相關(guān)絕對(duì)值指標(biāo)等密碼學(xué)性質(zhì)不變的同時(shí)，將布爾函數(shù)的彈性階由0 變?yōu)?。因此，第二個(gè)代價(jià)函數(shù)先不考慮一階彈性這一優(yōu)化目標(biāo)。由于Bent 函數(shù)具有最大的非線性度以及最小的自相關(guān)絕對(duì)值，且對(duì)任意的都有平衡布爾函數(shù)的非線性度及自相關(guān)性雖然無(wú)法達(dá)到Bent 函數(shù)的結(jié)果，但通過(guò)使布爾函數(shù)的Walsh 譜值的絕對(duì)值逼近可以使布爾函數(shù)逐漸逼近Bent 函數(shù)這兩方面的性質(zhì)。因此在HTS算法中引入第二個(gè)代價(jià)函數(shù)，即

2.1.5 終止準(zhǔn)則

為了避免算法在搜索的過(guò)程中錯(cuò)失符合條件的布爾函數(shù)或者進(jìn)行多余的迭代，除了設(shè)置最大迭代次數(shù)max_iter 這一終止準(zhǔn)則外。針對(duì)不同的代價(jià)函數(shù)設(shè)置了不同的提前終止準(zhǔn)則。本文算法使用代價(jià)函數(shù)cost1(f)時(shí)所對(duì)應(yīng)的提前終止準(zhǔn)則為

2.1.6 HTS 算法中的爬山算法

除了減少HTS 算法對(duì)初始解的依賴性以及提高算法的收斂速度之外，還需HC 算法在優(yōu)化過(guò)程中進(jìn)一步提高布爾函數(shù)的非線性度這一優(yōu)化目標(biāo)。由式(6)可知，對(duì)任意的越小，f的非線性度就越大。因此，與2.1.4 節(jié)中的代價(jià)函數(shù)不同，HC 算法所采用的代價(jià)函數(shù)為。在HC 算法的具體步驟中，本文還引入了一種深度優(yōu)先搜索的思想，具體步驟如算法1 所示。

算法1HC 算法

步驟1輸入n元平衡布爾函數(shù)f的真值表，計(jì)算其代價(jià)函數(shù)值

步驟2 令 i=1，并記f的單點(diǎn)優(yōu)化集合C0和1C 都為空。

2.1) 對(duì)f真值表第i個(gè)位置的值進(jìn)行取反，并將其記為g，計(jì)算g的代價(jià)函數(shù)值若，轉(zhuǎn)到步驟2.2)；否則，轉(zhuǎn)到步驟2.3)。

2.2) 若 g (i)=1，將i加入C0；否則，將i加入1C。

2.3) 令i=i+1，若 2ni≤，轉(zhuǎn)到步驟2.1)；否則，執(zhí)行步驟3。

步驟3判斷C0或1C 是否為空集，若是，則算法結(jié)束，輸出f為最優(yōu)解；否則，執(zhí)行步驟4。

步驟4令 C=C0×C1（集合的笛卡兒積），記集合C中位置對(duì)的個(gè)數(shù)為num_C，令j=1，flag=0。

4.1) 記集合C中第j個(gè)位置對(duì)為 C (j)，對(duì)f的真值表的 C (j) 位置處的值進(jìn)行取反，并將其記為h，計(jì)算h的代價(jià)函數(shù)值若那么令f=h，flag=1，并再對(duì)f執(zhí)行爬山算法；否則，執(zhí)行步驟5。

4.2) 令j=j+1，若 j≤ num_C，轉(zhuǎn)到步驟4.1)；否則，執(zhí)行步驟5。

步驟5若flag=0，則算法結(jié)束，輸出最優(yōu)解f。

下面，給出算法1 執(zhí)行的一個(gè)實(shí)例。

2.2 HTS 算法步驟設(shè)計(jì)

2.2.1 算法改進(jìn)

由于傳統(tǒng)的禁忌搜索算法在每次迭代過(guò)程中是串行的，即首先逐一計(jì)算每個(gè)候選解的代價(jià)函數(shù)值，然后將每次計(jì)算的結(jié)果與當(dāng)前最優(yōu)代價(jià)函數(shù)值進(jìn)行比較，以此確定是否要更新當(dāng)前最優(yōu)代價(jià)函數(shù)值和禁忌表。因此，當(dāng)前最優(yōu)代價(jià)函數(shù)值和禁忌表在迭代過(guò)程中是動(dòng)態(tài)變化的，從而導(dǎo)致傳統(tǒng)禁忌搜索算法無(wú)法使用并行計(jì)算，當(dāng)候選解的個(gè)數(shù)較多時(shí)，算法運(yùn)行速度會(huì)很慢。對(duì)此，除了引入HC 算法來(lái)提高算法的收斂速度之外，本文還做了如下改進(jìn)來(lái)提高算法的運(yùn)行速度。在每次迭代時(shí)，將計(jì)算候選解的代價(jià)函數(shù)值與更新當(dāng)前最優(yōu)代價(jià)函數(shù)值和禁忌表分開(kāi)進(jìn)行，即首先使用并行計(jì)算得到所有候選解的代價(jià)函數(shù)值，并選取代價(jià)函數(shù)值最優(yōu)的候選解作為當(dāng)前最優(yōu)解，然后將那些順序在當(dāng)前最優(yōu)解之后且代價(jià)函數(shù)值劣于迭代前最優(yōu)代價(jià)函數(shù)值的候選解全部舍棄，此時(shí)更新當(dāng)前最優(yōu)代價(jià)函數(shù)值和禁忌表只需要按先后順序?qū)λＡ舻暮蜻x解進(jìn)行判斷。

表2 算法改進(jìn)前后運(yùn)行時(shí)間對(duì)比

2.2.2 算法步驟

將改進(jìn)后的TS 算法與HC 算法相結(jié)合，就得到了如算法2 所示的HTS 算法。

算法2HTS 算法

步驟1輸入候選解個(gè)數(shù)num_cs、禁忌長(zhǎng)度len_tabu、最大迭代次數(shù)max_iter 以及非線性度期望值exp_Nf，令禁忌表tabu 為空表。

步驟2隨機(jī)生成一個(gè)平衡布爾函數(shù) frand，對(duì)其執(zhí)行HC 算法，將HC 算法的執(zhí)行結(jié)果f作為初始解，判斷f是否滿足終止條件term(f)，若滿足，則算法結(jié)束，輸出f為最優(yōu)解；否則，計(jì)算f的代價(jià)函數(shù)值cost(f)，令當(dāng)前最優(yōu)解best_ f=f以及當(dāng)前最優(yōu)代價(jià)函數(shù)值best_cost=cost(f)，記迭代次數(shù)iter 為0。

步驟3在best_ f 的2-opt 鄰域中隨機(jī)選取num_cs 個(gè)候選解，并計(jì)算所有候選解的代價(jià)函數(shù)值。

步驟4判斷是否存在某個(gè)候選解cf 滿足終止條件term(cf)，若存在，則算法結(jié)束，輸出cf 為最優(yōu)解；否則，執(zhí)行步驟5。

步驟5計(jì)算所有候選解中的最優(yōu)代價(jià)函數(shù)值min_cost，并與best_cost 進(jìn)行比較，若min_cost＜ best_cost，則更新當(dāng)前最優(yōu)解best_ f 為min_cost 所對(duì)應(yīng)的候選解，執(zhí)行步驟6；否則，執(zhí)行步驟7。

步驟6對(duì)候選解進(jìn)行篩選，只保留那些順序在best_ f 之前（包括best_ f ）并且代價(jià)函數(shù)值小于best_cost 的候選解。記篩選后的候選解的個(gè)數(shù)為num_cs_rem，令 i=1，

6.1 ) 將第i個(gè)保留的候選解的代價(jià)函數(shù)值cost(fi)與 best_cost 進(jìn)行比較，若cost(fi)＜ best_cost，則更新保留的候選解中最優(yōu)代價(jià)函數(shù)值best_cost=cost(fi)，轉(zhuǎn)到步驟6.2)；否則，轉(zhuǎn)到步驟6.3)。

6.2 ) 判斷fi是否在禁忌表tabu 中，若是，則fi滿足特赦準(zhǔn)則，此時(shí)更新禁忌表，先將fi從禁忌表tabu 中解禁，再將fi加入禁忌表中；否則，將fi加入禁忌表tabu 中，更新禁忌表，執(zhí)行步驟7。

6.3 ) 令i=i+1，若 i≤ num_cs_rem，則返回步驟6.1)；否則，執(zhí)行步驟8。

步驟7此時(shí)要接受弱解，即從所有不屬于禁忌表的候選解中選取一個(gè)代價(jià)函數(shù)值最優(yōu)的解作為best_f，并更新最優(yōu)代價(jià)函數(shù)值best_cost 為best_ f 的代價(jià)函數(shù)值，將best_ f 加入禁忌表tabu中，更新禁忌表，執(zhí)行步驟8。

步驟8對(duì)best_f 執(zhí)行HC 算法，將優(yōu)化后的函數(shù)記為hc_ f，判斷hc_ f 是否滿足終止條件term(hc_ f)，若滿足，則算法結(jié)束，輸出hc_ f 為最優(yōu)解；否則，執(zhí)行步驟9。

步驟9令iter=iter+1，若iter＜ max_iter，轉(zhuǎn)到步驟3；否則，對(duì)best_ f 執(zhí)行爬山算法并將優(yōu)化后的函數(shù)hc_ f 輸出為最終結(jié)果。

下面，給出算法2 執(zhí)行的一個(gè)實(shí)例。

例2輸入num_cs=50、len_tabu=1、max_iter=200、exp_Nf=12，代價(jià)函數(shù)為cost2(f)，以例1最終的輸出 f= (11 11 0010 0000 0000 0100 1111 1110 0111)作為初始解，且f不滿足終止條件，令best_ f=f，best_cost= cost2(f)=1.51 × 107。執(zhí)行步驟3 和步驟4，不存在候選解滿足終止條件。執(zhí)行步驟5，有 min_cost=6.12 × 106。令best_ f=(11 11 0010 0000 00 10 01 00 11 01 1110 01 11)，執(zhí)行步驟 6，更新禁忌表及best_cost=min_cost=6.12 × 106。執(zhí)行步驟8，對(duì)best_ f 執(zhí)行算法1，執(zhí)行后的輸出為hc_ f= (01 11 0010 10 00 001 0 0100 11 01 1110 01 11)，hc_ f 滿足終止條件，算法2 結(jié)束，輸出hc_ f。

對(duì) hc_ f 進(jìn)行線性變換得 hc_ f′=(0101 1000 1100 0111 0111 1001 0010 1010)，至此，就得到了一個(gè)非線性度為12、自相關(guān)絕對(duì)值為8、代數(shù)次數(shù)和代數(shù)免疫度為3、抵抗快速代數(shù)攻擊能力為4 的5 元一階彈性布爾函數(shù)。對(duì)5 元一階彈性布爾函數(shù)而言，除抵抗快速代數(shù)攻擊能力為次優(yōu)之外，hc_ f′的其他密碼學(xué)指標(biāo)均達(dá)到了最優(yōu)。

3 實(shí)驗(yàn)結(jié)果及分析

本文的實(shí)驗(yàn)環(huán)境是主頻為2.5 GHz 的Intel core i5-7300HQ 處理器，內(nèi)存為8 GB，編程軟件采用MATLAB 2019a。對(duì)8～14 元的布爾函數(shù)進(jìn)行搜索時(shí)，一些參數(shù)的選取如表3 所示。

表3 參數(shù)的選取

由于所得到的結(jié)果都是具有一階彈性的布爾函數(shù)，為了方便表示，將布爾函數(shù)的密碼學(xué)性質(zhì)用(Nf,Δf,deg,AI,FAA)表示，其中，Nf為非線性度，Δf為自相關(guān)絕對(duì)值，deg 為代數(shù)次數(shù)，AI 為代數(shù)免疫度，F(xiàn)AA 為抵抗快速代數(shù)攻擊能力。在HTS算法中，代價(jià)函數(shù)算法）與算法）的結(jié)果對(duì)比如表4 所示。

表4 算法與算法的結(jié)果對(duì)比

表4 算法與算法的結(jié)果對(duì)比

下面，具體分析表5 中各個(gè)密碼學(xué)指標(biāo)的對(duì)比結(jié)果。

1) 代數(shù)次數(shù)。由定理2 中代數(shù)次數(shù)與彈性階的關(guān)系可知，除文獻(xiàn)[9]中12 和14 元布爾函數(shù)的代數(shù)次數(shù)之外，表5 中其他布爾函數(shù)的代數(shù)次數(shù)都達(dá)到了最優(yōu)。

2) 代數(shù)免疫度。當(dāng)n為偶數(shù)時(shí)，表5 中布爾函數(shù)的代數(shù)免疫度全部達(dá)到最優(yōu)。當(dāng)n為奇數(shù)時(shí)，本文算法搜索得到的布爾函數(shù)的代數(shù)免疫度也全部達(dá)到最優(yōu)；文獻(xiàn)[12-13]結(jié)果中的布爾函數(shù)的代數(shù)免疫度是次優(yōu)的；而文獻(xiàn)[8-9]的結(jié)果是基于Bent 函數(shù)構(gòu)造的，未能給出奇數(shù)元的結(jié)果。

3) 抵抗快速代數(shù)攻擊的能力。文獻(xiàn)[12-13]以及本文算法得到的布爾函數(shù)的抵抗快速代數(shù)攻擊能力都達(dá)到了 n-1（次優(yōu)）；Carlet[32]證明了文獻(xiàn)[8]中所構(gòu)造的布爾函數(shù)的抵抗快速代數(shù)攻擊能力較弱；文獻(xiàn)[9]的結(jié)果中，除8 元布爾函數(shù)之外，其他布爾函數(shù)的抵抗快速代數(shù)攻擊能力皆未達(dá)到次優(yōu)。

表5 一階彈性布爾函數(shù)的密碼學(xué)性質(zhì)對(duì)比

5) 自相關(guān)性。與上述4 個(gè)密碼學(xué)性質(zhì)不同，對(duì)一個(gè)布爾函數(shù)而言，其自相關(guān)絕對(duì)值越小，該布爾函數(shù)的自相關(guān)性就越好。本文算法搜索得到的布爾函數(shù)的自相關(guān)絕對(duì)值優(yōu)于文獻(xiàn)[12-13]的結(jié)果；當(dāng)n=12時(shí)，文獻(xiàn)[9]中布爾函數(shù)的自相關(guān)絕對(duì)值優(yōu)于本文算法的結(jié)果；而文獻(xiàn)[8]中未考慮這一性質(zhì)。

4 結(jié)束語(yǔ)

本文以高非線性度、低自相關(guān)性、一階彈性為優(yōu)化目標(biāo)，以最優(yōu)代數(shù)次數(shù)、最優(yōu)代數(shù)免疫度、最優(yōu)（次優(yōu)）抵抗快速代數(shù)攻擊能力為約束條件，提出了2 個(gè)代價(jià)函數(shù)。本文在HC 算法和TS 算法上進(jìn)行改進(jìn)，得到了一種新的布爾函數(shù)快速生成算法——HTS 算法。與傳統(tǒng)的TS 算法相比，HTS 算法不僅搜索能力更強(qiáng)，而且運(yùn)行速度也更快。利用本文算法對(duì)8～14 元的布爾函數(shù)進(jìn)行搜索，得到了滿足幾乎所有密碼學(xué)性質(zhì)的布爾函數(shù)。當(dāng)n=8,10時(shí)，本文算法得到的一階彈性布爾函數(shù)的非線性度都達(dá)到了目前已知的最大值。與其他啟發(fā)式算法相比，本文算法的搜索能力更強(qiáng)，所得的結(jié)果也更好。不同于文獻(xiàn)[8-9]中的代數(shù)構(gòu)造法所存在的一些局限性，本文算法不僅對(duì)變?cè)獋€(gè)數(shù)為奇數(shù)時(shí)的情形也同樣適用，而且以隨機(jī)生成的平衡布爾函數(shù)作為初始輸入（除了10 元布爾函數(shù)需要嘗試多個(gè)輸入之外），可以搜索到滿足上述密碼學(xué)性質(zhì)的全部布爾函數(shù)。

附錄

n=8,(116,24,6,4,7)

3639 7756 304C C72F D09F 425A F13A 1E49 0972 ED40 EAA7 C1F8 BE95 AAC9 D843 462F

n=9,(236,48,7,5,8)

3EA4 427D EF09 C463 2F64 E3B0 B950 9D14 4A2A CD57 42BD ACFC 5882 179A 2F9A CEAE A11F B352 E489 2775 36EB E145 F17E 02DC 8C86 26ED 61F5 2E60 1F57 7D32 781C A071

n=10,(488,72,8,5,9)

CAAC 4954 3C59 39D1 C724 B6FB B2E7 89F4 AD63 4BFA 8250 FA13 2D4E FA02 2247 9A0A 7968 3E1B 9983 3146 4CE4 53A7 6B42 5C92 0FE3 B3F4 668F 78E4 2071 79DC 7BD3 267A F70B 5EBB E015 4EE7 5C40 BC7C 17A0 19AE 794D 0121 775F 2A2F FA1C EC6A 621C 59CC CCB1 C0A4 1C6F 07C5 DFC0 AEE2 81EF 7852 3205 4339 DF9E 8835 059F 10D8 79EC 3DB6

n=11,(988,104,9,6,10)

0D0D 65C0 7F85 16AF 82DF 0126 C7CF 47DD 9734 985F 71F2 3A65 2DA9 B6F7 2985 5AF3 118C A003 7568 9D9F 20D4 97BC 7920 3681 0163 F04C 3CC9 C9A9 6D36 43CB 0FC3 8674 B5A0 EF5E A548 D121 9E1B 9A44 C578 6291 3EB2 0174 F0BA 93B3 8D73 C8D7 3488 BFAC 8F18 C399 59E0 4FC8 E455 963B C7FB 354D D3A5 E86F 7837 1A1B B191 E8BE BE44 629F FFE5 0D2D 1FF3 9534 C876 EEA9 11A5 74D2 7EE0 1468 0730 400F E963 ECED 0C76 3B62 2B76 D5D7 3FCA C9CA AB98 EA20 9B7F CAB9 08CD 2E02 F847 9B23 53E6 F440 8BA3 6D95 5612 EAF6 4AAB CC73 510F 6DA3 E598 56B2 0810 B4F9 736B 40A0 91BD 5ABE 9480 82CF 155D 7A66 BBCA 2643 4984 1DA6 88C9 88C0 FD5E 5DEB 7DB3 2BAD 6957 E082 73A4 CF01

n=12,(1996,152,10,6,11)

A8C7 C7A5 ABB9 6349 3704 C774 EF9F C0DA CB92 BFA8 AB54 4315 077B A0B3 984D DA89 B55B 2CAA 4D28 A082 7F63 5CC4 E3F7 2F7C A0CB 178D F559 AFA6 456B 92F5 0EA3 6324 D781 8044 94DC 66CC 3119 01E7 06E8 990D BE22 D706 6439 5954 DDB3 B66D D607 1016 5C13 2DFC A8E1 A572 CB94 0940 1DF4 11DA F1BD F071 B540 3E58 CC02 56CC 47E2 6B8D 3648 A16B B451 F017 0564 9BAA D9BF B702 3CB5 6D2C 438D FFAA C016 6B62 3BDF 6EA1 F08C 7084 AD57 00E0 1D1E ADCF 2067 942B 28CC 679B 853B 131D 629A EF1E F65C 78BF EA42 1A46 39E8 93E0 729F 5B28 AEA4 6B26 989D 13A6 5971 FB74 0CFD 7028 231A 10CB 178F 89B1 BD9D A8DD 3AB8 9BD2 1797 4B3B 0311 DA7B 7F77 939D CD35 E39D CF21 D626 BE91 DEE2 9024 05A6 F036 AFB5 FAD4 A4E5 0A3C 4B46 F109 9BE6 29B1 C055 00C1 7B75 BEB5 A052 4DCF CB16 B154 6A16 DFBE C322 ECE8 9952 7791 E7C3 CE24 05B1 2A42 5B3F 07F7 B29A D326 89C7 0602 F6FD A2A6 1E72 DCE5 977A 6EDF 195D 27E4 AE57 10C3 5A1E 4ED1 39A5 AD45 8BFA 786F 0D93 6518 CC4E 4CEF F2BE C827 C60C 90D2 16FC 198F 799E B7E4 23FE BF35 72B4 67C1 7EB2 C1FB 9D99 838C C2C3 FFE0 6048 547E C715 E0D4 0269 4E3C BB79 8248 7A90 0C9E 38C2 195D 3146 507F B24A D934 1B21 67A8 0EA9 00AE C29D D0FC BE54 0C96 CB84 AD3F 39B3 7B71 53D5 812A 8EE2 205A 4DB7 F4A2 B483 294D D76F 600F FDF5 DA9C 5CB0 7029 E038 2A80 D6C8 45C7 8CE0 4B82 41F8 7E1E 21A1 FD87 4D6F