基于ｎ叉樹的動態安全群密鑰協商協議

摘 要：將三叉樹拓展為n叉樹引入到群密鑰中，提出了動態安全的基于n叉樹的可認證群密鑰協商協議。在三叉樹的基礎上進一步減少了輪數，計算復雜度由O(log3 m)降低為O(logn m)，但是單輪內成員間通信量增加。群內成員先進行樹結構的劃分，每n個節點作為相應上一級節點的孩子節點，n個節點分別選定代表，n個代表通過調用協議BCP協商密鑰得到本輪即相應父親節點的子密鑰，重復進行上述過程最終可以得到群組密鑰。同時，協議考慮了有成員加入或離開的動態情形并給出了很好的解決方案，一方面保證了動態情形發生時，在前一時刻計算出結果的基礎上作最小的修改就能得到新的密鑰，從而減少了計算量；另一方面動態方案保持了樹的結構始終均衡。其意義在于，如果成員加入或離開后樹的結構不能保持，下一步加入或離開就不能順利進行，需重新進行樹結構的劃分。最后基于隨機預言機模型的安全性分析證明了協議是安全的。

關鍵詞：可認證群密鑰協商；動態情況；可證明安全；n叉樹；隨機預言機模型

中圖分類號：TP309文獻標志碼：A

文章編號：1001-3695(2009)06-2180-04

doi:10.3969/j.issn.1001-3695.2009.06.055

Dynamic secure group key agreement based on n-ary trees

GAO Wei，HU Yu-pu，YANG Hong-mei

(Key Laboratory of Computer Network Information Security for Ministry of Educational， Xidian University， Xi’an 710071， China)

Abstract:This paper presented a secure authenticated group key agreement protocol based on n-ary trees in dynamic scenario by introducing n-ary trees obtained by extending ternary trees into key agreement protocol， which reduced more rounds than the ones with ternary trees and reduced computation complexity from O(log3 m) to O（logn m）. But in just one round， the communication complexity increased due to the flows passed between parties increase. Parties were first partitioned to form a tree， then n representations from n nodes which were children nodes of the corresponding father node in the above level agree on a group key in this round by invoking the BCP scheme. Repeating the above process， the group key was obtained finally. At the same time， the scheme took into account the dynamic case which contained the join and leave scenario and presented a good solution.On one hand，it ensured the minimum modification to the computation already precomputed just before the dynamic case happened to reduce computation complexity.On the other hand，concerned the solution retained the tree structure while such dynamic operations (join or leave) because if the tree structure was not maintained after a join or leave operation， the subsequent join or leave in the group could not be performed anymore. At last，gave a security analysis based on the random oracle security model.

Key words:authenticated group key agreement; dynamic scenario; provably security; n-ary trees; random oracle security model

0 引言

密鑰協商協議使得成員在公開的信道上安全地交換信息以得到密鑰成為可能，該密鑰能用來生成會話密鑰，也能用來達到特定的安全目標，如認證、機密性、數據的完整性等。

密鑰協商首先是由Diffie-Hellman等人^[1]給出的，Joux提出了一種基于橢圓曲線上的雙線性對的三方單輪密鑰協商協議。然而，與Diffie-Hellman協議一樣，Joux的協議沒有提供認證功能，容易遭受中間人攻擊。之后的一些協議，在Diffie-Hellman及Joux協議的基礎上加入了認證，并且試圖提出對協議的非正式的安全性證明，但大多數都失敗了，有些甚至在提出后不久缺點就顯現出來了。在Bresson等人^[2]首次提出了安全模型并精準定義了AKE及實體認證作為基本安全目標，提出了可認證的Diffie-Hellman群協議并且在隨機預言機模型下對其安全性給出了證明。Bresson等人^[3]在文獻[2]的基礎上進一步考慮了動態情形；之后，Bresson等人修正已有的正式安全模型以滿足強安全性，文獻[4]中密碼硬件設備用來彌補軟件的缺陷，并且在標準模型下給出了安全性證明比在隨機預言機模型下能得到更好的安全保證。

