0 引言

随着“互联网+”逐渐融入我们的生活，我们在网络上留下的痕迹越来越多，在如今的大数据时代下，这些痕迹可能威胁到我们的隐私安全，匿名认证技术是提高隐私安全的一项重要手段.匿名认证允许对用户进行身份认证，同时还保证用户身份的匿名性.但是，匿名性特征可能会被恶意用户利用，在实施犯罪活动时逃避追踪.于是，很多学者开始研究可追踪的匿名认证方案.

基于环签名^[1]，田子建等^[2]实现匿名认证时，在管理员和验证者的合作下，可追踪到示证者的隐私身份.但该方案的匿名追踪不是门限追踪，追踪的门槛较低，隐私身份受到威胁.基于民主签名^[3]，刘方斌等^[4]实现的门限可追踪匿名认证方案，可应用到ad hoc网络.基于可追踪签名^[5]，Shin等^[6]实现的匿名认证和授权方案，可以支持细粒度的授权服务.基于1/n签名^[7]，殷凤梅等^[8]实现的门限追踪匿名认证方案，允许成员自主选择子密钥.但以上3个可追踪匿名认证方案，追踪的门限值t是固定的，不允许被动态调整.在匿名认证的实际应用中，追踪示证者的难度不同，需要动态调整追踪的门限值.

本文将动态认证加密思想^[9]引入到匿名认证方案中，实现动态门限追踪的匿名认证方案.其安全性依赖于离散对数假设和Diffie-Hellman (DDH) 假设.

1 动态门限追踪匿名认证方案 1.1 系统初始化

本方案包含成员集合U={U₁, U₂, …, U_n}，系统中心SC和公告栏NB.NB主要用来发布公共参数、成员的公开信息等，且只有SC有权发布或修改NB上的数据，各个成员只能查询NB上的数据.

在系统初始化中，各个成员自主选择私钥.

1) SC选取大素数p和q(且q|p-1), Z_q上的q阶元素g, 单向哈希函数H:{0, 1}^*→Z_q，并将参数{p, q, g, H}发布到NB上.

2) 成员U_i选取身份标识ID_i∈Z_q和私钥x_i∈Z_q，按照 (1) 式计算公钥y_i，

(1)

并将{ID_i, y_i}发给SC.若存在某些成员的ID_i和y_i相同，SC强制要求对应的成员重新选取参数.最后SC将互不相同的{ID_i, y_i}发布到NB上.

1.2 匿名认证

示证者U_k从NB上查询若干成员的公钥信息，并将自己的公钥隐含在公钥集UA={y₁‖y₂‖…y_d} (符号“‖”表示串联) 中，借鉴环签名^[1]思想，生成环签名σ，并发送给验证者U_v验证.如果环签名正确，U_k通过匿名认证.匿名认证过程具体包括签名生成和签名验证两个过程.

1) 签名生成

U_k对消息M∈{0, 1}^*产生环签名σ.

① 选择门限值t∈Z_q(t为1.3节中的追踪门限).

② 选取随机数r∈Z_q，按照 (2) 式计算R,

(2)

从NB上查询各个成员的信息{ID_i, y_i}，使用n个点{(ID₁, y₁^rmod p), (ID₂, y₂^rmod p), …, (ID_n, y_n^rmod p)}，按照 (3) 式构造n-1次Lagrange插值多项式f(x),

(3)

计算n-t个值{f(1), f(2), …, f(n-t)}，然后按照 (4) 式计算Q_k,

(4)

将匿名追踪信息{R, f(1), f(2), …, f(n-t), Q_k}发给SC在NB上公开.

③ 选取随机数α∈Z_q，按照 (5) 式计算c_k+1,

(5)

对于i=k+1, …, d, 1, …, k-1(即i≠k)，选择w_i∈Z_q，按照 (6) 式计算c_i+1,

(6)

按照 (7) 式计算w_k

(7)

④ 生成环签名σ

(8)

并发送给U_v.

2) 签名验证

U_v收到环签名σ后，对于i=k+1, k+2…, d, 1, …, k-1，按照 (6) 式计算c_i+1.如果

(9)

成立，说明环签名正确，U_k属于集合U.否则，U_k不属于集合U.

1.3 匿名追踪

如果示证者U_k存在不良行为，需要追踪其隐私身份.为了在可追踪的同时，提高U_k隐私身份的安全性和追踪门限值的灵活性，匿名追踪环节采用动态门限联合追踪.匿名追踪过程如下.

