肖俊芳，廖剑，曾贵华

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