基于樹形奇偶機的密鑰交換優化方案

韓益亮 李 魚 李 喆

(武警工程大學密碼工程學院 西安 710086)

1 引言

人工智能技術與各個領域的交叉結合越來越緊密，與密碼學的融合也在不斷加深。一方面，人工智能技術本身存在的安全隱私問題可以利用密碼學的方法和工具來解決[1]；另一方面，人工智能技術也可以用于密碼算法的設計與分析[2]。其中，利用互學習神經網絡設計密鑰交換不需要耗用大量計算資源，在無線傳感器網絡、無人機、云計算等領域有良好的應用前景。將神經網絡同步用于設計密鑰交換是Kanter等人[3]首次提出來的，其具有速度快、安全性高的優勢，但隨著幾何攻擊、合作攻擊等分析方法的提出，盡管其可以通過增大參數來保證安全性，但參數增大帶來了效率的降低。因此采用新技術提高神經網絡同步的效率和安全性是目前亟待解決的問題。

Kinzel等人[4]的研究表明了單個感知機之間的同步易于被攻擊者模仿而不適合用于實現密鑰交換。Klimov等人[5]對Kanter等人[3]提出的神經密鑰交換協議進行了詳細的分析，并提出了遺傳算法攻擊、幾何攻擊和概率攻擊，以上3種攻擊能有效攻破神經密鑰交換協議，但僅限于固定的參數。當參數增大時，Shacham等人[6]提出了一種合作攻擊的策略，和單個攻擊效果最好的幾何攻擊相結合，能夠使攻擊者的成功概率不受神經網絡突觸深度的影響。Ruttor等人[7]提出了一種基于神經網絡權重查詢的方式來代替隨機輸入，能夠降低合作攻擊的成功概率。Allam等人[8]提出了將預共享密鑰作為學習邊界的認證神經密鑰交換協議，并采用動態的學習率，使得攻擊者在不知道預共享密鑰的情況下，無法采用遺傳算法攻擊、幾何攻擊和概率攻擊得到想要的結果。Pal等人[9]為了解決現有基于樹形奇偶機(Tree Parity Machine,TPM)的密鑰交換中同步時間不夠高效和密鑰隨機性不夠強的問題，提出了一種新的同步學習規則，該學習規則在通信雙方TPM輸出結果相等時更新權重，然后各自將權重與系統當前時間進行模運算。其仿真結果表明，Pal等人[9]提出的新方法與Hebbian,Anti-Hebbian和Random-Walk學習規則相比，能夠有效減少同步所需時間。Dong等人[10]將TPM從實數域擴展到復數域，相應的權值、輸入和輸出也都擴展為復數，并給出了復數域下TPM的相關定義和學習規則，然后設計了基于復數域下TPM的密鑰交換協議。

Sarkar[11]將基于多層感知機同步產生的會話密鑰應用到無線通信網絡中，提出了一種新的加密算法。Sarkar等人[12]提出用TPM之間的同步生成可變長度的會話密鑰，并從會話密鑰中派生出子密鑰串用于設計初始密碼矩陣，對明文進行加密。肖成龍等人[13]提出了一種采用人工神經網絡的雙重加密方案，主要利用人工神經網絡產生隨機矩陣來對數據進行第1次加密，從而提高通信系統抵抗暴力攻擊的能力。Saballus等人[14]提出了兩種基于完全二叉樹的多神經網絡同步算法，并將其應用到了基于神經網絡的群組密鑰交換中。Santhanalakshmi等人[15]基于神經網絡分別設計了環結構(采用鄰居學習同步模式)和樹結構(采用分布式同步模式)的組密鑰協商協議，這兩類協議都可以用作動態對等組的密鑰協商，支持舊用戶撤銷和新用戶加入，且均能保證前向安全、后向安全和密鑰獨立。

