肖俊芳，廖劍，曾貴華

（1. 工業(yè)和信息化部電子科學(xué)技術(shù)情報(bào)研究所，北京 100040；2. 普天信息技術(shù)研究院有限公司 北京 100080；3. 上海交通大學(xué) 電子工程系，上海 200030）

1 引言

無線傳感器網(wǎng)絡(luò)（WSN）廣泛應(yīng)用于軍事、環(huán)境監(jiān)測、醫(yī)療、智能建筑和其他商業(yè)領(lǐng)域。在無線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)規(guī)模頗為龐大，節(jié)點(diǎn)數(shù)目較多；節(jié)點(diǎn)在電池能量、計(jì)算能力和存儲容量方面都有限制；節(jié)點(diǎn)因能量耗盡而失效或離開都是非常常見的現(xiàn)象。這些特點(diǎn)給無線傳感器網(wǎng)絡(luò)安全協(xié)議的設(shè)計(jì)提出了更高的要求，安全成為制約無線傳感器網(wǎng)絡(luò)進(jìn)一步廣泛應(yīng)用的關(guān)鍵。

環(huán)簽名首先由Rivest等[1]提出。在一般環(huán)簽名的應(yīng)用場景中，節(jié)點(diǎn)群的規(guī)模及相應(yīng)的PKI（公鑰體系）對節(jié)點(diǎn)能量和性能消耗影響較大。針對無線傳感器網(wǎng)絡(luò)的特點(diǎn)，安全協(xié)議的選取受到通信帶寬、存儲空間、計(jì)算量、能量消耗和抵御各種已知安全攻擊等方面的影響，因此設(shè)計(jì)合適的環(huán)簽名方案，由一個經(jīng)常變化的子群代替整個群完成簽名，才更加適合無線傳感器網(wǎng)絡(luò)。

Crescenzo提出在自組織網(wǎng)絡(luò)中應(yīng)該注意的 2個基本安全問題[2]。第一，單個節(jié)點(diǎn)的失效，即避免由于關(guān)鍵節(jié)點(diǎn)的失效而導(dǎo)致嚴(yán)重的系統(tǒng)事件；第二，服務(wù)的可用性，即某個服務(wù)請求被提出時，系統(tǒng)能確保足夠的節(jié)點(diǎn)資源來滿足服務(wù)需求。Stefaan[3]提出一個可以使多個節(jié)點(diǎn)相互協(xié)作去認(rèn)證信息的方案，但是該方案需要一個節(jié)點(diǎn)起到完全的支撐整個系統(tǒng)運(yùn)行的作用。一旦該節(jié)點(diǎn)失效，對于整個系統(tǒng)將是災(zāi)難性的。Liu引入新的概念－聯(lián)系性[4]，并針對自組織網(wǎng)絡(luò)提出第一個具備聯(lián)系性的環(huán)簽名（LSAG）方案。但是LSAG方案中架構(gòu)的(t,n)門限環(huán)簽名方案需要每個節(jié)點(diǎn)生成一個環(huán)簽名，然后再將所有節(jié)點(diǎn)生成的n個簽名組合，形成(t,n)門限環(huán)簽名，使得每個節(jié)點(diǎn)的計(jì)算量和存儲空間的消耗都非常大。Qi[5]采用門限密碼學(xué)中的(t,n)秘密共享方法，提高了基于身份的加密簽名(IBES)系統(tǒng)中密鑰生成中心(PKG)的可信性，并應(yīng)用于無線傳感器網(wǎng)絡(luò)。Tony提出第一個盲自發(fā)匿名群簽名（SAG， spontaneous anonymous group）[6]，在此方案的基礎(chǔ)上，架構(gòu)(t,n)門限環(huán)盲簽名。在環(huán)簽名的架構(gòu)基礎(chǔ)上，Javier針對自組織網(wǎng)絡(luò)的通用接入架構(gòu)[7]，提出一個環(huán)簽名架構(gòu)。基于該方案Javier也提出了門限簽名方案，并且給出了安全性證明，包括正確性、匿名性以及在選擇消息攻擊模式下抵御存在性偽造。Bresson[8]首次改進(jìn)了Rivest[1]環(huán)簽名方案的模型，隨后將該模型擴(kuò)展應(yīng)用至門限簽名方案和ad hoc群。此外Bresson還給出了具有較高性能的環(huán)簽名方案，并給出在隨機(jī)預(yù)言機(jī)模型下的安全性證明。

