無可信中心的門限追蹤ad hoc網(wǎng)絡(luò)匿名認(rèn)證

(1. 南京理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210094；2.南京炮兵學(xué)院 計(jì)算機(jī)教研室，江蘇 南京 211132)

1 引言

Ad hoc網(wǎng)絡(luò)由于具有不需要基礎(chǔ)設(shè)施、自組織、自管理等特點(diǎn)，使其在軍事戰(zhàn)場、搶險(xiǎn)救災(zāi)等環(huán)境中得到越來越多的應(yīng)用。但由于ad hoc網(wǎng)絡(luò)自身的特性，如使用無線信道作為傳輸介質(zhì)，使其安全性面臨很大的威脅，其中節(jié)點(diǎn)身份的匿名性（私密性），得到越來越多的關(guān)注，如ANODR[1]、A3RP[2]等協(xié)議。在ad hoc網(wǎng)絡(luò)環(huán)境下，通信中節(jié)點(diǎn)身份的匿名性研究比較多，如ANODR[1]等匿名路由協(xié)議，而在認(rèn)證中節(jié)點(diǎn)身份的匿名性研究較少；且由于ad hoc網(wǎng)絡(luò)的自組織性、無中心性，使傳統(tǒng)網(wǎng)絡(luò)中的基于可信中心的匿名認(rèn)證方案不再適合，所以提出新的適合ad hoc網(wǎng)絡(luò)的匿名認(rèn)證方案非常有必要。

Jung等[2]提出的A3RP協(xié)議，以及田子健等[3]提出的動態(tài)可追蹤的匿名認(rèn)證方案，雖能提供匿名認(rèn)證，但它們都需要一個(gè)可信中心TA參與匿名認(rèn)證，導(dǎo)致權(quán)利過于集中以及單點(diǎn)失效等問題，這與ad hoc網(wǎng)絡(luò)的無中心性相違背；Zhimin等[4]將可信計(jì)算及One-Way Accumulator引入匿名認(rèn)證中，降低了協(xié)議計(jì)算量，且不需要可信第三方參與，但示證者（被認(rèn)證者）身份無法追蹤；為了解決ad hoc網(wǎng)絡(luò)中節(jié)點(diǎn)匿名認(rèn)證及示證者追蹤問題而又不引入可信第三方，本文提出一種無可信中心的門限追蹤ad hoc網(wǎng)絡(luò)匿名認(rèn)證方案。方案提供對任意節(jié)點(diǎn)合法性的認(rèn)證，而不暴露示證者身份；通過門限機(jī)制實(shí)現(xiàn)任意k個(gè)合法節(jié)點(diǎn)可聯(lián)合追蹤示證者身份，而不需要管理員等可信第三方參與，亦不會導(dǎo)致任意合法節(jié)點(diǎn)都可追蹤示證者身份的過于自由、隨意性等問題；方案的整個(gè)執(zhí)行過程，不需要可信第三方參與，完全符合ad hoc網(wǎng)絡(luò)的無中心、自組織、自管理等特性。

2 無可信中心的門限追蹤匿名認(rèn)證模型及安全要求

定義 1 認(rèn)證方案的匿名性：示證者不暴露自己的身份而能向驗(yàn)證者證明自己身份的合法性。

定義 2 認(rèn)證方案的可追蹤性：在需要的情況下，能夠根據(jù)陷門信息及驗(yàn)證者提供的信息，恢復(fù)出示證者的身份。

定義3 無可信中心性：從方案的初始化開始，整個(gè)方案不涉及可信中心。

匿名認(rèn)證階段，任意節(jié)點(diǎn)Pu向任意節(jié)點(diǎn)Vu（Vu可以不屬于U）證明它屬于組織U，但不透露Pu的身份。若想知道已通過匿名認(rèn)證的節(jié)點(diǎn)Pu的身份，則必須經(jīng)U中至少k個(gè)節(jié)點(diǎn)同意，方可恢復(fù)出Pu的身份，實(shí)現(xiàn)Pu身份的追蹤。

整個(gè)模型包括如下過程。