1) t个成员使用各自的私钥x_i，计算出R^x_i，产生t个点{(ID₁, R^x₁mod p), (ID₂, R^x₂mod p), …, (ID_t, R^x_tmod p)}，从NB上查询n-t个值，产生n-t个点{(1, f(1)), (2, f(2)), …, (n-t, f(n-t))}，按照 (10) 式计算E_k,

(10)

2) 按照

(11)

输出公钥y_k，即示证者U_k的隐私身份.

1.4 成员加入

新成员U_n+1申请加入集合U时，选取身份标识ID_n+1∈Z_q和私钥x_n+1∈Z_q，按照 (1) 式计算公钥y_n+1，并将{ ID_n+1, y_n+1}发给SC.若{ ID_n+1, y_n+1}与U中其他成员的信息相同，SC强制要求新成员U_n+1重新选取参数，直至参数不相同为止.最后SC将{ ID_n+1, y_n+1}发布到NB上.

1.5 恶意成员撤销

当需要撤销某个恶意成员U_i时，系统中心SC在NB上发布“撤销成员U_i”的信息，并将其对应的信息{ ID_i, y_i}从NB上删除.为了使U_i不能再参与动态门限追踪，示证者U_k使用NB上剩余的n-1个成员的公开信息，产生n-1个点

按照 (3) 式重新构造n-2次Lagrange插值多项式f′(x)，重新计算n-t个值{f′(1), f′(2), …, f′(n-t)}.按照 (4) 式重新计算

将新的匿名追踪信息{R, f′(1), f′(2), …, f′(n-t), Q′_k}发给SC，并请求SC替换之前的匿名追踪信息.

2 方案分析 2.1 性质分析

定理1    匿名认证性：在DDH假设的前提下，可完成对示证者身份的认证，同时还保证示证者身份的匿名性.

当收到环签名σ后，对于i=k+1, …, d, 1, …, k-1(i≠k)，验证者U_v按照 (6) 式计算各个c_i+1，得

由 (7) 式可知

由 (5) 式可得

可见，U_v计算得到的c_k+1与各个c_i+1形式一致，即求得的c_i(i=1, 2, …, d) 序列与签名生成过程中的c_i(i=1, 2, …, d) 序列一致.因此，

(9) 式成立，U_k通过认证.

在整个匿名认证过程中，示证者并不直接使用n个点 (ID_i, y_i) 构造n-1次Lagrange插值多项式f(x)，而是引入一个随机数r，使用n个点 (ID_i, y_i^rmod p) 构造f(x).因此，f(x) 不直接与公钥身份y_i相关，匿名认证过程可以保证示证者身份的匿名性.

定理2    追踪门限性：t个以上成员联合，方可追踪到示证者的隐私身份.

根据 (2) 式可知，

则t个成员提供的t个点{(ID₁, R^x₁mod p), (ID₂, R^x₂mod p), …, (ID_t, R^x_tmod p)}，等价于{(ID₁, y₁^rmod p), (ID₂, y₂^rmod p), …, (ID_t, y_t^rmod p)}.t个成员再从NB上查询到n-t个值{f(1), f(2), …, f(n-t)}，获得n-t个点{(1, f(1)), (2, f(2)), …, (n-t, f(n-t))}.因此，t个成员共计获得t+n-t=n个点，可恢复出n-1次Lagrange插值多项式f(x)，进而获得E_k=R^f(0)mod p.即

t个成员根据 (11) 式可求出

即出示证者的隐私身份.

从上述证明过程可知，若参与追踪的成员数量少于t个，获得的R^x_i的数量就少于t个，即使从NB上查询到n-t个值，累计获得的多项式上点的数量也少于n个，这将无法恢复出n-1次Lagrange插值多项式f(x)，继而无法求出E_k，无法追踪到示证者的隐私身份.因此，追踪成员的数量必须超过门限值t，方可完成示证者隐私身份的追踪.

定理3    门限动态性：匿名追踪的门限值t的大小可由示证者动态调整.

示证者使用n个成员的公开信息{ ID_i, y_i}，构造n-1次Lagrange插值多项式f(x).当确定匿名追踪的门限值t后，示证者计算n-t个f(i)(i=1, 2, …, n-t) 并公开.从定理2的证明过程可知，加上公开的n-t个f(i)，t个合法成员可门限追踪到示证者的隐私身份.若中途想改变匿名追踪的门限值t，示证者只需改变公开的f(i) 数量，其他公开信息无需变动.