本文基于雙線性配對提出一個新的門限簽名方案可適用于無線傳感器網(wǎng)絡(luò)，同時給出正確性、匿名性和抵御存在性偽造的證明。在假設(shè)計(jì)算Diffie-Hellman（CDH, computational Diffie-Hellman）問題困難的前提下，給出在隨機(jī)預(yù)言機(jī)模型下的安全性證明，結(jié)論證明本文所提的方案可以在自適應(yīng)選擇消息攻擊模式下抵御存在性偽造。除此之外本文所提方案還具備以下特點(diǎn)。

1) 頑健性：群合作的條件下可以在合作生成簽名的過程中檢測所有節(jié)點(diǎn)是否運(yùn)行錯誤的行為和步驟，同時可以防御一些惡意的節(jié)點(diǎn)對整個群造成的影響。

2) 多簽：群內(nèi)的所有節(jié)點(diǎn)可以自由選擇自己需要發(fā)布的消息，在簽名中可以一次性對所有的消息進(jìn)行簽名。多簽現(xiàn)在被廣泛應(yīng)用于移動代理、招投標(biāo)、電子投票、數(shù)字彩票、電子現(xiàn)金等方面。

3) 滿足分布式并行計(jì)算要求：所有參與簽名節(jié)點(diǎn)可以并行地計(jì)算自己的部分簽名，然后將部分簽名組合成為門限簽名。無需像傳統(tǒng)的環(huán)簽名，需要參與簽名的節(jié)點(diǎn)一個接著一個生成部分簽名，這樣才可以組成一個環(huán)。該方法產(chǎn)生一個環(huán)簽名需要的時間非常長，增加了能量的消耗；并且如果某個節(jié)點(diǎn)失效，需要重新定義群內(nèi)參與簽名的節(jié)點(diǎn)次序，浪費(fèi)較多的資源。因此本文提出的門限環(huán)簽名方案非常適合無線傳感器等網(wǎng)絡(luò)。

2 門限環(huán)簽名的語法及安全模型

一個門限環(huán)簽名方案應(yīng)該包含至少3個算法(Setup,Sign,Verify)，算法定義如下。

1)Setup算法：該算法是一個PPT（probabilistic polynomial time）算法，它的表達(dá)式為：Setup(1k,N)=

3)Verify算法：通常是確定性算法，是對Sign算法的輸出進(jìn)行有效性的檢驗(yàn)，輸出是Ture或者False。該算法的表達(dá)式為：Verify(1k,N, m, Ppub,={0,1}。

以上定義的門限環(huán)簽名方案是一個最簡化的版本。對于門限環(huán)簽名方案至少需要有3個方面的要求：正確性、匿名性和抵御存在性偽造。

與Benoit[9]、Sherman[10]定義類似，本文給出門限環(huán)簽名的安全模型：定義在隨機(jī)預(yù)言機(jī)模型下，宣稱一個(,)t n門限環(huán)簽名方案可以抵御自適應(yīng)選擇消息攻擊，那么應(yīng)該不存在一個多項(xiàng)式邊界的偽造者（polynomially bounded forger）以不可忽略的概率完成如下的游戲。

1) 偽造者F從節(jié)點(diǎn)群N中任意選取t-1個目標(biāo)節(jié)點(diǎn)，這些節(jié)點(diǎn)可以與F一起參與偽造。F可以從挑戰(zhàn)者C處得到部分私鑰。

2) 在安全參數(shù)k的作用下，C運(yùn)行Setup算法，然后將系統(tǒng)參與發(fā)送給F。

3) F進(jìn)行多項(xiàng)式邊界次散列函數(shù)和簽名詢問。F可以根據(jù)C返回的結(jié)果動態(tài)地調(diào)整詢問值。

4) F輸出一個有效的簽名。

F輸出一個關(guān)于消息m的門限環(huán)簽名，在有n個節(jié)點(diǎn)的群內(nèi)至少需要t個節(jié)點(diǎn)參與簽名。在游戲中有2個要求：①消息m在之前的簽名和隨機(jī)預(yù)言機(jī)詢問中沒有被涉及到；②少于t個節(jié)點(diǎn)的密鑰被F獲取。當(dāng)偽造的簽名可以通過簽名驗(yàn)證算法，那么F贏得這個游戲。