1) 初始化：群組織中各成員生成自己的簽名公私鑰對，并相互協(xié)作建立群公鑰及群共享秘密（匿名認(rèn)證中的追蹤陷門信息）。

2) 匿名認(rèn)證過程：示證者利用自己的簽名私鑰及群公鑰生成一個(gè)簽名，驗(yàn)證者對示證者的簽名進(jìn)行驗(yàn)證，整個(gè)過程不暴露示證者的身份信息。

3) 追蹤算法：k個(gè)成員聯(lián)合利用追蹤陷門等信息恢復(fù)出示證者身份。

4) 新成員加入算法：新成員與群組織中各成員相互協(xié)商，以更新群公鑰、群追蹤陷門等信息。

5) 成員撤銷算法：節(jié)點(diǎn)離開后，剩余節(jié)點(diǎn)相互協(xié)商以更新群公鑰、群追蹤陷門等信息。

一個(gè)無可信中心的陷門追蹤ad hoc網(wǎng)絡(luò)匿名認(rèn)證方案是安全的，若滿足以下條件。

1) 正確性：群組織中任意一個(gè)成員執(zhí)行匿名認(rèn)證中的簽名算法后，輸出的簽名都能通過匿名認(rèn)證中的簽名驗(yàn)證算法。

3) 可追蹤性：群組織中任意k個(gè)合法成員，可聯(lián)合恢復(fù)出已通過認(rèn)證的示證者身份。

4) 完備性：任何不屬于組織 U的節(jié)點(diǎn)，皆不能通過匿名認(rèn)證。

5) 追蹤的(k, n)門限性：必須至少k個(gè)合法成員聯(lián)合，方可追蹤示證者身份。

6) 無可信中心性：從系統(tǒng)建立至匿名認(rèn)證及身份追蹤，皆不需要可信第三方的參與。

3 相關(guān)技術(shù)介紹

3.1 假設(shè)

離散對數(shù)假設(shè)：設(shè)G為g生成的一個(gè)階為q的循環(huán)群。不存在概率多項(xiàng)式時(shí)間算法A，其能以不可忽略的概率從ag計(jì)算出a。

確定的Diffie-Hellman(DDH）假設(shè)：設(shè)G為g生成的一個(gè)階為q的循環(huán)群。不存在概率多項(xiàng)式時(shí)間算法A，其能以不可忽略的概率區(qū)分出分布D和R，

3.2 民主簽名

使用群簽名實(shí)現(xiàn)匿名認(rèn)證是最直接的方法。群簽名概念最初由Chaum和Heyst提出[7]，目前較好的群簽名方案由 Ateniese[8]等提出。群簽名實(shí)現(xiàn)匿名認(rèn)證，群管理員可以實(shí)現(xiàn)示證者身份的追蹤。由于群管理員的特殊身份，將會導(dǎo)致權(quán)利過于集中、權(quán)利濫用以及單點(diǎn)失效等問題，所以必須對群管理員加以約束。

民主簽名[9]由Manulis于2006年提出，其中任意成員可代表群進(jìn)行簽名，群內(nèi)任意成員可從給定的有效群簽名中恢復(fù)出簽名者的身份。若使用民主簽名實(shí)現(xiàn)匿名認(rèn)證方案，則群中任意成員可恢復(fù)出示證者的身份，追蹤示證者。這種追蹤能力過于自由必將導(dǎo)致不受控制的濫用，所以必須對群成員的這種追蹤能力加以控制。

將群簽名中管理員權(quán)利過于集中與民主簽名中成員追蹤能力過于自由進(jìn)行折衷，提出具有門限追蹤能力的匿名認(rèn)證方案，使得至少k個(gè)群成員同意恢復(fù)示證者身份時(shí)，方能追蹤到示證者身份。

3.3 秘密共享

(k, n)門限秘密共享是指將一個(gè)秘密s分成n個(gè)份額s1, s2,…,sn，并將這些秘密份額秘密地分發(fā)給n個(gè)用戶，使得發(fā)生如下情況。

1) 由k個(gè)或多于k個(gè)用戶擁有的秘密份額 si可以恢復(fù)出秘密s。

