(1. 南京理工大学 计算机科学与技术学院，江苏 南京 210094；2.南京炮兵学院 计算机教研室，江苏 南京 211132)

1 引言

Ad hoc网络由于具有不需要基础设施、自组织、自管理等特点，使其在军事战场、抢险救灾等环境中得到越来越多的应用。但由于ad hoc网络自身的特性，如使用无线信道作为传输介质，使其安全性面临很大的威胁，其中节点身份的匿名性（私密性），得到越来越多的关注，如ANODR[1]、A3RP[2]等协议。在ad hoc网络环境下，通信中节点身份的匿名性研究比较多，如ANODR[1]等匿名路由协议，而在认证中节点身份的匿名性研究较少；且由于ad hoc网络的自组织性、无中心性，使传统网络中的基于可信中心的匿名认证方案不再适合，所以提出新的适合ad hoc网络的匿名认证方案非常有必要。

Jung等[2]提出的A3RP协议，以及田子健等[3]提出的动态可追踪的匿名认证方案，虽能提供匿名认证，但它们都需要一个可信中心TA参与匿名认证，导致权利过于集中以及单点失效等问题，这与ad hoc网络的无中心性相违背；Zhimin等[4]将可信计算及One-Way Accumulator引入匿名认证中，降低了协议计算量，且不需要可信第三方参与，但示证者（被认证者）身份无法追踪；为了解决ad hoc网络中节点匿名认证及示证者追踪问题而又不引入可信第三方，本文提出一种无可信中心的门限追踪ad hoc网络匿名认证方案。方案提供对任意节点合法性的认证，而不暴露示证者身份；通过门限机制实现任意k个合法节点可联合追踪示证者身份，而不需要管理员等可信第三方参与，亦不会导致任意合法节点都可追踪示证者身份的过于自由、随意性等问题；方案的整个执行过程，不需要可信第三方参与，完全符合ad hoc网络的无中心、自组织、自管理等特性。

2 无可信中心的门限追踪匿名认证模型及安全要求

定义 1 认证方案的匿名性：示证者不暴露自己的身份而能向验证者证明自己身份的合法性。

定义 2 认证方案的可追踪性：在需要的情况下，能够根据陷门信息及验证者提供的信息，恢复出示证者的身份。

定义3 无可信中心性：从方案的初始化开始，整个方案不涉及可信中心。

匿名认证阶段，任意节点Pu向任意节点Vu（Vu可以不属于U）证明它属于组织U，但不透露Pu的身份。若想知道已通过匿名认证的节点Pu的身份，则必须经U中至少k个节点同意，方可恢复出Pu的身份，实现Pu身份的追踪。

整个模型包括如下过程。

1) 初始化：群组织中各成员生成自己的签名公私钥对，并相互协作建立群公钥及群共享秘密（匿名认证中的追踪陷门信息）。

2) 匿名认证过程：示证者利用自己的签名私钥及群公钥生成一个签名，验证者对示证者的签名进行验证，整个过程不暴露示证者的身份信息。

3) 追踪算法：k个成员联合利用追踪陷门等信息恢复出示证者身份。

4) 新成员加入算法：新成员与群组织中各成员相互协商，以更新群公钥、群追踪陷门等信息。

5) 成员撤销算法：节点离开后，剩余节点相互协商以更新群公钥、群追踪陷门等信息。

一个无可信中心的陷门追踪ad hoc网络匿名认证方案是安全的，若满足以下条件。

1) 正确性：群组织中任意一个成员执行匿名认证中的签名算法后，输出的签名都能通过匿名认证中的签名验证算法。

3) 可追踪性：群组织中任意k个合法成员，可联合恢复出已通过认证的示证者身份。

4) 完备性：任何不属于组织 U的节点，皆不能通过匿名认证。

5) 追踪的(k, n)门限性：必须至少k个合法成员联合，方可追踪示证者身份。