基于樹的群密鑰協商協議在成員為分層結構的群中是尤為重要的。目前有相當多的基于樹的協議，如Barua等人在文獻[5]中給出的協議，在Joux協議基礎上對成員數量進行了拓展，經證明該協議對被動攻擊是安全的。Dutta等人^[6]利用多重簽名給出了認證協議，并應用Bresson等人^[2]提出的標準模型給出了針對主動攻擊者的具體安全分析。Dutta等人^[7，8]在文獻[5]的基礎上由靜態擴展為動態，并給出了安全性證明。

與文獻[7]相同，本文的目的之一就是在有成員加入或離開時，在前一時刻計算出結果的基礎上作最小的修改就能得到新的密鑰，從而減少了計算量；此外，如果成員加入或離開后樹的結構不能保持，下一步加入或離開就不能順利進行，因此，在考慮動態操作時保持樹的結構是另一個重要問題。本文在此基礎上將樹的結構由三叉樹擴展為n叉樹，減少了輪數及計算復雜度。

1 協議方案

本文的協議將樹型結構的建立由三叉樹拓展為n叉樹，目的是將計算復雜度由O(log3 m)降低為O(logn m)。密鑰協商的過程調用BCP，由于該協議在隨機預言機模型下證明是安全的，本文協議即多次調用BCP得到的協議也是安全的。協議是基于G-CDH困難問題的。

1.1 拓展的n叉樹

令p=m/n」，r=m mod n。參與會話的成員首先被分割成n個子集合，具體如下：如果r=0，每個子集成員個數分別為p，p，…，p，p；如果r=1，每個子集成員個數分別為p，p，…，p，p+1；如果r=2，每個子集成員個數分別為p，p，…，p+1，p+1；…；如果r=p-1，每個子集成員個數分別為p，p+1，…，p+1，p+1。從上到下遞歸地調用該過程進一步劃分可以得到一個n叉樹結構。以m=22的4叉樹為例，如圖1所示的結構。

1.2 BCP

BCP^[3]包括setup、join以及remove算法。本節舉例描述了協議的具體執行過程(以四個成員為例)：在下流程中成員仍保存其上流程中接收到的中間值，事實上，在接下來成員離開后任何留下的成員都有可能成為群管理者UGC，他們需要用這些中間值來執行remove，本協議中UGC是群中下標最大的成員。數據流用長期密鑰LLU加密，用戶名包括在數據流中，會話密鑰sk=H(I‖Flmax(I)‖gx1…xmax(I))，Flmax(I)是下流程的數據流。

1）Setup算法 該算法包括了上流程和下流程兩個階段。在上流程中，成員Ui接收到一組中間數據（Y，Z）。其中:Y=∪0＜s＜i{Z1/xs}，Z=g0＜t＜ixt 。成員Ui隨機選擇一個私鑰xi，計算Y的xi次冪與Z串聯作為其中間值，Y′=∪0＜s＜i{Z′1/xs}。其中:Z′=Zxi=g0＜t＜ixt；然后成員Ui將(Y′，Z′)傳送給環中的下一個成員。當Umax(I)接收到最后的上流程數據流時，下流程開始，此時Umax(I)與在上流程中的成員一樣，廣播中間數據，但是僅僅是Y′，因為事實上，Umax(I)計算出的Z′即是會話密鑰sk。這時，群I中成員計算出sk并接受。

2）Remove算法 該算法僅僅包括了下流程。屬于集合J的成員離開群I，此時成員集合為I/J。群管理者UGC生成一個隨機值x′GC，刪除之前廣播的數據流中屬于J中成員的數據。UGC將其余的數值中所有含有xGC（xGC是UGC之前的私鑰）的數值計算x-1GCx′GC次冪并廣播。I/J中成員計算會話密鑰sk并接受，J中成員刪除任何內部數據，UGC刪除xGC以及x-1GC，只保存x′GC。