2) 由少于 k個(gè)用戶持有的秘密份額 si不能獲得關(guān)于秘密 s的任何信息。這里 k稱為門限，且1≤k≤n。

Shamir[10]于 1979年提出的基于多項(xiàng)式拉格朗日插值的(k, n)門限方案。該方案有如下2個(gè)缺點(diǎn)：1)不能檢測可信中心分發(fā)假的份額給用戶；2)該方案需要一個(gè)可信的中心。隨后Feldman提出了可驗(yàn)證秘密共享方案，Pedersen[11]提出了無可信中心的秘密共享方案。由于ad hoc網(wǎng)絡(luò)的無中心性、自組織性等特點(diǎn)，本文選用Pedersen的無可信中心的秘密共享方案，并將其應(yīng)用于匿名認(rèn)證方案中，從而實(shí)現(xiàn)本方案的門限追蹤能力。

4 匿名認(rèn)證協(xié)議

借助群簽名、民主簽名以及無可信中心的秘密共享思想，實(shí)現(xiàn)了無可信中心的門限追蹤ad hoc網(wǎng)絡(luò)匿名認(rèn)證方案。本方案主要包括系統(tǒng)初始化、匿名認(rèn)證、示證者追蹤、新成員加入以及成員吊銷等過程。

4.1 系統(tǒng)初始化

系統(tǒng)初始化的目的是建立各節(jié)點(diǎn)簽名公私鑰對、群共享秘密S（匿名認(rèn)證中的追蹤陷門）、群公鑰 PU。

1) 選取素?cái)?shù)q，G為q階循環(huán)群，其上離散對數(shù)問題是困難的，g為生成元；k是門限值，n是用戶數(shù)；散列函數(shù)為安全參數(shù)。

2) 節(jié)點(diǎn) ui選取 Si∈Zq作為自己的簽名私鑰，計(jì)算對應(yīng)的簽名公鑰為 Pi= gSi。

3) ui在 Zq上選擇 k-1次多項(xiàng)式

4) ui計(jì)算 yij=fi(j) mod q , 1 ≤ j ≤ n ,并將 yij秘密發(fā)送給節(jié)點(diǎn) uj,節(jié)點(diǎn) ui保留 yii。

5) 節(jié)點(diǎn) ui收到其他所有節(jié)點(diǎn)的 yji，并計(jì)算yi即是節(jié)點(diǎn) ui的秘密份額。

6) 群共享秘密S的計(jì)算方法。

任意k個(gè)節(jié)點(diǎn)可利用自己的秘密份額通過拉格朗日插值法計(jì)算出群共享秘密S，群秘密S即為匿名認(rèn)證中的追蹤陷門。

7) 群公鑰計(jì)算方法。

初始化結(jié)束后，每個(gè)節(jié)點(diǎn)擁有自己的公私鑰對(Si, Pi)、自己的秘密份額 yi以及群公鑰 PU。

4.2 匿名認(rèn)證過程

節(jié)點(diǎn) uP想向節(jié)點(diǎn) uV證明自己屬于組織 U，則uP使用自己的簽名私鑰及群公鑰生成一群簽名，并把此簽名交給 uV驗(yàn)證，若驗(yàn)證通過則說明 uP屬于組織U，否則 uP不屬于組織U。匿名認(rèn)證過程主要包括簽名生成算法和簽名驗(yàn)證算法。

1) 示證者 uP簽名的生成算法

參照民主簽名[9]，給出如下簽名算法，算法的輸入為 uP的私鑰 Sp、群公鑰 PU，待簽名消息為m∈ { 0,1}*， uP執(zhí)行如下計(jì)算。

2) 簽名驗(yàn)證算法

uV接收到sign(m )后，利用群公鑰 PU以及消息m，驗(yàn)證如下等式是否成立：

如果成立，則簽名認(rèn)證通過，說明Pu是U中合法節(jié)點(diǎn)；否則認(rèn)證不通過。在此身份認(rèn)證過程中，驗(yàn)證者只能確定示證者是群中的某個(gè)成員，而不能確定是哪一個(gè)成員，即實(shí)現(xiàn)了示證者身份的匿名性。