一般的樹形奇偶機沒有使用向量計算，效率不高。Chourasia等人[16]在TPM實現時用NumPy庫進行向量化，提出了向量化的神經密鑰交換協議，并深入研究了向量化后的TPM結構參數對同步時間的影響。該文還提出在密鑰生成過程中使用消息認證碼來實現認證性。Walter等人[17]采用Python實現的幾何攻擊算法來尋找TPM的最佳結構，即尋找使得神經密鑰交換安全性更高的TPM的最佳參數組合，他們的研究表明參數為(8,16,23)時在抵抗幾何攻擊上效果最佳。由于文獻[17]的研究使用的是采用幾何攻擊策略的單個攻擊者，而不是采用合作攻擊策略的多個攻擊者，其方案的安全性還有待進一步研究。

本文的主要貢獻在于：定義了向量化的學習規則，提高樹形奇偶機同步學習的時間效率；給出了尋找在時間和安全性上更優的TPM結構參數的方法，并將采用優化參數的本文方案與文獻[17]、文獻[18]進行了效率對比；將向量化方法與文獻[16]的方法進行了對比；同時，研究了向量化對同步步數和同步時間的不同影響。仿真結果表明，采用向量化學習規則和優化參數的本文方案在時間效率上優于文獻[17]、文獻[18]中的方案，且采用向量化的學習規則只是減少了同步所需要的時間，沒有減少同步所需步數，不會導致攻擊者的成功率增加，因而不會影響優化方案的安全性。

2 預備知識

2.1 樹形奇偶機

樹形奇偶機[19]是具有一個隱藏層的前向反饋神經網絡(見圖1)，能夠用于神經密鑰交換協議的設計。樹形奇偶機由K個隱藏單元組成，每個隱藏單元有N個輸入神經元和1個輸出神經元。

圖1 K=3和N=4的樹形奇偶機

每個輸入神經元的取值范圍：xi,j∈{?1,+1}，每個輸入神經元所對應權重的取值范圍：w i,j∈{?L,?L+1,···,+L}，其中i=1,2,···,K表示樹形奇偶機的第i個隱藏單元，j=1,2,···,N表示隱藏單元的第j個 輸入，L表示隱藏神經元權重可取的最大值。每個隱藏單元的輸出為σi=sign(h i)，其中h i?1h i=0

的取值有3種，分別為 ,0,1，當 時，

2.2 學習規則

在開始進行密鑰交換時，Alice和Bob各自運行一個樹形奇偶機，雙方隨機選擇互不關聯的初始權重wA和wB。在同步過程中，雙方都將公共參數x作為共同輸入，并將輸出結果τA或τB發送給對方。在收到對方發送的輸出結果后，判斷τA和τB是否相等，如果相等，則按照以下學習規則進行權重的同步更新；否則，不對權重做任何改變。

Hebbian學習規則[20]，更新權重方式

2.3 幾何攻擊

幾何攻擊是由Klimov等人[5]在2002年亞密會上提出的，每個幾何攻擊者各自進行獨立攻擊，互不影響，目的是和通信雙方實現權值同步。其具體思想是攻擊者Eve采用和通信雙方Alice,Bob一樣的樹形奇偶機結構，隨機地初始化自己的權值，在每一個學習步采用和Alice,Bob一樣的輸入，然后根據以下策略更新自己的權值，以為了和Alice實現權值同步為例。

步驟1如果Alice和Bob的輸出不相等，即τA=τB，那么攻擊者Eve選擇不更新自己的權重。

步驟2如果Alice和Bob輸出相等且和攻擊者Eve的輸出相等，即τA=τB且τA=τE，那么攻擊者Eve按照和Alice一樣的學習規則更新自己的權重。

步驟3如果Alice和Bob的輸出相等，但是和攻擊者Ev e的輸出不等，那么攻擊者Eve尋找

3 基于向量化學習規則的神經密鑰交換方案

3.1 模型描述

本文采用特殊的神經網絡即向量化樹形奇偶機(vectorized Tree Parity Machine,vTPM)來進行Alice和Bob之間的密鑰交換，將通過相互學習實現同步后的vTPM權值作為會話密鑰，其同步過程如下所示：

步驟1 Alice和Bob各生成隨機權值對vTPM進行初始化，接著進行以下步驟直至完全同步；