3 改進(jìn)的門限環(huán)簽名方案

針對無線傳感器網(wǎng)絡(luò)的特點(diǎn)，本節(jié)提出改進(jìn)的門限環(huán)簽名方案，在簽名的構(gòu)建部分包括準(zhǔn)備、簽名和驗(yàn)證3個步驟。隨后對改進(jìn)的門限環(huán)簽名方案進(jìn)行頑健性分析，給出參與簽名的節(jié)點(diǎn)在簽名過程中如何檢測錯誤的發(fā)生。最后基于改進(jìn)的門限環(huán)簽名方案，本節(jié)提出實(shí)現(xiàn)多方數(shù)字簽名的方法。

3.1 改進(jìn)的門限環(huán)簽名算法

假設(shè)在一個無線傳感器網(wǎng)絡(luò)群內(nèi)有n個節(jié)點(diǎn)，用符號S表示，同時在WSN群內(nèi)架構(gòu)一個公鑰生成器（PKG），該P(yáng)KG可以離線預(yù)先生成各節(jié)點(diǎn)的公私鑰對。

3.1.1 Setup算法

1) 選定系統(tǒng)安全參數(shù)k，輸出q階加法群G1和q階乘法群G2，雙線性映射e: G1×G1→G2，此處q是kbit的素?cái)?shù)。

2) PKG隨機(jī)選擇G1的生成元P，隨機(jī)選擇，計(jì)算并公布公鑰Ppub=sP，隨機(jī)選擇，計(jì)算并公布Q=s′ P。

3) PKG生成一個t階多項(xiàng)式：

5) 定義密碼散列函數(shù)H:{0,1}*×G1→，其中{0,1}*表示任意長度的數(shù)據(jù)。

6) 消息明文空間m∈{0,1}*。

7) PKG將s作為系統(tǒng)私鑰，輸出系統(tǒng)參數(shù)params:

8) 在每個節(jié)點(diǎn)得到相應(yīng)的私鑰之前，WSN群內(nèi)每個節(jié)點(diǎn)Sk∈{1,…,n}都可以檢查

3.1.2 Sign算法

為了不失一般性，假設(shè)WSN群中編號為{1,…,t}的節(jié)點(diǎn)參與環(huán)簽名的生成，編號為{t+1,…,n}的節(jié)點(diǎn)不參與環(huán)簽名的生成。

1) 編號為{1,…,t}的節(jié)點(diǎn)進(jìn)行的步驟如下：對于j∈{1,…,t} 的節(jié)點(diǎn)，隨機(jī)選擇ri∈R，然后計(jì)算Ui=riP，隨后通過認(rèn)證的通道將Ui發(fā)給其他所有的節(jié)點(diǎn)。

2) 編號為{1,…,t}中的任意一個節(jié)點(diǎn)或者其他任意一個實(shí)體（只要不將其他參與簽名節(jié)點(diǎn)的身份暴露即可）進(jìn)行的步驟如下：對于j∈{t+1,…,n}的節(jié)點(diǎn)，隨機(jī)選擇rj∈R，計(jì)算

此處S表示W(wǎng)SN群中參與簽名的n個節(jié)點(diǎn)的身份；隨后將(Uj, Vj)公布；最后計(jì)算并公布。

3) 編號為{1,…,t}的節(jié)點(diǎn)進(jìn)行的步驟如下：對于j∈{1,…,t} 的節(jié)點(diǎn)，計(jì)算

3.1.3 Verify算法

1) 對于k∈(1,…,n)，驗(yàn)證者計(jì)算hk=H( m。

2) 驗(yàn)證者檢驗(yàn)等式

是否成立。如果成立，則簽名δ是有效的，否則為無效的簽名。

3.2 頑健性分析

在WSN群體簽名方案中頑健性指的是參與其中的任何節(jié)點(diǎn)可以方便地檢測出自己或者其他節(jié)點(diǎn)的行為或者計(jì)算是否發(fā)生錯誤。頑健性對于能量受限的無線傳感器網(wǎng)絡(luò)等自組織網(wǎng)絡(luò)來說是非常有意義的，一旦某個參與簽名的節(jié)點(diǎn)發(fā)生了錯誤，該節(jié)點(diǎn)可以對計(jì)算的結(jié)果進(jìn)行檢查驗(yàn)證并且加以改正。因此群體簽名方案中頑健性可以減少某個節(jié)點(diǎn)發(fā)生錯誤的幾率，避免因錯誤導(dǎo)致的通信數(shù)據(jù)量、計(jì)算等帶來的能量消耗。針對本節(jié)提出的環(huán)簽名方案，頑健性應(yīng)該具備以下特征。