4.3 示證者身份追蹤算法

為了在必要情況下實(shí)現(xiàn)示證者身份的追蹤，組織 U中的任意 k個(gè)成員 { u1′, u2′,… ,uk′} ? U ={u1,u2,… ,un}，可聯(lián)合利用群追蹤陷門恢復(fù)出示證者的身份，具體步驟如下。

1) k個(gè)節(jié)點(diǎn)使用自己的秘密份額 y1′, y2′,… ,yk′， x0以及對應(yīng)的 c1′, c2′,… , ck′聯(lián)合計(jì)算出 T =x0S

3) 輸出示證者的簽名公鑰，即可得到示證者身份。

4.4 節(jié)點(diǎn)加入算法

新節(jié)點(diǎn)的加入，將導(dǎo)致群公鑰、追蹤陷門以及各節(jié)點(diǎn)秘密份額的更新。假設(shè)節(jié)點(diǎn) ux想加入到組織 U中，且組織U中目前節(jié)點(diǎn)數(shù)為n，則執(zhí)行如下步驟。

1) 節(jié)點(diǎn) ux選取 Sx∈Zq作為自己的簽名私鑰，計(jì)算對應(yīng)的簽名公鑰為 Px= gSx； ux在 Zq上選擇k-1次多項(xiàng)式 fx(x) = ax0+ax1x + …+ax,k-1xk-1，并計(jì)算 yxj=fx( j) mod q , 1 ≤ j ≤ n +1,并將 yxj秘密 發(fā)送給節(jié)點(diǎn) uj,節(jié)點(diǎn) ux保留 yxx。

2) 組織U中原有節(jié)點(diǎn) ui計(jì)算 yix=fi( x) mod q,1,in≤≤并將ixy秘密發(fā)送給節(jié)點(diǎn)xu。

3) 節(jié)點(diǎn)xu收到其他所有節(jié)點(diǎn)的ixy，并計(jì)算即是節(jié)點(diǎn)xu的秘密份額。

5) k個(gè)節(jié)點(diǎn)聯(lián)合利用拉格朗日插值算法，計(jì)算新的追蹤陷門，進(jìn)而得到新的群公鑰。

4.5 節(jié)點(diǎn)吊銷算法

由于節(jié)點(diǎn)的移動性等原因，致使節(jié)點(diǎn)離開組織U，將導(dǎo)致群公鑰、追蹤陷門以及各節(jié)點(diǎn)秘密份額的更新。假設(shè)節(jié)點(diǎn) uj離開組織 U，且 uj離開前 U中的節(jié)點(diǎn)數(shù)為n，則執(zhí)行如下步驟。

1) 組織 U中各節(jié)點(diǎn)計(jì)算新的秘密份額，且新的秘密份額為 yi′ =yi-yji，i≠j，且1≤i≤n。

2) k個(gè)節(jié)點(diǎn)通過拉格朗日插值算法，計(jì)算新的追蹤陷門，以及新的群公鑰。

5 協(xié)議分析

5.1 協(xié)議性質(zhì)分析

定理1 匿名性：本方案在確定的Diffie-Hellman(DDH)假設(shè)的前提下，可保證示證者的匿名性。

以下論證皆在DDH假設(shè)的前提下進(jìn)行。r的隨機(jī)性，可保證0y與示證者公鑰PP的無關(guān)聯(lián)性。由1ir、的隨機(jī)性，決定了 xi、 yi及 zi的隨機(jī)性。由于 cP由 xi， yi及 zi決定，因此不能從 S1P、 S2P中推導(dǎo)出示證者的公私鑰，亦找不出 S1P、 S2P與示證者身份的關(guān)聯(lián)性，所以無法從消息m的簽名中判斷出簽名者的身份。匿名性的形式化數(shù)學(xué)證明可參照文獻(xiàn)[9]。

定理2 可追蹤性：任意k個(gè)合法群組織成員，可聯(lián)合恢復(fù)出通過認(rèn)證的示證者身份。

