應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)的門(mén)限環(huán)簽名方案

肖俊芳，廖劍，曾貴華

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

1) 偽造者F從節(jié)點(diǎn)群N中任意選取t-1個(gè)目標(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ù)和簽名詢問(wèn)。F可以根據(jù)C返回的結(jié)果動(dòng)態(tài)地調(diào)整詢問(wèn)值。

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

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

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

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

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

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

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生成一個(gè)t階多項(xiàng)式：

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

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

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

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

3.1.2 Sign算法

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

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

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

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

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

3.1.3 Verify算法

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

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

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

3.2 頑健性分析

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

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

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

在 Setup算法階段的步驟 8）中，實(shí)際上已經(jīng)在進(jìn)行頑健性檢查，每個(gè)節(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群中不同的簽名者對(duì)多個(gè)不同的消息同時(shí)進(jìn)行簽名。在網(wǎng)絡(luò)規(guī)模較大的密碼學(xué)應(yīng)用環(huán)境中，如果WSN群內(nèi)有簽名者想發(fā)布一個(gè)特別的信息，但是不想暴露到底是哪一個(gè)簽名者發(fā)布的，最有效的方式就是生成一個(gè)包含不同消息的群簽名。

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

1) Setup算法

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

2) Sign算法

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

3) Verify算法

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

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

4 安全性證明

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

4.1 正確性

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

4.2 匿名性

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

對(duì)于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ī)分布的。

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

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

4.3 抵御存在性偽造

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

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

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

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

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

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

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

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

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

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

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

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

注意到x是隨機(jī)選取的，算法A無(wú)法從詢問(wèn)的結(jié)果中得到關(guān)于x的任何信息。同樣，只要H是一個(gè)隨機(jī)預(yù)言機(jī)，那么算法A不通過(guò)詢問(wèn)隨機(jī)預(yù)言機(jī)H而生成一個(gè)有效輸出的概率是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ì)算出來(lái)的，即解決了計(jì)算Diffie-Hellman問(wèn)題。實(shí)際上，CDH問(wèn)題以目前的計(jì)算能力是無(wú)法解決的，與已知的事實(shí)是矛盾的。從文獻(xiàn)[13]中，可以得到結(jié)論：敵手偽造一個(gè)有效簽名的概率是可以忽略的。也就是偽造者F無(wú)法以不可忽略的概率生成一個(gè)有效的簽名，進(jìn)而偽造簽名Vi的概率也是可以忽略的，從而改進(jìn)的門(mén)限環(huán)簽名可以抵御自適應(yīng)選擇消息攻擊。

5 效率分析

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

計(jì)算量較難評(píng)估，可以先考慮計(jì)算量最大的操作，如散列函數(shù)計(jì)算次數(shù)、環(huán)簽名等式的驗(yàn)證、雙線性配對(duì)計(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 。本文提出的門(mén)限環(huán)簽名方案在簽名生成階段計(jì)算量是nH，在簽名驗(yàn)證階段計(jì)算量是nH+(n+1)e 。

表1 計(jì)算量對(duì)比

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

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

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

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

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

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

[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.