1) 避免到最后生成簽名時才發(fā)現(xiàn)生成的簽名是無效的。

2) 在簽名的生成過程中，每個參與簽名的節(jié)點(diǎn)應(yīng)該可以檢驗(yàn)自身的錯誤。

在 Setup算法階段的步驟 8）中，實(shí)際上已經(jīng)在進(jìn)行頑健性檢查，每個節(jié)點(diǎn)需要計(jì)算公鑰是否是有效，進(jìn)一步判斷參與簽名的群體S是否合法。

在Sign算法階段中，所有的節(jié)點(diǎn){1,…,n}在步驟3）結(jié)束后，獲得部分簽名 δi= { hi, Ui, Vi}，因此節(jié)點(diǎn)j可以計(jì)算等式

是否成立。如果成立則該節(jié)點(diǎn)生成的部分簽名是正確的，否則該節(jié)點(diǎn)重新進(jìn)行計(jì)算。

3.3 多簽方案

與其他的群簽名方案相比較，本節(jié)提出的環(huán)簽名方案可以使WSN群中不同的簽名者對多個不同的消息同時進(jìn)行簽名。在網(wǎng)絡(luò)規(guī)模較大的密碼學(xué)應(yīng)用環(huán)境中，如果WSN群內(nèi)有簽名者想發(fā)布一個特別的信息，但是不想暴露到底是哪一個簽名者發(fā)布的，最有效的方式就是生成一個包含不同消息的群簽名。

一個典型的應(yīng)用場景就是 Yao[11]提出一個對“offer privacy”的定義，應(yīng)用于移動代理環(huán)境中，例如：有一群應(yīng)標(biāo)者參與某個項(xiàng)目的競爭性投標(biāo)，每個應(yīng)標(biāo)者給出他們的報(bào)價。為防止應(yīng)標(biāo)者抵賴，需要應(yīng)標(biāo)者對這個報(bào)價進(jìn)行簽名，保證該報(bào)價的不可偽造性。其他應(yīng)標(biāo)方可以看到該標(biāo)價，最后招標(biāo)方公布勝出的應(yīng)標(biāo)者身份，但是其他競標(biāo)失敗的應(yīng)標(biāo)者無法得知其真實(shí)的身份。針對這種應(yīng)用環(huán)境，需要一個帶offer privacy的多簽方案，本文提出的環(huán)簽名方案略加改動，即可實(shí)現(xiàn)該多簽方案。

1) Setup算法

與改進(jìn)門限環(huán)簽名算法一樣。

2) Sign算法

設(shè)定與改進(jìn)門限環(huán)簽名算法一樣，不同流程是在步驟2）和步驟3）中，對于 j ∈ { 1,… ,n }的節(jié)點(diǎn)，選取消息 mi，計(jì)算；在步驟4）中，WSN群S輸出針對消息 { m1,…,mn}的環(huán)簽名

3) Verify算法

對 于 k ∈ ( 1,… ,n )， 驗(yàn) 證 者 計(jì) 算 hk=H( mk||S|| Uk)，檢驗(yàn)等式

是否成立。如果成立，則簽名δ是有效的，否則為無效的簽名。

4 安全性證明

當(dāng)前在很多論文中都提出了從 Diffie-Hellman問題到簽名方案的規(guī)約[3,8 ～10,12]，這些規(guī)約的方法是很有效的。本節(jié)首先給出正確性推導(dǎo)；環(huán)簽名方案必須保證真正產(chǎn)生簽名的節(jié)點(diǎn)是匿名的，因此本節(jié)隨后給出匿名性分析；最后在假設(shè)計(jì)算 Diffie-Hellman問題難解的前提下，根據(jù)隨機(jī)預(yù)言模型給出安全性證明。

4.1 正確性

在門限環(huán)簽名方案中簽名和驗(yàn)證階段應(yīng)該保持一致性，推導(dǎo)過程如下。

4.2 匿名性

