應用于無線傳感器網絡的門限環簽名方案

肖俊芳，廖劍，曾貴華

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

1 引言

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

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

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

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

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

2) 多簽：群內的所有節點可以自由選擇自己需要發布的消息，在簽名中可以一次性對所有的消息進行簽名。多簽現在被廣泛應用于移動代理、招投標、電子投票、數字彩票、電子現金等方面。

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

2 門限環簽名的語法及安全模型

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

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

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

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

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

1) 偽造者F從節點群N中任意選取t-1個目標節點，這些節點可以與F一起參與偽造。F可以從挑戰者C處得到部分私鑰。

2) 在安全參數k的作用下，C運行Setup算法，然后將系統參與發送給F。

3) F進行多項式邊界次散列函數和簽名詢問。F可以根據C返回的結果動態地調整詢問值。

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

F輸出一個關于消息m的門限環簽名，在有n個節點的群內至少需要t個節點參與簽名。在游戲中有2個要求：①消息m在之前的簽名和隨機預言機詢問中沒有被涉及到；②少于t個節點的密鑰被F獲取。當偽造的簽名可以通過簽名驗證算法，那么F贏得這個游戲。

3 改進的門限環簽名方案

針對無線傳感器網絡的特點，本節提出改進的門限環簽名方案，在簽名的構建部分包括準備、簽名和驗證3個步驟。隨后對改進的門限環簽名方案進行頑健性分析，給出參與簽名的節點在簽名過程中如何檢測錯誤的發生。最后基于改進的門限環簽名方案，本節提出實現多方數字簽名的方法。

3.1 改進的門限環簽名算法

假設在一個無線傳感器網絡群內有n個節點，用符號S表示，同時在WSN群內架構一個公鑰生成器（PKG），該PKG可以離線預先生成各節點的公私鑰對。

3.1.1 Setup算法

1) 選定系統安全參數k，輸出q階加法群G1和q階乘法群G2，雙線性映射e: G1×G1→G2，此處q是kbit的素數。

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

3) PKG生成一個t階多項式：

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

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

7) PKG將s作為系統私鑰，輸出系統參數params:

8) 在每個節點得到相應的私鑰之前，WSN群內每個節點Sk∈{1,…,n}都可以檢查

3.1.2 Sign算法

為了不失一般性，假設WSN群中編號為{1,…,t}的節點參與環簽名的生成，編號為{t+1,…,n}的節點不參與環簽名的生成。

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

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

此處S表示WSN群中參與簽名的n個節點的身份；隨后將(Uj, Vj)公布；最后計算并公布。

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

3.1.3 Verify算法

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

2) 驗證者檢驗等式

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

3.2 頑健性分析

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

1) 避免到最后生成簽名時才發現生成的簽名是無效的。

2) 在簽名的生成過程中，每個參與簽名的節點應該可以檢驗自身的錯誤。

在 Setup算法階段的步驟 8）中，實際上已經在進行頑健性檢查，每個節點需要計算公鑰是否是有效，進一步判斷參與簽名的群體S是否合法。

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

是否成立。如果成立則該節點生成的部分簽名是正確的，否則該節點重新進行計算。

3.3 多簽方案

與其他的群簽名方案相比較，本節提出的環簽名方案可以使WSN群中不同的簽名者對多個不同的消息同時進行簽名。在網絡規模較大的密碼學應用環境中，如果WSN群內有簽名者想發布一個特別的信息，但是不想暴露到底是哪一個簽名者發布的，最有效的方式就是生成一個包含不同消息的群簽名。

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

1) Setup算法

與改進門限環簽名算法一樣。

2) Sign算法

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

3) Verify算法

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

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

4 安全性證明

當前在很多論文中都提出了從 Diffie-Hellman問題到簽名方案的規約[3,8 ～10,12]，這些規約的方法是很有效的。本節首先給出正確性推導；環簽名方案必須保證真正產生簽名的節點是匿名的，因此本節隨后給出匿名性分析；最后在假設計算 Diffie-Hellman問題難解的前提下，根據隨機預言模型給出安全性證明。

4.1 正確性

在門限環簽名方案中簽名和驗證階段應該保持一致性，推導過程如下。

4.2 匿名性

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

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

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

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

4.3 抵御存在性偽造

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

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

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

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

2) 計算對應的系數λji，并計算，此處,,i=t…n。

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

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

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

假設一個算法A執行自適應選擇消息攻擊改進的門限環簽名方案，并以不可忽略的概率攻破本文提出的簽名方案。現構建一個算法B進行如下步驟。

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

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

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

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

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

5 效率分析

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

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

表1 計算量對比

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

圖1 不同節點規模的平均能量消耗比較

在圖1的比較中，縱坐標采用對數比例，可以看出在節點規模達到50個的時候，本文方案的簽名生成和Bresson方案基本持平；在節點規模達到80個時，本方案簽名生成只有Bresson方案的1/6，但是簽名驗證的能量消耗與Bresson方案持平；節點規模達到 100個的時候，本方案簽名生成只有Bresson方案的1/20，簽名驗證只有Bresson方案的1/3；節點規模達到120個的時候，本方案簽名生成只有 Bresson方案的 1/70，簽名驗證只有 Bresson方案的1/12。因此Bresson的方案計算量隨著參與簽名節點數量成指數增長，而本文提出的門限環簽名方案計算量與群的規模成線性增長。因此在群內節點個數規模越大的時候本文提出的環簽名方案計算量優勢越明顯。

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

6 結束語

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

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