其中，PP即為示證者的公鑰，根據(jù)公鑰即可找到示證者身份。

定理 3 正確性：群組織中任意一合法成員，可通過匿名認(rèn)證。

生成算法及簽名驗(yàn)證算法中的 uP為隨機(jī)選取的，故對群中任意成員 uX及其對消息 m的簽名sign(m)，都存在一多項(xiàng)式時(shí)間算法Verify，使得Verify( SX,PU, m. s ign(m )) = 1（1表示簽名有效，通過匿名認(rèn)證；0表示無效）。

定理4 完備性（不可冒充性）：非群組織成員，不能通過匿名認(rèn)證。

由于匿名認(rèn)證中簽名算法的第6步需要簽名者私鑰的參與，而非組織成員沒有合法的私鑰，從而導(dǎo)致生成的簽名不能通過驗(yàn)證者的驗(yàn)證。

定理 5 無中心性：本方案不需要可信第三方參與。

本方案各階段皆不需要可信第三方參與。系統(tǒng)初始化階段，各節(jié)點(diǎn)生成自己的簽名公私鑰，并使用無可信中心的秘密分享方案協(xié)商生成群追蹤陷門及群公鑰；匿名認(rèn)證階段，示證者選擇相應(yīng)隨機(jī)數(shù)并生成簽名，而驗(yàn)證階段只需驗(yàn)證者參與；新節(jié)點(diǎn)加入及節(jié)點(diǎn)吊銷階段，只需群內(nèi)各節(jié)點(diǎn)相互協(xié)作更新群追蹤陷門及群公鑰即可，所以方案這個(gè)過程沒有可信第三方的參與。

定理6 追蹤的（k, n）門限性：若要追蹤示證者身份，則必須至少k個(gè)合法節(jié)點(diǎn)同意參與方可。

若想恢復(fù)示證者身份，則必須得到群陷門信息。群陷門信息則由k個(gè)節(jié)點(diǎn)的秘密份額通過拉格朗日插值法方能得出。若少于k個(gè)節(jié)點(diǎn)，則不能恢復(fù)出群陷門信息，亦不能恢復(fù)出示證者的身份。示證者身份追蹤的(k, n)門限性，既避免了群簽名中的管理員權(quán)利過大而導(dǎo)致的各種問題，又避免了民主簽名中各節(jié)點(diǎn)追蹤能力過于自由而導(dǎo)致不受控制的濫用等問題。

定理 7 簽名的無關(guān)聯(lián)性：本方案中示證者 2次提供的簽名具有無關(guān)聯(lián)性，可抵抗對簽名的一致性攻擊。

5.2 節(jié)點(diǎn)移動性分析

第4.4節(jié)及第4.5節(jié)的節(jié)點(diǎn)加入、吊銷算法，很好地滿足了ad hoc網(wǎng)絡(luò)節(jié)點(diǎn)的移動性。節(jié)點(diǎn)加入（或者離開）群組織，將激活節(jié)點(diǎn)加入算法（節(jié)點(diǎn)吊銷算法）更新群公鑰、追蹤陷門以及各節(jié)點(diǎn)秘密份額，從而保證后續(xù)的匿名認(rèn)證及追蹤的成功性。特別地，

1) 節(jié)點(diǎn)的大量離開，導(dǎo)致 n＜k，此時(shí)已打破Pedersen的秘密共享方案，故需從新選取k；

2) 節(jié)點(diǎn)的大量加入，導(dǎo)致k遠(yuǎn)小于n，安全性下降，由于節(jié)點(diǎn)的大量加入，惡意節(jié)點(diǎn)個(gè)數(shù)超過 k的可能性增加，而k個(gè)節(jié)點(diǎn)聯(lián)合可恢復(fù)出示證者的身份，故需從新選取k，k的選取方式可參照Pedersen的秘密共享方案。

5.3 協(xié)議比較

與現(xiàn)有匿名認(rèn)證協(xié)議相比較，本協(xié)議同時(shí)具有示證者身份的匿名性、無中心性、門限可追蹤性，結(jié)果如表1所示。