環(huán)簽名方案的特點(diǎn)之一就是匿名性，即外界無法猜測真正發(fā)布簽名的節(jié)點(diǎn)。在有n個節(jié)點(diǎn)的群內(nèi)，外界猜測簽名者的身份，猜對的概率應(yīng)該是1 n。對于(,)t n門限環(huán)簽名方案，外界需要從n個節(jié)點(diǎn)中猜測出t個真正參與簽名的節(jié)點(diǎn)，猜測正確的概率應(yīng)該是

對于i∈{1,…,t},j∈{t+1,…,n}，{ri}∪{rj}是從域中隨機(jī)選取的，因此{(lán)Ui=riP}∪{Uj=rjP}在域G1內(nèi)也是隨機(jī)分布的。由于，因此(U′, U′)在域G1內(nèi)也是隨機(jī)分布的。在隨機(jī)預(yù)言模型中，一般假設(shè)所有的散列函數(shù)的映射都是理論上完全隨機(jī)的。{Ui}∪{Uj}是隨機(jī)預(yù)言機(jī)H的輸入并且在域G1內(nèi)是隨機(jī)分布的，因此隨機(jī)預(yù)言機(jī)H的輸出{hi}∪{hj}在域內(nèi)也是隨機(jī)分布的。

對于t階多項(xiàng)式f( x)=s+a1x+a2x2+…+at-1xt-1，其中，a1,…,at-1∈R是隨機(jī)選擇的，因此每個節(jié)點(diǎn)的私鑰=f( i) Q在域G1內(nèi)是隨機(jī)分布的，并且與{ri}和{hi}是分布獨(dú)立的。因此可以推斷出在域G1內(nèi)是隨機(jī)分布的。

從n個簽名者的群S內(nèi)任意選取t個簽名者，對于某個消息m，簽名都是獨(dú)立且均勻隨機(jī)分布。因此可以推導(dǎo)出敵手或者外界猜測正確生成門限環(huán)簽名的t個簽名者的概率不會超過

4.3 抵御存在性偽造

假定挑戰(zhàn)者C（挑戰(zhàn)CDH問題）接收到CDH問題的一個隨機(jī)實(shí)例(P, aP, bP)，用(P, A, B)表示。挑戰(zhàn)者C在不知道a和b的情況下被要求計(jì)算出abP。挑戰(zhàn)者C與概率多項(xiàng)式時間（PPT，probabilistic polynomial time）的偽造者F玩下面的游戲，在完成該游戲之后，利用偽造者F得到的返回信息去解決CDH問題。在游戲的過程中偽造者F可以向挑戰(zhàn)者C詢問隨機(jī)預(yù)言機(jī)H、密鑰提取和簽名的應(yīng)答。

在一個(t,n)門限方案中，對一個秘密a可以利用拉格朗日系數(shù)很容易地將其分為{a1, a2,…,an}。假設(shè)在一個WSN群S中任意挑選一個子群Si={i1, i2,…,it}?{1,…,n}，對于任意i∈{1,…,n}Si，都可容易地計(jì)算系數(shù) λi1, λi2,…,λit∈使得等式成立?，F(xiàn)在挑戰(zhàn)者C和偽造者F開始進(jìn)行如下的交互。

偽造者F從WSN群S中任意挑選一個有1t-個節(jié)點(diǎn)的子群S′作為攻破的對象。為了不失一般性，假設(shè)子群S′包括編號為{1,2,,1}t-…的節(jié)點(diǎn)。挑戰(zhàn)者C進(jìn)行如下步驟。

1) 隨機(jī)選擇a1, a2,…,at-1∈R。

2) 計(jì)算對應(yīng)的系數(shù)λji，并計(jì)算，此處,,i=t…n。

對于任意一個子群S∈{1,…,n}，并且子群的規(guī)模||St=，等式都是成立的。注意到挑戰(zhàn)者C同樣可以計(jì)算節(jié)點(diǎn)的私鑰=cQ i(i=1,…,t-1)，并將該私鑰發(fā)往偽造者F。顯然，在一個有效的簽名U′中，實(shí)際上是關(guān)于ri和hi的簽名，并且是關(guān)于U′的簽名。因此偽造一個有效的簽名Vi實(shí)際上就是輸出一個有效的簽名。因此可以理解為，如果一個偽造者可以輸出一個有效的簽名，那么可以很容易地偽造簽名。但是偽造者F無法以一個不可忽略的概率（non-negligible probability）偽造一個合法的簽名。