6) 无可信中心性：从系统建立至匿名认证及身份追踪，皆不需要可信第三方的参与。

3 相关技术介绍

3.1 假设

离散对数假设：设G为g生成的一个阶为q的循环群。不存在概率多项式时间算法A，其能以不可忽略的概率从ag计算出a。

确定的Diffie-Hellman(DDH）假设：设G为g生成的一个阶为q的循环群。不存在概率多项式时间算法A，其能以不可忽略的概率区分出分布D和R，

3.2 民主签名

使用群签名实现匿名认证是最直接的方法。群签名概念最初由Chaum和Heyst提出[7]，目前较好的群签名方案由 Ateniese[8]等提出。群签名实现匿名认证，群管理员可以实现示证者身份的追踪。由于群管理员的特殊身份，将会导致权利过于集中、权利滥用以及单点失效等问题，所以必须对群管理员加以约束。

民主签名[9]由Manulis于2006年提出，其中任意成员可代表群进行签名，群内任意成员可从给定的有效群签名中恢复出签名者的身份。若使用民主签名实现匿名认证方案，则群中任意成员可恢复出示证者的身份，追踪示证者。这种追踪能力过于自由必将导致不受控制的滥用，所以必须对群成员的这种追踪能力加以控制。

将群签名中管理员权利过于集中与民主签名中成员追踪能力过于自由进行折衷，提出具有门限追踪能力的匿名认证方案，使得至少k个群成员同意恢复示证者身份时，方能追踪到示证者身份。

3.3 秘密共享

(k, n)门限秘密共享是指将一个秘密s分成n个份额s1, s2,…,sn，并将这些秘密份额秘密地分发给n个用户，使得发生如下情况。

1) 由k个或多于k个用户拥有的秘密份额 si可以恢复出秘密s。

2) 由少于 k个用户持有的秘密份额 si不能获得关于秘密 s的任何信息。这里 k称为门限，且1≤k≤n。

Shamir[10]于 1979年提出的基于多项式拉格朗日插值的(k, n)门限方案。该方案有如下2个缺点：1)不能检测可信中心分发假的份额给用户；2)该方案需要一个可信的中心。随后Feldman提出了可验证秘密共享方案，Pedersen[11]提出了无可信中心的秘密共享方案。由于ad hoc网络的无中心性、自组织性等特点，本文选用Pedersen的无可信中心的秘密共享方案，并将其应用于匿名认证方案中，从而实现本方案的门限追踪能力。

4 匿名认证协议

借助群签名、民主签名以及无可信中心的秘密共享思想，实现了无可信中心的门限追踪ad hoc网络匿名认证方案。本方案主要包括系统初始化、匿名认证、示证者追踪、新成员加入以及成员吊销等过程。

4.1 系统初始化

系统初始化的目的是建立各节点签名公私钥对、群共享秘密S（匿名认证中的追踪陷门）、群公钥 PU。

1) 选取素数q，G为q阶循环群，其上离散对数问题是困难的，g为生成元；k是门限值，n是用户数；散列函数为安全参数。

2) 节点 ui选取 Si∈Zq作为自己的签名私钥，计算对应的签名公钥为 Pi= gSi。

3) ui在 Zq上选择 k-1次多项式

4) ui计算 yij=fi(j) mod q , 1 ≤ j ≤ n ,并将 yij秘密发送给节点 uj,节点 ui保留 yii。

5) 节点 ui收到其他所有节点的 yji，并计算yi即是节点 ui的秘密份额。

6) 群共享秘密S的计算方法。

任意k个节点可利用自己的秘密份额通过拉格朗日插值法计算出群共享秘密S，群秘密S即为匿名认证中的追踪陷门。

7) 群公钥计算方法。

初始化结束后，每个节点拥有自己的公私钥对(Si, Pi)、自己的秘密份额 yi以及群公钥 PU。

4.2 匿名认证过程