步驟2生成隨機輸入向量；

步驟3利用隨機輸入向量計算各隱藏層的輸出值以及vTPM的輸出值；

步驟4 Alice和Bob將自己vTPM的輸出結果發送給對方；

步驟5在收到對方的信息后，判斷自己的輸出結果和對方的是否相等，如果相等則采用相應的學習規則更新權值；否則，跳轉到步驟2執行。

本文在步驟5中采用的學習規則是向量化的，即可以并行執行的學習規則。以Alice為例，其通過向量化Hebbian規則更新權重的方式為

通過向量化Anti-Hebbian學習規則更新權重的方式為

通過向量化Random-Walk學習規則更新權重的方式為

其中，t表示當前時間步，t+1表示下一時間步，函數Θ1用于比較雙方輸出結果是否相等，如果相等，即τA=τB則返回1，否則返回0。函數Θ2返回的結果為向量[ (0/1)1,(0/1)2,···,(0/1)K]，其作用為比較σ1,σ2,···,σK分別與τA是否相等，如果相等，則在向量對應位置返回為1；否則，在向量對應位置返回為0。函數h(W)將 任意w∈W的值保持在?L和 +L之間。如果權值超出區間，那么通過h(W)函數將權值w∈W設置為±L。

3.2 參數設置

本節主要通過參數預處理找出用于生成約512 bit長度密鑰的v TPM結構參數。表1給出了相關變量及其描述。

表1 變量說明

v TPM的結構是由其參數K,N,L決定的，用vTPM生成加密密鑰的長度也是由K,N,L三者決定的。加密密鑰長度=K×N ×LBIN，其中LBIN表示L的二進制值的比特長度，因為權重范圍{?L,?L+1,···,+L}，所以用有符號數表示L，即LBIN中有1位是符號位。當L=1時，LBIN=2；L=2或3時，LBIN=3；當L=4或5或6或7時，LBIN=4；當L不斷增大時，以此類推。為了找到最適合生成512 bit長度密鑰的vTPM結構，首先需要找到所有可能的K,N,L的值。由于K≤3時很容易被合作攻擊攻破，因此本文中不考慮K≤3的情況。并且嚴格限制K≤N，因為當K>N時，兩個樹形奇偶機之間的同步將會變得困難。又因K,N,LBIN不全是512的因子，所以存在部分K ×N ×LBIN的值略大于512。

通過參數預處理發現，當K增至14時，由于K≤N的限制，N=14已是N所能取的最小值。在K>14并繼續增大時，N的值也隨著K的增大而同步增大，而同步時間也會隨著增大。而預處理也發現當K增至14時，相應的參數組合已經完全能夠抵抗幾何攻擊和合作攻擊了。因此，本文的參數組合僅考慮K在4～14，一共有25種組合。具體的參數組合如表2所示。

表2 參數組合

3.3 效率測試算法

本節主要設計了用于測試神經密鑰交換所需時間的算法。本算法主要測試的是通信雙方Alice和Bob在采用樹形奇偶機進行相互學習所需的步數和對應的時間。具體過程如表3中算法1所示。

表3 效率測試算法(算法1)

在算法1中，第(1)行是用于記錄運行總時間和總步數的，第(2)行是需要執行的次數，第(3)～(6)行是用參數K,N,L對vTPM進行初始化以及初始時間和初始步數。第(7)行是進行仿真直到Alice和Bob實現同步，第(8)行是生成隨機輸入向量。第(9)～(10)行是計算Alice和Bob的vTPM的輸出。第(12)～(14)行是對輸出滿足條件時進行權重更新，并增加1次步數，進入下一次循環。第(15)～(21)行是計算平均時間和平均步數。

3.4 安全性分析