在交互之中，偽造者F將向挑戰(zhàn)者C詢問最多qH次隨機(jī)語言機(jī)H的輸出答案，并詢問最多qS次消息/簽名對，2次詢問都是相對獨(dú)立進(jìn)行的。粗略的講，這些回答都是隨機(jī)生成的，因此為了保證回答的一致性，挑戰(zhàn)者C需要維護(hù)相應(yīng)的列表保存自己的回答，以免碰撞的發(fā)生，避免偽造者F發(fā)現(xiàn)挑戰(zhàn)者C的破綻。

隨后偽造者F可以通過挑戰(zhàn)者C向簽名的預(yù)言機(jī)（signature oracle）發(fā)起詢問。為了使得分析簡單化，本節(jié)先討論如何偽造一個有效的。假設(shè)第i(1≤i≤qS)次詢問的輸入是(mi, ri, Ui)，偽造者F得到相應(yīng)的簽名。最后偽造者F輸出一個新的簽名(m′, Ui)。如果消息m′沒有在前面的詢問中出現(xiàn)，并且等式e(,U+h P)=e( Q,)成立，那ii么可以宣稱偽造者F以不可忽略的概率攻破改進(jìn)的門限環(huán)簽名方案?，F(xiàn)在偽造者F進(jìn)行類似文獻(xiàn)[12]中的流程如下。

假設(shè)一個算法A執(zhí)行自適應(yīng)選擇消息攻擊改進(jìn)的門限環(huán)簽名方案，并以不可忽略的概率攻破本文提出的簽名方案?，F(xiàn)構(gòu)建一個算法B進(jìn)行如下步驟。

1) 選擇一個整數(shù)x∈{1,2,…,qS}。定義Sign( H2(mi, ri, Ui))=。

2) 對于i=1,2,…,qS，算法B回應(yīng)算法A對隨機(jī)預(yù)言機(jī)H和簽名預(yù)言機(jī)的詢問。如果i=x，算法B使用mx代替m。

3) 算法A輸出(m′, Ui, Vi′1)。

注意到x是隨機(jī)選取的，算法A無法從詢問的結(jié)果中得到關(guān)于x的任何信息。同樣，只要H是一個隨機(jī)預(yù)言機(jī)，那么算法A不通過詢問隨機(jī)預(yù)言機(jī)H而生成一個有效輸出的概率是1 2k。設(shè)定=A=aP作為公鑰，并且使得Q=bP，此處挑戰(zhàn)者C不知道a和b的數(shù)值。假設(shè)=(ri+hi)-1←βP，可以做出如下的推導(dǎo)：

從式(12)最后一步的推導(dǎo)可以得出結(jié)論，abP是可以計(jì)算出來的，即解決了計(jì)算Diffie-Hellman問題。實(shí)際上，CDH問題以目前的計(jì)算能力是無法解決的，與已知的事實(shí)是矛盾的。從文獻(xiàn)[13]中，可以得到結(jié)論：敵手偽造一個有效簽名的概率是可以忽略的。也就是偽造者F無法以不可忽略的概率生成一個有效的簽名，進(jìn)而偽造簽名Vi的概率也是可以忽略的，從而改進(jìn)的門限環(huán)簽名可以抵御自適應(yīng)選擇消息攻擊。

5 效率分析

Bresson[8]提出門限環(huán)簽名方案，(t,n)門限環(huán)簽名的長度是[2t(n+t)lbn] lbit，此處l是安全參數(shù)。然而本文提出的改進(jìn)(t,n)門限環(huán)簽名方案的簽名長度是[2]n k bit，此處k是安全參數(shù)。一般來說，雙線性配對采用的是橢圓曲線算法的160bit的密鑰長度，而其他一般采用1 024bit。顯而易見，即使采用的安全參數(shù)都是一樣長度位數(shù)的前提下，本文提出的改進(jìn)門限環(huán)簽名方案的簽名長度依然要短很多。而且在節(jié)點(diǎn)群個數(shù)增長的情況下，尤其是參與簽名的節(jié)點(diǎn)數(shù)增長的情況下，Bresson的簽名長度成指數(shù)增長，而本文提出的門限環(huán)簽名長度只是線性增長。