节点 uP想向节点 uV证明自己属于组织 U，则uP使用自己的签名私钥及群公钥生成一群签名，并把此签名交给 uV验证，若验证通过则说明 uP属于组织U，否则 uP不属于组织U。匿名认证过程主要包括签名生成算法和签名验证算法。

1) 示证者 uP签名的生成算法

参照民主签名[9]，给出如下签名算法，算法的输入为 uP的私钥 Sp、群公钥 PU，待签名消息为m∈ { 0,1}*， uP执行如下计算。

2) 签名验证算法

uV接收到sign(m )后，利用群公钥 PU以及消息m，验证如下等式是否成立：

如果成立，则签名认证通过，说明Pu是U中合法节点；否则认证不通过。在此身份认证过程中，验证者只能确定示证者是群中的某个成员，而不能确定是哪一个成员，即实现了示证者身份的匿名性。

4.3 示证者身份追踪算法

为了在必要情况下实现示证者身份的追踪，组织 U中的任意 k个成员 { u1′, u2′,… ,uk′} ⊂ U ={u1,u2,… ,un}，可联合利用群追踪陷门恢复出示证者的身份，具体步骤如下。

1) k个节点使用自己的秘密份额 y1′, y2′,… ,yk′， x0以及对应的 c1′, c2′,… , ck′联合计算出 T =x0S

3) 输出示证者的签名公钥，即可得到示证者身份。

4.4 节点加入算法

新节点的加入，将导致群公钥、追踪陷门以及各节点秘密份额的更新。假设节点 ux想加入到组织 U中，且组织U中目前节点数为n，则执行如下步骤。

1) 节点 ux选取 Sx∈Zq作为自己的签名私钥，计算对应的签名公钥为 Px= gSx； ux在 Zq上选择k-1次多项式 fx(x) = ax0+ax1x + …+ax,k-1xk-1，并计算 yxj=fx( j) mod q , 1 ≤ j ≤ n +1,并将 yxj秘密 发送给节点 uj,节点 ux保留 yxx。

2) 组织U中原有节点 ui计算 yix=fi( x) mod q,1,in≤≤并将ixy秘密发送给节点xu。

3) 节点xu收到其他所有节点的ixy，并计算即是节点xu的秘密份额。

5) k个节点联合利用拉格朗日插值算法，计算新的追踪陷门，进而得到新的群公钥。

4.5 节点吊销算法

由于节点的移动性等原因，致使节点离开组织U，将导致群公钥、追踪陷门以及各节点秘密份额的更新。假设节点 uj离开组织 U，且 uj离开前 U中的节点数为n，则执行如下步骤。

1) 组织 U中各节点计算新的秘密份额，且新的秘密份额为 yi′ =yi-yji，i≠j，且1≤i≤n。

2) k个节点通过拉格朗日插值算法，计算新的追踪陷门，以及新的群公钥。

5 协议分析

5.1 协议性质分析

定理1 匿名性：本方案在确定的Diffie-Hellman(DDH)假设的前提下，可保证示证者的匿名性。

以下论证皆在DDH假设的前提下进行。r的随机性，可保证0y与示证者公钥PP的无关联性。由1ir、的随机性，决定了 xi、 yi及 zi的随机性。由于 cP由 xi， yi及 zi决定，因此不能从 S1P、 S2P中推导出示证者的公私钥，亦找不出 S1P、 S2P与示证者身份的关联性，所以无法从消息m的签名中判断出签名者的身份。匿名性的形式化数学证明可参照文献[9]。

定理2 可追踪性：任意k个合法群组织成员，可联合恢复出通过认证的示证者身份。

其中，PP即为示证者的公钥，根据公钥即可找到示证者身份。

定理 3 正确性：群组织中任意一合法成员，可通过匿名认证。