2.2 安全性分析

攻击1    攻击者试图获取某个成员U_i的私钥.

攻击者试图获取成员U_i的私钥x_i有两种可能的方法：一是通过NB上公开的公钥y_i=g^x_imod p获取私钥x_i，这需要解决离散对数求解难题，而在现阶段这是不可能做到的，因此私钥x_i是安全的；二是门限追踪联合计算E_k时，通过参与追踪的成员U_i提供的R^x_i获取私钥x_i，根据离散对数求解的困难性，私钥x_i是安全的.由此可知，参与门限追踪的成员，并不会泄露其隐私信息.

攻击2    攻击者试图获取示证者U_k的隐私身份.

攻击者试图获取示证者U_k的隐私身份有两种可能的方法：一是通过NB上公开的匿名追踪信息Q_k=R^f(0)y_kmod p获取y_k.由于Q_k=g^rf(0)y_kmod p，r的随机性，可保证Q_k与公钥身份y_k不直接关联.因此，攻击者无法通过公开的Q_k获取示证者的隐私身份.二是通过环签名

中d个{w_i}(i=1, 2, …, d)，猜测出与U_k隐私身份相关的w_k，试图由w_k获取示证者私钥x_k，继而获取U_k的隐私身份.w_k=(α-x_kc_k)r^-1mod q中含有随机数α和r，因此攻击者无法通过w_k获取示证者的隐私身份.

攻击3    攻击者伪造示证者U_k生成环签名σ，试图通过匿名认证.

从1.2节的匿名认证过程可知，环签名σ的生成需要使用示证者U_k的私钥x_k.攻击者伪造σ，必须通过NB上公开的y_k先获取x_k，而从公式y_k=g^x_kmod p中获取x_k，面临离散对数求解问题.因此，攻击者无法伪造环签名σ，即无法通过匿名认证.

攻击4    t个以上成员合谋伪造成员身份，试图通过匿名追踪.

由 (11) 式可知，t个以上的成员合谋伪造成员身份通过匿名追踪，需要同时伪造一组相应的Q_k和E_k.在匿名认证过程中，示证者U_k选择随机数r且对其他成员保密，构造n-1次Lagrange插值多项式

公开

在匿名追踪过程中，t个以上成员获取

可见，以上数据中都含有保密的随机数r，起到间接保护关键数据f(0) 的作用.因而，增加随机数r，可以防止合谋伪造攻击.

2.3 有效性分析

1) 性质比较

与现有的门限可追踪匿名认证方案相比，本方案具有匿名认证性、追踪门限性、门限动态性等性质，如表 1所示.

2) 计算代价比较

为了表示方便，模指数计算代价用T_exp表示，模乘计算代价用T_mul表示，模加、异或等其他运算的时间复杂度相当小，这里忽略不计.

本方案在初始化阶段，让各个成员直接选择私钥，计算对应的公钥并发布到公共栏NB上，其代价仅为1次T_exp.匿名认证阶段，示证者构造n-1次Lagrange插值多项式f(x)，公开匿名追踪信息，其计算代价为 (2n-t+d+1)T_mul+(2n-t+d+1)T_exp.匿名追踪阶段，t个成员产生t个点，实现门限追踪，其计算代价为nT_mul+nT_exp.与其他方案计算代价的比较详见表 2.

表 2中的数据显示，初始化阶段本方案几乎无计算代价.匿名认证阶段，与文献[4]方案相比，模乘和模指数计算相对减少，与文献[8]方案相比，模乘和模指数计算相对增加，但仍然是线性级的.匿名认证阶段增加的计算量，主要是为匿名追踪阶段动态调整门限做准备的，其认证本身的计算代价并没有增加.从三个方案计算代价的比较来看，在计算代价增加不多的前提下，本文方案允许动态改变匿名追踪的门限值，因而更能推向实际应用.

3 结论

本文提出的动态门限追踪匿名认证方案，允许成员自主选择子密钥，借助环签名实现匿名认证，引入动态认证加密思想，允许动态改变匿名追踪的门限值.根据操作权限的级别，可对本方案加以拓展，应用到具有多级操作权限的机构或部门.