計(jì)算量較難評估，可以先考慮計(jì)算量最大的操作，如散列函數(shù)計(jì)算次數(shù)、環(huán)簽名等式的驗(yàn)證、雙線性配對計(jì)算，分別用H、C和e表示。Bresson方案在簽名生成階段的計(jì)算量是2tC+(2tlbn) H ，即需要進(jìn)行2t次環(huán)簽名等式驗(yàn)證計(jì)算和2tlbn次散列函數(shù)運(yùn)算；在簽名驗(yàn)證階段計(jì)算量是tC+(2tlbn) H 。本文提出的門限環(huán)簽名方案在簽名生成階段計(jì)算量是nH，在簽名驗(yàn)證階段計(jì)算量是nH+(n+1)e 。

表1 計(jì)算量對比

本文仿真實(shí)驗(yàn)運(yùn)行在Redhat9.0環(huán)境下，以NS2平臺為主，進(jìn)行無線傳感器的網(wǎng)絡(luò)模擬，仿真Bresson所提方案和本文方案的能量消耗。初始網(wǎng)絡(luò)規(guī)模為10個節(jié)點(diǎn)，隨機(jī)部署。后續(xù)節(jié)點(diǎn)個數(shù)依次遞增為20個、50個、80個直到120個。網(wǎng)絡(luò)均采用SMAC協(xié)議和AODV路由協(xié)議，底層數(shù)據(jù)通信的能量消耗暫未計(jì)入，2種方案分別獨(dú)立地仿真20次，分別模擬在不同網(wǎng)絡(luò)規(guī)模下的簽名生成和驗(yàn)證，計(jì)算每個節(jié)點(diǎn)消耗功率的平均值作為最后的結(jié)果。在每次仿真中，每個節(jié)點(diǎn)初始能量1 000J，門限值t=n/10，在不同網(wǎng)絡(luò)規(guī)模下的能量消耗如圖1所示。

圖1 不同節(jié)點(diǎn)規(guī)模的平均能量消耗比較

在圖1的比較中，縱坐標(biāo)采用對數(shù)比例，可以看出在節(jié)點(diǎn)規(guī)模達(dá)到50個的時候，本文方案的簽名生成和Bresson方案基本持平；在節(jié)點(diǎn)規(guī)模達(dá)到80個時，本方案簽名生成只有Bresson方案的1/6，但是簽名驗(yàn)證的能量消耗與Bresson方案持平；節(jié)點(diǎn)規(guī)模達(dá)到 100個的時候，本方案簽名生成只有Bresson方案的1/20，簽名驗(yàn)證只有Bresson方案的1/3；節(jié)點(diǎn)規(guī)模達(dá)到120個的時候，本方案簽名生成只有 Bresson方案的 1/70，簽名驗(yàn)證只有 Bresson方案的1/12。因此Bresson的方案計(jì)算量隨著參與簽名節(jié)點(diǎn)數(shù)量成指數(shù)增長，而本文提出的門限環(huán)簽名方案計(jì)算量與群的規(guī)模成線性增長。因此在群內(nèi)節(jié)點(diǎn)個數(shù)規(guī)模越大的時候本文提出的環(huán)簽名方案計(jì)算量優(yōu)勢越明顯。

此外本文提出的門限環(huán)簽名方案可以進(jìn)行并行計(jì)算，即參與簽名的節(jié)點(diǎn)可以并行地生成部分簽名，然后再將部分簽名共同生成門限環(huán)簽名，本文稱為并行生成算法。但是絕大部分的門限環(huán)簽名方案，包括 Bresson的方案，需要參與簽名的節(jié)點(diǎn)一個接著一個生成部分簽名，這樣才可以組成一個環(huán)，本文稱為串行生成算法。串行生成算法產(chǎn)生一個環(huán)簽名需要的時間非常長，增加了能量的消耗；并且如果某個節(jié)點(diǎn)失效，需要重新定義群內(nèi)參與簽名的節(jié)點(diǎn)次序，浪費(fèi)較多的資源。因此本文提出的門限環(huán)簽名方案非常適合無線傳感器等自組織網(wǎng)絡(luò)。

6 結(jié)束語