Alice的隱藏層輸出不相等的有1個或者3個。有1個隱藏層輸出不相等發生的概率為25%，而有3個隱藏層輸出不相等的概率也為25%。因此有1個隱藏層輸出不相等和有3個隱藏層輸出不相等發生的概率是相同的。幾何攻擊僅針對有1個隱藏層輸出不相等而采取相應的策略，忽略了有3個隱藏層輸出不相等的情況，這種策略在K=3時十分有效，因為有1個隱藏層輸出不相等的情況為大多數，而有3個隱藏層輸出不相等的情況很少發生。因此K=4時幾何攻擊效果有所下降。

同理當K=5時，有1個隱藏層輸出不相等的概率約為15.6%，有3個隱藏層輸出不相等的概率為約15.6%，有5個隱藏層輸出不相等的概率約為3.1%。以此類推，當K不斷增大時，只有1個隱藏層輸出不相等的概率會越來越小，因此隨著K的增大，幾何攻擊的效果不斷下降，利用幾何攻擊策略的合作攻擊的效果也會下降。

3.5 安全性測試算法

本節主要將合作攻擊策略應用到測試K>4時方案的安全性。因為在同步過程進行到1/3后采用合作攻擊策略效果最好，所以本文將時間測定算法嵌入到合作攻擊中，在測試每種參數之前先測得平均同步步數，使其能夠自適應參數的變化，從而保證合作攻擊策略的有效性。在表4的算法2中，第(1)行的判斷保證只有當同步過程進行到1/3后且當前步數為偶數步時使用合作攻擊策略，否則使用幾何攻擊策略。第(2)～(4)行是對輸出和Alice不相等的攻擊者進行更新隱藏層輸出，第(5)行通過投票找出票數最多的隱藏層輸出表示，并讓所有人都用這個表示來更新權重第(6)～(8)行。第(9)～(15)行表示采用幾何策略進行更新權重。

表4 安全性測試算法(算法2)

4 性能分析

4.1 向量化方法對比

本節主要將本文方案與文獻[16]所提方案進行了對比分析(詳見表5)。文獻[16]中主要利用了Python語言的第三方NumPy庫在TPM的實現上采用向量化的計算來提高TPM之間同步的時間效率，該方法的局限性在于只有用Python語言進行編程實現時才有效。而本文主要通過定義向量化的學習規則來實現TPM的向量化，不局限于編程語言和平臺，具有更強的實用性。此外，本文還給出了尋找優化參數的方法，并進行了安全性測試。

表5 向量化方法對比

4.2 仿真結果

本文采用Python語言編程實現和測試，實驗環境為：Think Pad E431筆記本電腦，intel酷睿i3處理器，雙核四線程，Ubuntu系統。仿真結果如表6所示，本文組合運行了1000次，主要測試了平均步數、平均時間、幾何攻擊成功率和合作攻擊成功率。幾何攻擊成功概率是指單個攻擊者Eve能夠成功和通信雙方實現同步的次數占總測試次數的百分比，合作攻擊成功率是指采用100個攻擊者Eve合作的方式能夠成功和通信雙方實現同步的次數占總測試次數的百分比。

本文的目的是尋找高效安全的參數，故不采用同步時間大于0.5 s的參數，也不對這部分參數進行攻擊。從表6可看到，平均時間最少的參數為(4,64,1)，僅0.0192 s。但其被合作攻擊攻破的概率為99.1%，幾乎完全攻破。能抵抗合作攻擊的參數有6組，分別是(11,16,2),(11,16,3),(12,15,2),(12,15,3),(13,14,2)和(14,14,2)。其中(14,14,2)的平均時間是6組參數中最少的，為0.1219 s，而(11,16,3)的平均時間是6組參數中最多的，為0.4165 s，比(14,14,2)慢了0.2946 s，是(14,14,2)的3倍。

從表6可以發現，當固定L時，隨著K的增大和N的減小，攻擊成功率下降速度較快。圖2展示了當K從8增大至14時，合作攻擊成功率的下降趨勢。在圖2(a)中，當K的取值分別為8,9,10,11,12,13,14時，N對應的取值分別為32,29,26,24,22,20,19；在圖2(b)中，K的取值分別為8,9,10,11,12,13,14時，N對應的取值分別為22,19,18,16,15,14,14。L=1時，攻擊成功率下降稍緩；而L=2時，攻擊成功率下降非?？?，當K >10時，攻擊成功率降為0。