生成算法及签名验证算法中的 uP为随机选取的，故对群中任意成员 uX及其对消息 m的签名sign(m)，都存在一多项式时间算法Verify，使得Verify( SX,PU, m. s ign(m )) = 1（1表示签名有效，通过匿名认证；0表示无效）。

定理4 完备性（不可冒充性）：非群组织成员，不能通过匿名认证。

由于匿名认证中签名算法的第6步需要签名者私钥的参与，而非组织成员没有合法的私钥，从而导致生成的签名不能通过验证者的验证。

定理 5 无中心性：本方案不需要可信第三方参与。

本方案各阶段皆不需要可信第三方参与。系统初始化阶段，各节点生成自己的签名公私钥，并使用无可信中心的秘密分享方案协商生成群追踪陷门及群公钥；匿名认证阶段，示证者选择相应随机数并生成签名，而验证阶段只需验证者参与；新节点加入及节点吊销阶段，只需群内各节点相互协作更新群追踪陷门及群公钥即可，所以方案这个过程没有可信第三方的参与。

定理6 追踪的（k, n）门限性：若要追踪示证者身份，则必须至少k个合法节点同意参与方可。

若想恢复示证者身份，则必须得到群陷门信息。群陷门信息则由k个节点的秘密份额通过拉格朗日插值法方能得出。若少于k个节点，则不能恢复出群陷门信息，亦不能恢复出示证者的身份。示证者身份追踪的(k, n)门限性，既避免了群签名中的管理员权利过大而导致的各种问题，又避免了民主签名中各节点追踪能力过于自由而导致不受控制的滥用等问题。

定理 7 签名的无关联性：本方案中示证者 2次提供的签名具有无关联性，可抵抗对签名的一致性攻击。

5.2 节点移动性分析

第4.4节及第4.5节的节点加入、吊销算法，很好地满足了ad hoc网络节点的移动性。节点加入（或者离开）群组织，将激活节点加入算法（节点吊销算法）更新群公钥、追踪陷门以及各节点秘密份额，从而保证后续的匿名认证及追踪的成功性。特别地，

1) 节点的大量离开，导致 n＜k，此时已打破Pedersen的秘密共享方案，故需从新选取k；

2) 节点的大量加入，导致k远小于n，安全性下降，由于节点的大量加入，恶意节点个数超过 k的可能性增加，而k个节点联合可恢复出示证者的身份，故需从新选取k，k的选取方式可参照Pedersen的秘密共享方案。

5.3 协议比较

与现有匿名认证协议相比较，本协议同时具有示证者身份的匿名性、无中心性、门限可追踪性，结果如表1所示。

表1 协议性质比较

5.4 匿名认证阶段计算量分析

签名算法中，计算量主要是计算ix、iy和iz的指数运算，复杂度与普通的公钥运算相同，且随着群组织中成员数的增加，计算量成线性增加。分析可知，验证阶段的计算量与签名过程相同。

5.5 建立可检测秘密共享方案

系统建立阶段，若群组织内有恶意节点，发送虚假秘密ijy以破坏秘密共享机制的建立，可通过建立可检测秘密共享方案抵制恶意节点，具体实现方案可在4.1节系统建立阶段，加入以下2步。

1)ui计算并广播

2)uj验证从iu处收到的秘密ijy：

若等式成立，则秘密ijy有效，否则ijy无效。若ijy无效，则ju可广播一个对iu的抱怨。

等式正确性分析：

6 结束语

由于ad hoc网络的无中心性、自组织性，使传统网络中的匿名认证方案不再适合。本文提出一种适合ad hoc网络的匿名认证方案，本方案将民主签名与无中心的秘密分享方案应用到匿名认证中，实现了在不需要可信中心的参与下，示证者身份的匿名性、可追踪性及不可冒充性，并给出了相应的匿名认证算法、追踪算法、节点加入算法及节点吊销算法。

[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] 田子健, 王继林, 伍云霞. 一个动态可追踪匿名认证方案[J]. 电子与信息学报, 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.