有效的动态k 次匿名认证协议

刘蓬涛

（山东政法学院信息科学与技术系，山东济南250014）

0 引言

k 次匿名认证协议（k-TAA）[1]包括群管理员GM、应用提供者AP和用户. GM 将用户注册到群组中，每一个AP 可以决定自己应用的访问次数.一个群组中的成员可以在限定次数内单独被AP 匿名认证.任何人都无法知道用户身份， 无法将同一用户的两次认证过程联系起来，但所有人都可以追踪不诚实的用户.在k 次匿名认证协议中，应用提供者只能决定为群组中一个用户提供应用服务的次数而无法决定向谁提供应用服务.为解决这一问题，引入了动态k 次匿名认证协议[2].目前提出的一些k-TAA 方案[1-2]的认证过程的计算量和通信量线性依赖于k.文献[3]提出了一个有效的动态k-TAA 方案，其认证过程的计算量和通信量不依赖于k.

本文提出一个有效的动态k-TAA 方案， 其认证代价不依赖于k.我们证明方案是安全的，并与[3]中的方案进行比较.

1 符号约定

令G1，G2，GT分别为阶为素数p 的乘法循环群.g1，g2分别是G1，G2的生成元.令e：G1x G2→GT为双线性映射[4].我们令G1＝G2＝G，g1＝g2＝g.

2 有效的动态k 次匿名认证方案

GKg：设（p，G，GT，e，g）为系统参数，e（G，G）→GT，选u0，u1，u2，u3←G，φ←GT，γ∈Zp*，并计算Ppub＝gγ.群公钥gpk＝（g，Ppub），群密钥gsk＝γ.认证列表LIST 置为空.H 和H′为Hash 函数.

AKg：AP υ 选择g1∈G，s，s’∈Zp*， 计算Qpub＝g1s，Qpub’＝g1s’. υ 的公钥apkυ＝（g1，Qpub，Qpub’），私钥apkυ＝（s，s’）. υ 管理认证记录LOGυ以及累加值V.在Grant 和Revoke 后，累加值V 要被更新.公开三元组记录ARC中第一个元素是可以访问υ 的用户公钥，第二个元素表示该用户是被Grant 还是被Revoke，第三个元素是Grant 和Revoke 之后的累加值V.初始时V＝V0∈G，LOGυ和ARC 为空.

JoinU，JoinM：用户Ui可以执行如下协议加入授权群组中.

1）Ui选择x’∈Zp*，计算β＝φ1/x’和C＝gx’，并将（i，β）加入LIST.发送β 和C 给群管理员GM.

2）GM 检查（i， β）是LIST 的元素，并验证e（β，C）＝e（φ，g）.如果验证通过，GM 选择一个不同的a∈Zp，∈Zp*，并计算S＝（Cgu0）1/（γ+a），发送（S，a，）给用户.

3）用户Ui计算x＝x’＝，验证e（S，gaPpub）＝e（gxu0，g），如验证通过，则Ui的密钥mski＝x，公钥mpki＝（a，S，β）.

Bound：υ 的公开身份为ID， 其应用服务的允许访问次数上限为k，对j＝i，…k 计算tj＝H（ID，k，j），Rj＝g11/（s’+tj）.公开（t1，R1）…（tk，Rk）.

Grant：设υ（ID，k）的当前ARC 中有j 个三元组， υ 的当前累加值为Vj. 设υ 要赋予用户Ui访问其应用的权限， 用户Ui的公钥为mpki＝（a，S，β）.AP υ 计算新的累加值Vj+1＝Vjs+a，并将（a，1，Vj+1）加入ARC.用户可以得到其访问密钥mak＝（j，Wj＝Vj）.同时，用户还保有一个初始化为0 的计数器d.

Revoke：设υ 当前ARC 中有j 个三元组， υ 的当前累加值为Vj.设υ 要撤销用户Ui访问其应用的权限，用户Ui的公钥为mpki＝（a，S，β）.υ计算新的累加值Vj+1＝Vj1/（s+a），并将（a，0，Vj+1）加入ARC.

AuthenU， AuthenP：设应用提供者υ（ID，k）的公钥为apkυ＝（g1，Qpub，Qpub’）， 当前累加值为V， 与之认证的用户U 的公钥和私钥分别为mpk＝（a，S，β）和msk＝x.认证过程如下：