3）Join算法 該算法包括了上流程和下流程兩個階段。J中成員欲加入群I中，I中管理者UGC生成一個隨機值x′GC，將中間數值中所有含有xGC（xGC是UGC之前的私鑰）的數值計算x-1GCx′GC次冪，得到一組Y′值；然后x′GC計算Y′中最后一個數值的x′GC值以得到Z′。Ui將(Y′，Z′)傳送給J中第一個加入I的成員，之后調用setup算法，收到廣播數據流之后，I∪J中成員刪除之前會話密鑰，計算新會話密鑰sk并接受。這時群I變成I∪J。

下面以四個成員為例來描述具體算法：U1、U2、U3、U4按順序排成一個環形。

a)Setup算法。以四個成員誠實地執行為例，群I={U1，U2，U3，U4}，共享的會話密鑰為sk=H(I‖Fl4‖gx1x2x3x4)。具體如下：成員U1、U2、U3以及U4各自選取一個私鑰x1、x2、x3、x4，均屬于[1，q-1]。協議首先由U1開始，U1計算X1={g，gx1}，Fl1={I‖X1}，將[Fl1]U1發送給U2；U2驗證V(Fl1)=?true，若真，計算X2={gx2，gx1，gx1x2}，Fl2={I‖X2}，將[Fl2]U2發送給U3；U3驗證V(Fl2)=?true，若真，計算X3={gx2x3，gx1x3，gx1x2，gx1x2x3}，

Fl3={I‖X3}，將[Fl3]U3發送給U4；U4驗證

V(Fl3)=?true，若真，計算

X4={gx2x3x4，gx1x3x4，gx1x2x4，

gx1x2x3}，Fl4={X‖I‖X4}，將[Fl4]U4廣播給其他成員，經過驗證后，成員均能計算出會話密鑰。

b）Remove算法。以四個成員誠實地執行為例，群I={U1，U2，U3，U4}，J={U2，U4}。成員離開后，新群為I={U1，U3}，UGC=U3，共享的會話密鑰為sk=H(I‖Fl3‖g

x1x2x′3x4)。具體如下：假設成員U2和U4離開前執行最后一次協議時，各成員U1、U2、U3以及U4的私鑰分別為x1、x2、x3和x4，并且四個成員同時擁有U4的廣播消息即X4={gx2x3x4，gx1x3x4，gx1x2x4，gx1x2x3}。此時群管理者是U3，U3選取新的私鑰x′3，屬于[1，q-1]。U3計算X′3={

gx2x3x4(x-13x′3)，gx1x2x4}，Fl3=(X4‖I‖X′3)，將[Fl3]U3發送給U1，驗證后，U1和U3均能計算出新的會話密鑰。

c)Join算法。以四個成員誠實地執行為例，群I={U1，U3}，J={U4}，UGC=U3。成員加入后，新群為I={U1，U3，U4}，共享的會話密鑰為sk=H(I‖Fl4‖gx1x2x″3(x4x′4))。具體如下：假設成員U4加入前，U1、U3各自擁有私鑰x1、x′3，且擁有X′3={hx′3，hx1}。其中h=gx2x4，當成員U4加入群后，管理者U3選取新的私鑰x″3，屬于[1，q-1]。U3計算X″3={hx′3(x′-13x″3)，hx1，hx1(x″3)}，Fl3=(X′3‖I‖X″3)，并將[Fl3]U3發送給U4；U4驗證V(Fl3)=?true，若真，計算X″4={hx″3x′4，hx1x′4，hx1x″3

}，Fl4=(X′3‖I‖X′4)，將[Fl4]U4廣播給U1和U3，驗證后可得到新的會話密鑰。

1.3 新協議

動態協議包括初始密鑰生成以及加入算法、離開算法。成員欲加入群可調用加入算法實現，相反若離開群可調用離開算法。協議設計時考慮最大程度利用之前計算的結果以減少計算量，同時考慮到保持樹的結構。