表6 仿真結果(1000次)

由于圖2中K在增大而N在減小，于是本文研究了K和N單獨變化對攻擊成功率的影響，如圖3所示。圖3(a)是固定N=40和L=2，令K從4增大至14時對攻擊成功率的影響，從中可以看到，隨著K的增大，攻擊成功率呈指數下降，直至降為0。圖3(b)是固定K=4和L=2，令N從10增至40時對攻擊成功率的影響，從中可以看到，隨著N的增大，攻擊成功率呈下降趨勢。即隨著N的減小，攻擊成功率會增大。從圖3可以得到，影響攻擊成功率下降的主要因素是K，K的增大會導致攻擊成功率的急劇下降直至為0。當K >14且繼續增大時，由于K≤N的限制，N不得不跟著K同步增大，盡管這會進一步加強方案的安全性，但是其所需同步時間會迅速增大。所以本文得到(14,14,2)是在時間效率和抵抗已知攻擊效果最好的參數。

圖2 K和N同時變化對攻擊成功率的影響

圖3 單一參數變化對攻擊成功率的影響

此外，本文還研究了采用向量化學習規則對同步時間和同步步數的影響，并和沒有向量化的進行了對比。同步時間的對比如圖4(a)所示，向量化后的同步時間在0.01～0.04 s，比沒有向量化的同步時間降低近兩個數量級。同步步數的對比如圖4(b)所示，二者同步所需步數基本一致，且都隨著K的增大而增大。在圖4中，實線表示向量化后的，虛線表示非向量化的，均固定取值N=64,L=1。

圖4 向量化與非向量化的對比

4.3 效率分析

將本文的優化方案分別和文獻[17,18,22]中的方案進行了效率上的對比。文獻[17]中的方案是基于神經網絡的密鑰交換方案，所采用的參數為(8,16,23)；文獻[18]中的方案是基于格上LWE問題的密鑰交換方案，所采用的參數為文獻[18]中推薦的參數；文獻[22]中的方案是基于身份的無雙線性對的密鑰協商方案。本文采用Pairing-Based Cryptography庫對其進行了仿真實現，所采用的橢圓曲線為y2=x3+x，所采用的哈希函數為MHASH-SHA512，生成密鑰長度為512 bit；本文方案采用的參數為(14,14,2)。4個方案均采用C語言實現，其余實驗環境與前文一致，對每個方案進行1000次仿真，效率對比如表7所示。和基于神經網絡的密鑰交換方案相比，交換得到相同長度的密鑰，采用向量化學習規則的本文方案完成密鑰交換所需的平均時間比沒有向量化的文獻[17]中的方案少1/16；和基于格的方案[18]相比，由于其方案中沒有提供生成512 bit長度密鑰的參數，本文采用其生成256 bit長度密鑰的推薦參數，其生成256 bit長度所需的平均時間比本文方案生成512 bit長度密鑰所需的平均時間多1倍，且理論上文獻[18]生成512 bit長度的密鑰需要更多的時間。和基于身份的無雙線性對的密鑰協商文獻[22]相比，本文方案完成密鑰交換的時間遠少于文獻[22]。因此本文方案在時間效率上是高效和實用的。

表7 效率對比

5 結束語

本文針對神經網絡學習規則串行實現效率不高的問題，給出了可并行實現的學習規則定義，對樹形奇偶機進行了向量化。提出了基于樹形奇偶機的密鑰交換優化方案，并對可用于生成512 bit固定長度密鑰的參數進行了仿真實驗，主要從時間效率和安全性兩個方面進行了測試。實驗結果表明，本文所提密鑰交換優化方案是安全高效的。采用本文所提優化方法，理論上可獲得生成任意固定比特長度密鑰的在時間效率和安全性上最佳的參數。在未來工作中，可以考慮使用嵌入零知識證明協議的方法進一步提高優化密鑰方案的安全性，實現基于神經網絡的認證密鑰交換方案。