基于雙線性配對，本文提出一個適用于無線傳感器網(wǎng)絡(luò)的門限簽名方案，并在假設(shè)計(jì)算Diffie-Hellman問題困難的前提下，利用規(guī)約到矛盾的方法給出在隨機(jī)預(yù)言機(jī)模型下的安全性證明。與傳統(tǒng)的網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)規(guī)模較大，網(wǎng)絡(luò)節(jié)點(diǎn)隨時可能失效，同時新舊節(jié)點(diǎn)的加入非常頻繁，而且無線傳感器網(wǎng)絡(luò)在存儲空間、移動性、計(jì)算能力和能量等方面限制，因此在需要采用認(rèn)證、簽名等安全技術(shù)時，本文所提的門限方案更加適合無線傳感器網(wǎng)絡(luò)。此外，本文所提方案還具有以下特點(diǎn)：第一，滿足群合作的條件下應(yīng)該具備的頑健性，可以在合作生成簽名的過程中檢測所有節(jié)點(diǎn)是否運(yùn)行錯誤的行為和步驟，同時可以防御一些惡意的節(jié)點(diǎn)對整個群造成的影響；第二，多簽，即群內(nèi)的所有節(jié)點(diǎn)可以自由選擇自己需要發(fā)布的消息，在簽名中可以一次性對所有的消息進(jìn)行簽名；第三，滿足分布式并行計(jì)算要求，所有參與簽名節(jié)點(diǎn)可以并行地計(jì)算自己的部分簽名，然后將部分簽名組合成為門限簽名。

[1] RIVEST R, SHAMIR A, TAUMAN Y. How to leak a secret[A]. Proc ASIACRYPT’2001[C]. Berlin, Heidelberg, New York: Springer- Verlag, 2001. 552-565.

[2] GIOVANNI D C, GONZALO A, RENWEI G. Threshold cryptography in mobile ad hoc networks[A]. SCN 2004[C]. Berlin, Heidelberg,New York: Springer-Verlag, 2005. 91-104.

[3] STEFAAN S, BART P. Efficient cooperative signatures: a novel authentication scheme for sensor networks[A]. SPC 2005[C]. Berlin Heidelberg, New York: Springer-Verlag, 2005. 86-100.

[4] LIU J K, WEI V K, WONG D S. Linkable spontaneous anonymous group signature for ad hoc groups[A]. ACISP 2004[C]. Berlin, Heidelberg, New York: Springer- Verlag, 2004. 325-335.

[5] QI Z H, Y G, CHEN W, et al, One threshold and identity based encryption-signature scheme for WSN[J]. Journal of Nanjing University of Posts and Telecommunication(Natural Science), 2009, 29(5): 14-20.

[6] TONY K C, FUNG K, LIU J K, et al. Blind spontaneous anonymous group signatures for ad hoc groups[A]. ESAS 2004[C]. Springer-Verlag, Berlin Heidelberg New York, 2005. 82-94.

[7] JAVIER H, GERMAN S. Ring signature schemes for general Ad-Hoc access structures[A]. ESAS 2004[C]. Berlin, Heidelberg, New York:Springer-Verlag, 2005. 54-65.

[8] BRESSON E, STERN J, SZYDLO M. Threshold ring signatures and applications to ad-hoc groups[A]. Proc CRYPTO 2002[C]. Berlin,Heidelberg, New York: Springer- Verlag, 2002. 465-480.

[9] BENOIT L, QUISQUATER J J. Efficient revocation and threshold pairing based cryptosystems[A]. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (PODC 2003)[C].New York, 2003. 163-171.

[10] SHERMAN C, LUCAS C K, YIU S M. Identity Based Threshold Ring Signature[A]. ICISC 2004[C]. Berlin, Heidelberg, New York:Springer-Verlag, 2005. 218-232.

[11] YAO M, MATT H, GREG M, et al. A mobile agent system providing offer privacy[A]. ACISP2004[C]. Berlin, Heidelberg, New York:Springer-Verlag, 2004. 301-312.

[12] LIAO J, XIAO J f, QI Y H, et al. ID-based signature scheme without trusted PKG[A]. CISC 2005[C]. Berlin, Heidelberg, New York:Springer-Verlag, 2005. 53-62.

[13] BONEH D, LYNN B, SHACHAM H. Short signatures from the weil pairings[A]. Cryptology-Asiacrypt 2001[C]. Springer- Verlag, Berlin Heidelberg New York, 2001. 514-532.