1）初始密鑰生成協議

從上到下遞歸調用2.1節中的方法生成n叉樹，最底層子集是單個成員各自的集合，每個成員各自擁有一個私鑰，在以每層節點為根節點的子樹中分別調用BCP生成子密鑰，各子樹中選擇代表（擁有各自子密鑰）在以上一層節點為根節點的子樹中生成新的子密鑰，重復調用直至生成會話所需要的密鑰。以圖1為例，如果22個成員協商密鑰，首先劃分樹型結構。第一輪，4和5、9和10、13和14、15和16、19和20、21和22分別協商出密鑰并各自選出一個代表（不妨選序號小的一個）；第二輪，成員4用與5協商的密鑰同成員1、2、3共同協商密鑰，同時成員6、7、8和9，成員11、12、13和15，成員17、18、19和21分別協商出密鑰并選擇代表（同樣選擇序號最小的一個）；第三輪，成員1、6、11和17協商出最終的群密鑰。

2）成員加入

假設新成員U請求加入群{U1，…，Um}，加入的原則應該能夠保證樹的結構不會改變，因而不需要考慮因樹的結構改變帶來的對樹的結構的重新劃分。具體程序語言的描述見文獻[7]。下面用圖1中的樹來舉例說明。在這種情況下，根節點有四個子樹，左邊兩個有五個葉節點，右邊兩個有六個葉節點。假設有新成員要加入，如果他加入第一個子樹顯然會破壞樹的結構，他加入后需要重新從上到下劃分樹型結構將成員重組；同理加入第三個和第四個也不行，只能加入第二個子樹，加入后樹型穩定。在第二個子樹中同樣有四個子樹，同上，只能加入第三個子樹即8的位置，與8共同組成原8所在位置節點的孩子節點。更新樹的結構后，如前調用BCP的算法可得到新的密鑰。具體算法為：成員8和新成員共同協商一個子密鑰，選成員8為代表，同時，成員6、7、9視成員8離開，由9作為UGC調用remove算法更新子密鑰，此后看成成員8加入成員6、7、9，調用join算法共同協商出本輪更新的子密鑰。在下一輪中，成員1、6、11、17協商密鑰，分別視成員6離開和加入，最終得到新群密鑰。

3）成員離開

假設群{U1，…，Um}中成員U由于某種原因主動或被動地離開群，同樣他離開的原則是離開后應該能夠保證樹的結構不會改變。然而成員離開是隨意的，任何成員都有可能離開，不像加入可以指定加入確定的位置而不會影響樹的結構。在這種情況下，同樣用圖1來描述。如果成員13離開一定不會影響樹結構，而且只有13或14離開不會影響樹的結構。但若成員22離開，定會影響，此時讓成員13（或14）離開原位置代替22的位置，這樣問題就解決了，其他成員離開采用同樣的方法。具體描述見文獻[7]。樹結構確定后，調用BCP中的算法可得更新密鑰。圖1中若成員22離開，由成員13來代替。在第三個子樹中，成員11、12、15分別視成員14離開和加入（如2．3節方法），算出本輪更新的子密鑰；同時，在第四個子樹中，成員13與21協商一個密鑰，并選成員21為代表，在成員17、18、19、21協商密鑰時分別視成員21離開和加入，他們能算出本輪更新的子密鑰。在下一輪中，成員1、6、11、17協商密鑰時，視成員11和17離開和加入，最終得到新群密鑰。

2 安全性分析

2.1 隨機預言機模型

隨機預言機模型也稱為理想hash模型，在隨機預言機模型中，密碼學hash函數被用做隨機函數，該模型下的安全性證明將hash函數當做預言機，在有新的提問時產生可靠的隨機值，并且兩次相同的提問會得到相同的回答。在hash函數不可攻破的前提下，隨機預言機模型下的分析在保證眾多密碼體制的安全性方面是非常成功的。

2.2 基本定義