1）用户U 设置d＝d+1.如果d＞k，则U 发送⊥给υ 并结束认证过程.否则U 执行如下算法得到其新的访问密钥mak＝（j，W＝Wj）. υ 发送随机数l∈RZp*给U.

该算法与[2]中的算法相同.设υ 的ARC 当前有n 个元素， 用户U使用其公开的公钥mpk＝（a，S，β）和mak＝（j，Wj）计算其新的访问密钥mak：

对k＝j+1，…，n，从ARC 中获取第k 个元素（u，b，Vk），如果b＝1，则计算Wk＝Vk-1Wk-1u-a，否则，计算Wk＝（Wk-1/Vk）1/（u-a）.

2）U 利用没有用到的（tl，Rl），计算Γ＝φ（lx+ltl+x）/（x2+xtl），＝φ1/（x+xtl），计算Γ的知识证明ProofΓ：

（1）用户U 随机选取r1，…，r6，k1，…，k16∈Zp，并计算U1＝Su3r1；U2＝Wu3r2；U3＝Rlu3r3；U4＝u1r1u2r2u3r4；U5＝u1r3u3r5；U6＝u1x+tlu3r6；T1＝u1k1u2k2u3k4；T2＝u1k7u2k8u3k9u4-k10；T3＝u1k3u3k5；T4＝u1k11u3k12u5-k13；T5＝u1k13+k14u3k6；T6＝u1k15u3k16u6-k14；r1＝Γk15φ-lk13-（l+1）k14；

r2＝e（U1，g）k10e（U3，g）-k7e（U3，Ppub）-k1e（g，g）-k14；

（2）计算c＝H’（ID||k||l||V||U1||…||U6||T2||…T6||R1||…||R4||R5），并计算

si＝ki+cri（1≦i≦6）；s7＝k7+cr1a；s8＝k8+cr2a；s9＝k9+cr4a；s10＝k10+ca；s11＝k11+cr3tl；s12＝k12+cr5tl；s13＝k13+ctl；s14＝k14+cx；s15＝k15+c（x+tl）x；s16＝k16+cr6x.

（3）ProofΓ＝（U1，…，U6，c，s1，…，s16），发送Γ 和ProofΓ给υ.

3 安全性分析及比较

方案的正确性很容易证明.使用其构造的敌手模型，我们可以证明在DBDHI 假设下方案具有匿名性.在SDH 假设下，Boneh-Boyen 签名方案保证了我们的方案具有可跟踪性和GM 的可开脱性.在CBDHI2 假设下方案具有用户的可开脱性。

忽略方案中一些预计算的部分，我们从认证协议中幂运算，标量乘运算，双线性运算以及传输数据量方面比较Nguyen[3]的方案和我们的方案.令p 为一个160 比特的大素数.

Nguyen 方案我们的方案

AP 的计算量21EXs+20SMs+6PAs18EXs+17SMs+6PAs

用户的计算量22EXs+27SMs20EXs+25SMs

AP 传输的数据字节数 2020

用户传输的数据字节数585545

4 结束语

本文提出一个有效的动态k 次匿名认证方案，其认证过程的耗费与k 无关.我们证明其正确性与安全性，并与Nguyen 提出的方案进行比较.方案比Nguyen 的方案需要更少的计算量和传输数据量，是有效的动态k 次匿名认证方案.

［1］I. Teranisi， J. Furukawa， and K. Sako. k-Times Anonymous Authentication[M].ASIACRYPT 2004， Springer-Verlag， LNCS 3329， pp. 308-322， 2004.

［2］L. Nguyen and R. Safavi-Naini. Dynamic k-Times Anonymous Authentication.Applied Cryptography and Network Security（ACNS）2005[M].Springer-Verlag,LNCS 3531，2005.

［3］L. Nguyen. Efficient Dynamic k-Times Anonymous Authentication[Z].2007.

［4］Dan Boneh， Ben Lynn， and Hovav Shacham. Short signatures from the Weil pairing[J]. Journal of Cryptology，17（4）：297－319， 2004. Extended abstract in Proceedings of Asiacrypt 2001， LNCS volume 2248.