表1 協(xié)議性質(zhì)比較

5.4 匿名認(rèn)證階段計(jì)算量分析

簽名算法中，計(jì)算量主要是計(jì)算ix、iy和iz的指數(shù)運(yùn)算，復(fù)雜度與普通的公鑰運(yùn)算相同，且隨著群組織中成員數(shù)的增加，計(jì)算量成線性增加。分析可知，驗(yàn)證階段的計(jì)算量與簽名過程相同。

5.5 建立可檢測秘密共享方案

系統(tǒng)建立階段，若群組織內(nèi)有惡意節(jié)點(diǎn)，發(fā)送虛假秘密ijy以破壞秘密共享機(jī)制的建立，可通過建立可檢測秘密共享方案抵制惡意節(jié)點(diǎn)，具體實(shí)現(xiàn)方案可在4.1節(jié)系統(tǒng)建立階段，加入以下2步。

1)ui計(jì)算并廣播

2)uj驗(yàn)證從iu處收到的秘密ijy：

若等式成立，則秘密ijy有效，否則ijy無效。若ijy無效，則ju可廣播一個(gè)對iu的抱怨。

等式正確性分析：

6 結(jié)束語

由于ad hoc網(wǎng)絡(luò)的無中心性、自組織性，使傳統(tǒng)網(wǎng)絡(luò)中的匿名認(rèn)證方案不再適合。本文提出一種適合ad hoc網(wǎng)絡(luò)的匿名認(rèn)證方案，本方案將民主簽名與無中心的秘密分享方案應(yīng)用到匿名認(rèn)證中，實(shí)現(xiàn)了在不需要可信中心的參與下，示證者身份的匿名性、可追蹤性及不可冒充性，并給出了相應(yīng)的匿名認(rèn)證算法、追蹤算法、節(jié)點(diǎn)加入算法及節(jié)點(diǎn)吊銷算法。

[1] KONG J J, HONG X Y, GERLA M. An identity-free and on-demand routing scheme against anonymity threats in mobile ad hoc networks[J]. IEEE Transactions on Mobile Computing, Frequency,2007,6:888-902

[2] PAIK J H, KIM B H, LEE D H. A3RP: anonymous and authenticated ad hoc routing protocol[A]. Information Security and Assurance[C].2008.

[3] 田子健, 王繼林, 伍云霞. 一個(gè)動態(tài)可追蹤匿名認(rèn)證方案[J]. 電子與信息學(xué)報(bào), 2005,27(11): 1737-1740.TIAN Z J, WANG J L, WU Y X. A dynamic anonymous authentication scheme with identity escrow[J]. Journal of Electronics & Information Technology, 2005,27(11): 1737-1740.

[4] XU Z M, TIAN H, LIU D S, et al. A ring-signature anonymous authentication method based on one-way accumulator[A]. Communication Systems, Networks and Applications[C]. 2010. 56-59.

[5] ZHOU L, HAAS Z. Securing ad hoc networks[J]. IEEE Network,2000, 13(6): 24-30.

[6] KONG J, ZERFOS P, LUO H, et al. Providing robust and ubiquitous security support for mobile ad hoc networks[A]. Washington: IEEE Computer Society[C]. 2001.251-261.

[7] CHAUM D, HEYST E. Group signatures[A]. Cryptology-EUROCRYPT’91[C]. 1991. 257-265.

[8] ATENISES G, CAMENISCH J, JOYE M, et al. A practical and provably secure coalition-resistant group signature[A]. Cryptology-CRYPTO 2000[C]. Santa Barbara, California, USA, 2000.255-270.

[9] MANULIS M. Democratic group Signature: on example of joint ventures[A]. Proceedings of ACM Symposium on Information[C].2006. 191-196.

[10] SHAMIR A. How to share a secret[J]. Communications of the ACM,1979, 22(1):612-613.

[11] PEDERSEN T P. Non-interaetive and information-theoretic secure verifiable secret sharing[A]. Cryptology-CRYPTO’91[C]. Berlin,1992. 129-140.