通常假設不安全的信道上存在兩種攻擊者，即主動攻擊者和被動攻擊者，這兩者都是概率多項式時間的圖靈機。被動攻擊者只能竊聽信道上傳送的消息，并試圖從截獲的消息中分析出會話密鑰。主動攻擊者則能夠完全控制信道，他可以竊聽、刪除和修改信道上的消息。群密鑰協商協議必須抗被動攻擊與主動攻擊。此外，對于動態對等網來說，完全前向安全性和密鑰獨立性也是兩個至關重要的安全性要求。在具體的分析之前，先來回顧以下幾個定義。

群Diffie-Hellman方案一直都是基于不同的困難問題的，或基于的假設能規約為困難問題。在素數階循環群G=〈g〉中，常使用的假設有：

定義1 DDH。已知G中的兩個元素gu和gv，區分guv和任意一個隨機數是計算困難的。

定義2 G-DDH。已知元素下標i的集合的一些子集（或是除了{1，…，n}的所有子集，或是所有子集中的部分集合），按照各子集中包含的下標號找出元素計算出所有的gxi，區分gx1…xn和任意的隨機數是計算困難的。

在隨機預言機模型下，通常使用CDH和G-CDH假設：

定義3 CDH。已知G中的兩個元素gu和gv，計算guv是計算困難的。

定義4 G-CDH。已知元素下標i的集合的一些子集（或是除了{1，…，n}的所有子集，或是所有子集中的部分集合），按照各子集中包含的下標號找出元素計算出所有的gxi，計算gx1…xn是計算困難的。

顯然，如果存在算法A求解CDH，那么，算法A也可以解決DDH。一般情況下，假設CDH和DDH都是困難問題，而且很多密碼體制都是建立在這種困難假設之上的。

定義5 密鑰獨立性。如果動態密鑰協商協議同時滿足前向保密性和后向保密性，則稱該協議滿足密鑰獨立性。

a）前向保密性，新加入群的成員不能獲得之前群的會話密鑰。

b）后向保密性，離開群的成員不能獲得之后群的會話密鑰。

顯而易見，在現實中要求動態協議滿足密鑰獨立性是必要的。此外，對于密鑰生成協議，通常希望在成員的長期密鑰泄露的情況下，利用長期密鑰協商的會話密鑰仍然是安全的。Günther^[9]首先提出此思想，稱之為完全前向安全性(PFS)。

定義6 完全前向安全性。如果成員的長期密鑰泄露不會削弱利用這些長期密鑰生成的會話密鑰的安全性，則稱這個密鑰生成協議滿足完全前向安全性。

2.3 安全性分析

定理1 正確性。如果所有成員都是誠實的，那么他們一定可以計算出相同的會話密鑰，而且惡意成員無法欺騙其他成員生成不同的會話密鑰。

證明 如果成員都是誠實的，那么每個成員都成功驗證前一個成員的中間數據是可靠的，用選取的私鑰和前一個成員發送給他的數據進行計算得到他的中間數據并發送給下一個成員，這些中間數值都是可靠的，直到下標最大的成員收到前一個成員的中間數據，并將他計算的中間數據廣播給其他成員，其他成員驗證數據的可靠性后用中間數據中的有用數值結合自己的私鑰可準確地計算出最終會話密鑰。

定理2 一個被動的攻擊者得不到會話密鑰的任何信息。

證明 被動攻擊者試圖通過竊聽信道中傳輸的數據來掌握關于會話密鑰的信息。本文通過證明攻擊者在公開信道竊取的成員U的信息可以在不知道成員私鑰的情況下仿真來證明攻擊者得不到成員U的任何信息。

本文用兩組隨機量來模擬攻擊者看到的值和仿真的值，如果不存在概率多項式時間算法能夠區分這兩組值，這兩組值是計算不可分的。由于仿真值是在不知道成員私鑰的情況下構造的，并且和真值是計算不可分的，攻擊者得不到任何與成員秘密有關的信息。需要一個假設來證明仿真值與真值是計算不可分的，即G-DDH困難問題。得證。

定理3 在隨機預言機模型的假設下，協議抗主動攻擊。

證明 主動攻擊者可以自由選擇子會話密鑰，并且順利完成子密鑰加密過程；然后，他必須假冒合法用戶對消息簽名才能通過下一個成員的驗證。假設hash函數的確是一個隨機預言機模型，那么容易證明，如果攻擊者可以偽造用戶的簽名，則該用戶的私鑰可以被計算出來，而這是不可能的。

定理4 新加入群的成員不能獲悉之前群的會話密鑰；離開群的成員不能獲悉之后群的會話密鑰。

證明 成員加入群時，他所看到的群管理員生成的中間數值已經被群管理者加入隨機數更新，所以他不可能得知以前群的會話密鑰。同樣，在成員離開群時，群管理者將選取新隨機數更新他的中間信息廣播給其余成員從而更新了會話密鑰，因此他同樣不能得知以后群的會話密鑰。

定理5 協議滿足密鑰獨立性。

證明 由定理4，新加入群的成員不能獲悉之前群的會話密鑰，滿足前向保密性；離開群的成員不能獲悉之后群的會話密鑰，滿足后向保密性。因此，滿足密鑰獨立性。

定理6 即使群成員的長期密鑰不慎泄露，利用這些長期密鑰生成的會話密鑰仍然是安全的。

證明 在協議中，長期密鑰用來加密中間數據流，而成員隨機選取的私鑰在執行下一次協議時會更新。因此，即使長期密鑰泄露，這些私鑰仍然是安全的，攻擊者不可能得到會話密鑰。

3 結束語

本文提出的基于n叉樹的密鑰協商方案適合在大群組密鑰協商中進一步減少輪數以減少計算復雜度。總之，樹在密鑰協商中的作用很早就提出，因此，在密鑰協商中要多加利用。本文的方案可以看做一個基于樹的密鑰協商的一個擴展和延伸，根據實際情況可以將n量化來加以使用。

參考文獻：

［1］DIFFIE W，HELLMAN M.New directions in cryptography[J].IEEE Trans on Information Theory，1976，IT-22(6):644-654.

[2]BRESSON E，CHEVASSUT O，POINTCHEVAL D，et al.Provably authenticated group Diffie-Hellman key exchange[C]//Proc of the 8th ACM Conference on Computer and Communications Security.New York:ACM Press， 2001:255-264.

[3]BRESSON E，CHEVASSUT O，POINTCHEVAL D.Provably authenticated group Diffie-Hellman key exchange:the dynamic case[C]//Proc of the 7th International Conference on the Theory and Application of Cryptology.Berlin:Springer，2001:290-309.

[4]BRESSON E，CHEVASSUT O，POINTCHEVAL D.Dynamic group Diffie-Hellman key exchange under standard assumptions[C]//Proc of the 8th International Conference on the Theory and Application of Cryptographic Techniques.London:Springer-Verlag， 2002:321-336.

[5]BARUA R，DUTTA R，SARKAR P.Extending Joux’s protocol to multi party key agreement[C]//Proc of the 4th International Confe-rence on Cyrptology.Berlin:Springer，2003:33-60.

[6]DUTTA R，BARUA R，SARKAR P.Provably secure authenticated tree based group key agreement[C]//Proc of the 6th International Confe-rence on Information and Communications Security.Berlin:Springer，2004:92-104.

[7]DUTTA R，BARUA R.Dynamic group key agreement in tree-based setting[C]//Proc of the 10th Australasian Conference on Information Security and Privacy.Berlin:Springer，2005:101-112.

[8]DUTTA R，BARUA R.Overview of key agreement protocols，report 2005/289[R/OL].(2005).http://eprint.iacr.org/2005/289.ps.

[9]GNTHER C G.An identity-based key-exchange protocol[C]//

Proc of Workshop on the Theory and Application of Cryptographic Techniques.New York:Springer-Verlag，1990:29-37.