层次撤销群签名: 概念与构建*

程小刚, 郭 韧, 周长利

1. 华侨大学 计算机科学与技术学院, 厦门361021

2. 华侨大学 工商管理学院, 泉州362021

1 引言

群签名[1,2]是指一群人中的任一个人都可以生成合法的签名, 外界只能验证此签名合法但不知道具体是这群人中的哪一个做的签名, 只有拥有密钥的群管理员(Group Manager, GM) 才能打开签名找出真正的签名者. 由于群签名同时具有隐私保护和可追踪的良好特性, 所以是一种具有中心地位的密码系统, 可应用于众多领域, 如电子投票[3–5]、电子货币[6–9]、电子拍卖[10–13]、可信计算[14,15]和车载自组网[16–18] 等等.

群签名方案中一个重要的问题是成员撤销问题[19], 即如果一个成员离开群(比如从公司离职) 或成为恶意成员(如做了很多不负责任的签名) 等, 那么他的签名能力就要被撤销.

最简单的撤销方法是GM 更新群签名验证公钥, 并给每个合法的群成员重新发送一个私钥(排除撤销的成员), 显然开销为O(N), N 是群的大小.

VLR (Verifier Local RevocRevoc) 验证方本地撤销[20], 指的是GM 把撤销成员的信息放入一个列表中, 群签名时每个合法群成员都要证明自己不在撤销列表中, 显然此种方式下每个群签名的签名与验证开销为O(R), R 是撤销成员的数量.

DA (Dynamic Accumulator) 动态聚集器撤销[21], 动态聚集器就是可以把许多数据合并成一个数据,并有高效NIZK 协议来证明签名者持有被聚合数据中的一个, 此种方式下GM 只要广播一条短消息给所有签名者和验证者即可.

群签名还有其他多种不同的撤销方式来适应不同应用场景的需要, 如双重撤销[22], 即同时支持两种撤销方式: 正常撤销(不可链接撤销) 和恶意用户的撤销(可链接撤销), 正常撤销后, 群成员不能再生成合法的群签名, 但其以前做的签名任然保持匿名, 而恶意成员被撤销后, 不仅其不能生成新的群签名, 其以前做的群签名也丧失匿名性被曝光了; K +L 次条件撤销[23], 签名次数K 次以内不可追踪(完全匿名), 而超过K 次小于K +L 次则GM 可追踪, 超过K +L 次则任何人都可追踪了即被曝光; 三重撤销[24],可以三种不同的方式撤销群签名: 根据已泄露的群成员私钥撤销、根据某个恶意成员的群签名撤销和GM强制撤销.

本文提出一种新的撤销方式的概念: 层次撤销, 其支持普通的单个成员撤销, 然后若某个小组(由多个成员构成) 不可信, 则可以撤销此小组, 当然简单的方法是对每个成员进行普通撤销, 但效率非常低; 而层次撤销中支持高效撤销一个小组, 其开销同撤销单个成员是差不多的; 类似还撤销大组(由多个小组构成)、更大的组等等, 即层次撤销.

这种层次撤销群签名方案可应用于如下的场合: 一个单位里要撤销某个部门, 若用普通VLR 撤销群签名方案, 那么部门中的每个人都要单独撤销, 效率很低; 而用本文提出的层次撤销群签名方案, 可简单撤销此部门, 效率同撤销单个成员近似. 还有就是如果某个小团体中多人出现问题, 成为恶意成员, 那么可认为此小团体整体不可信, 作为处罚, 就可用本文的方案高效撤销整个小团体.

同本文相关的工作还有文献[25,26] 等, 也是采用层次结构组织成员, 成员撤销采用VLR 撤销, 主要的区别在于撤销时要把每个成员的信息放入RL 中去, 而本文支持高效撤销一整个小组、大组等等, 即能高效进行整体撤销.

并基于RSA 假设、多项式、NIZK (非交互零知识证明) 等构建了一个具体的方案, 其基本思想是多项式的解作为私钥, 群签名就是NIZK 证明签名者拥有私钥满足公钥多项式; 同一小组的成员其公钥的值被安排在同一条直线上, 这样撤销时公布此条直线方程即可; 而大组所有成员的公钥被安排在一个平面上,撤销时公布此平面方程; 以此类推来进行层次撤销.

本文安排如下: 第2 节介绍了层次撤销群签名的定义和一些预备知识; 第3 节给出层次撤销群签名的具体构建; 方案的安全性和效率在第4 节进行了分析和对比; 最后第5 节是结束语和一些值得进一步研究的方向.

2 预备知识

定义1 (可撤销群签名) 一般由下面的6 个随机多项式算法组成:

(1) 设置: 给定一安全参数K, 群管理员(GM) 生成一个群公钥(GPK) 可用于群签名的验证, 和一群私钥(GSK) 可用于生成成员私钥;

(2) 加入: 用户向GM 申请加入群成为群成员, GM 验证用户身份并同意其加入后, 生成成员私钥并秘密传给此新成员; 同时保存相关信息以便将来打开此用户所做的群签名;

(3) 签名: 群成员可利用自己的成员私钥生成对任一消息的群签名;

(4) 验证: 任何人获得GPK 和一个消息/签名对, 可验证此群签名是否合法, 但对合法的群签名他不能找出实际的签名者;

(5) 打开: 对于合法的群签名, GM 能打开并找出实际的签名者;

(6) 撤销: GM 可撤消某成员的签名权利, 之后此用户就再也不能生成合法的群签名.

定义2 (层次撤销群签名) 我们的层次撤销群签名对上述的加入和撤销操作进行了扩展:成员加入时, 将相关成员放在同一小组中, 相关小组放在同一大组中, 以此类推.

撤销时分成下面几种情况:

(6.1) 撤销某个成员, 同原来的撤销功能;

(6.2) 撤销某个小组, 即撤销后, 此小组的任一成员都不能生成合法群签名;

(6.3) 撤销某个大组, 即撤销后, 此大组中的任一小组都被撤销了;

(6.4) 以此类推可撤销更大的组.

参见图1, 其中Ln层为群成员, 而L1层为最大的组.

图1 层次撤销成员组织图Figure 1 Membership structure of hierarchy revocation

定义3 (可追踪性安全定义模型) 博弈游戏定义如下, 敌手为A, 挑战者C:

(1) C 作为群管理员GM, 生成群公私钥GPK 和GSK, 并把GPK 发给敌手A;

(2) 利用GPK, A 可以向GM 申请加入群Join, 成为群成员并得到成员公私钥MPK 和MSK; A 也可以申请得到对某个消息m 的群签名Sm; A 可以要求得到某个群成员的私钥MSK; A 也可以要求GM 撤销某个群成员;

(3) A 输出一个消息m 和签名对(m,Sm), 如果签名合法(未被撤销), 且A 未要求查询得到过m 的群签名, 且签名Sm不能被GM 追踪为A 已经查询过或攻破过的群成员, 则称A 赢得胜利.可追踪性安全则指没有多项式时间的敌手A 能以高概率赢得上述博弈游戏.

定义4 (零知识证明系统(ZK)) 有两方, 证明者P (Prover) 和验证者V (Verifier), 通过一个交互协议, P 要向V 证明他具有某个知识(如离散对数、整数的因子分解等), 协议要满足下述两个安全性条件:

(1) 零知识特性: 即V 只能确信P 拥有某个知识, 但不能够获取到这个知识的任何信息;

(2) 公正性: P 不能欺骗V, 即如果P 没有某个知识, 他就不能使V 相信他有.

定义5 (非交互式ZK (NIZK)) 取消上述ZK 协议中的交互过程, 只要P 要V 发送一条消息来实现ZK 证明. 如著名的Schnorr 签名就是一个NIZK, 来证明签名者拥有作为私钥的离散对数.

3 层次撤销群签名构建

3.1 初始普通撤销群签名方案构建

本方案群公钥就是一个模N (N 为一安全的RSA 模) 的多项式, 成员私钥就是此多项式的一个解,群签名就是NIZK 来证明成员拥有一个解, 如可用文献[27–30] 等中提出的NIZK 方案.假设群有3 个成员, 则选择一个有三个变量的随机多项式如:

N 是一安全的RSA 模数, 给定其中的(i,j,k), 而系数(a,b,c,d) 待定, 3 个成员随机选取三组数

则可代入上式解出 (a,b,c,d), 三个方程四个未知数是因为上述方程两边可同乘以 1/a 得到(1,b/a,c/a,d/a).

如假设我们选定的多项式为(如上所述我们令a=1):

随机选择:

可得下面三个方程:

在有理数上可解得: x=−2702/143, y =−583/26, z =1272082/143, 模N =323 后得到:

即公钥多项式为:

可验证(xi,yi,zi),i ∈{1,2,3} 都是此多项式方程的解. 如果GM 想撤销第一个用户, 那么他可以令(x1,y1,z1) 为其他值, 再重新生成新的公钥多项式. 如令(x1,y1,z1)=(7,8,9), 那么方程组为:

可解得: x=−7291/520, y =4559/1040, z =521017/260, 即:

即新的公钥多项式为:

代入显然可得f(3,4,5) = 215= 0, 而f(4,5,6) = f(5,6,7) = f(7,8,9) = 0, 即第一个用户(密钥为(x1=3,y1=4,z1=5)) 已被撤销.

也有可能出现的情况是对于随机选择的新密钥, 有可能会出现同余方程组无解的情况; 因为线性方程组一般会有唯一的有理数解, 但若此有理数的分母同RSA 模不互素, 则线性同余方程组无解. 比如若上例中我们随机选择的新用户的密钥为(6,7,8), 则无解, 因此时的线性方程为:

解为: x = −1436/85,y = −1941/170,z = 515634/85, 此时(85,323) = 17,(170,323) = 17, 所以同余方程组无解.

但显然对于安全的RSA 模数来说, 此种情况出现的概率很低, 并且假若出现也只要重新生成一个新的随机密钥即可.

本方案撤销比较方便方便, 只要GM 更新群公钥即可, 正常用户不需要更新私钥, 但缺点是公钥过长为O(n), 签名和验证效率也较低为O(n), n 是群的大小. 下面我们对此方案进行提高来构建我们的层次撤销群签名方案.

3.2 层次撤销群签名构建

下面我们来基于多项式构建层次撤销群签名方案:

(1) 群公钥是一个多项式如:

其中N 是一个安全的RSA 模, 变量的个数决定了可撤销的层数.

(2) 群成员的私钥为(x1,y1,z1,w1),(x2,y2,z2,w2),(x3,y3,z3,w3),··· 等等, 都是上述公钥多项式的解, 即:

注意对任意的(x,y,z), 通常都有相应的w 满足公钥多项式方程(如上述分析, 只有极个别情况可能无解).即解空间近似为一个三维空间(x,y,z). 那么在生成私钥时, GM 先生成X,Y,Z,W, 再利用N 的因子分解来求出成员私钥x,y,z,w. GM 可把同一小组的成员放在一条直线上, 同一大组成员放在同一平面上.即使同一小组成员的: X =xi,Y =Yj,Z =zk满足一直线方程. 而同一大组成员X,Y,Z 满足一平面方程等等. 显然, 公钥多项式中的变量个数同可撤销的层次式相关的, 即若有n 个变量, 则支持撤销的层次数为n −1. 如本例中有四个变量, 则支持三层撤销: 单个成员(点)、小组(直线) 和大组(平面).

(3) 群签名时, 群成员公布自己的Xt,Yt,Zt,Wt, 然后再NIZK 证明:

对SPK{x : xi= X}(m) 的基于ROM 模型构建如下[27], 即对消息m 的知识签名为(t,T), 其中t = xcr mod N, T = rimod N, r 为随机数, c = Hash(m) (Hash 函数看作是Random Oracle), 验证时看ti=XcT mod N 是否成立即可.

此种基于ROM 模型的NIZK 优点是简单, 缺点是安全性较基于标准模型的方案弱. 文献[28–30] 中的方案是交互式的ZK 协议不适合构建签名方案, 而且这些方案都是对多项式函数的根的零知识证明, 此处用的方案比较简单只是证明拥有一个RSA 签名.

(4) 验证当然就是验证上述SPK 是否合法, 以及下式是否成立:

成立当然说明签名者拥有公钥多项式的一个解.

(5) 打开签名: 利用群签名中的Xt,Yt,Zt,Wt, 以及成员加入时提供的信息, GM 可简单的判断是谁做出的签名.

(6) 撤销:

(a) VLR 单个成员撤销: 把此成员的(X,Y,Z,W) 信息放入撤销列表RL (Revocation List) 中去, 这样验证方很容易判断一个签名是否由其签署;

(b) 小组撤销: 公布一条直线方程:

到RL 中去, 这样验证方可由签名中的Xt,Yt,Zt,Wt来判断签名者是否属于被撤销的小组;(c) 大组撤销: 公布一个平面方程到RL 中去:

下面给出一个具体的例子

例如, 作为公钥的多项式为:

可取一条直线如下:

任取此直线的两个点如(为简化描述, 以下运算都是模323 的运算):

可代入原线性化的公钥多项式7X +8Y +9Z+10W +2=0 解出对应的

所得的W 值相同, 因为此两点在同一直线上, 然后GM 利用私钥可求出相应的成员私钥:

群成员在签名时, 先公布(X,Y,Z,W), 然后再零知识证明[31]:

撤销时, 若撤销某个成员, 可把他的(X,Y,Z,W) 放入RL 中去即可, 而若要撤销小组, 可把上述的直线方程:

放入RL 中, 这样此条直线上的所有成员都被撤销了.

显然我们的层次群签名构建是可链接的, 即同一成员做的签名虽然匿名但是可分辨的; 所以一个重要的公开问题就是如何构建不可不可链接的层次撤销群签名方案.

4 安全性分析与效率对比

下面我们来证明上述层次群签名方案满足可追踪性:

定理1 基于RSA 假设, 上述的层次群签名方案是可追踪的.

证明: 基于RSA 假设, 下面来证明能赢得上述可追踪游戏的敌手A 是不存在的:

挑战者C 作为群管理员生成群公钥GPK 为N 和一个随机多项式

私钥 GSK=(p,q), 满足N =pq, C 并把GPK 发给A: 如果A 发出Join 的请求, 那么C 就利用GSK生成一个MSK=(xi;yi;zi;wi) 发送给A; 如果A 发出Sign 的请求, 那么C 就利用任意群成员的MSK来生成群签名

并发送给A; 如果A 发出Corruption 的请求, 要求得到对应某个群成员公钥MPK=(X;Y;Z;W) 的成员私钥, 那么C 就利用GSK 来计算对应的MSK=(x;y;z;w), 满足:并把此MSK 发给敌手A; 如果A 发出Revoke 的请求, 那么就把此成员的MPK = (X;Y;Z;W) 放到撤销列表RL 中去.

最后输出阶段, 来看A 的输出, A 能赢得可追踪的游戏, 即敌手A 能伪造签名, 即A 能造出(ˆx,ˆy,ˆz, ˆw), 满足公钥多项式且不同于任一组成员的私钥, 即:

且

那么下面来证明这样的敌手A 是不可能存在的, 否则就违反了RSA 假设:

首先, 易见生成(X,Y,Z,W) 满足方程

是容易的, 只需要随机选择(X,Y,Z), 然后再解一个线性方程就可求出对应的W; 对于A 来说困难在于如何生成成员秘钥(x,y,z,w) 满足

因A 没有对应的GM 私钥p,q :N =pq, 即RSA 模的因子分解.

由于(ˆX, ˆY, ˆZ, ˆW) /∈{(Xi,Yi,Zi,Wi)}, 必定有:

因为W 可由(X,Y,Z) 唯一确定(他们满足一个线性方程), 不失一般性假设ˆZ /∈{(Zi)}:

(1) 如果ADV 先选定ˆz, 再计算ˆZ = ˆzkmod N, 那么根据RSA 是随机置换的假设ˆZ 就是随机的,类似的可以生成随机的 ˆX 和ˆY, 那么由之而确定出来的 ˆW 也是必然是随机的, 根据RSA 假设,给定一个随机数 ˆW, 来计算相应的ˆw, 即其l 次方根是困难的.

(2) 如果如上所述, 先生成(ˆX, ˆY, ˆW), 再计算ˆZ, 那么类似上述ˆZ 是随机的, 那么根据RSA 假设计算ˆz = ˆZ1/kmod N 就是困难的.

所以, 根据RSA 假设, 能赢得可追踪游戏的敌手A 是不存在的.

关于匿名性, 我们的方案只满足有限匿名的特性, 即验证方不能知道签名者的身份信息, 因为签名中公布的(X,Y,Z,W) 都是随机值, 在加上NIZK, 都不会暴露签名者身份; 但同一成员所做的签名是可以被分辨出来的, 因签名中用的是相同的(X,Y,Z,W), 而GM 利用其数据库中保存的成员加入时提供的信息可知道其身份.

效率比较参见表1, 表中N 是群的大小, 即群成员的人数; R 表示被撤销成员的个数; L 表示可撤销的层数; 更新私钥是指在GM 撤销成员时, 合法的群成员需不需要更新自己的私钥; VLR 方案的验证开销为O(R), 是因为验证方要对RL 中的每一项来进行检验; DA 方案的撤销开销为O(N), 因为每个未被撤销的群成员都要更新自己的私钥, 所以撤销一个成员对整个群来说总体开销为O(N); NFHNF 方案比较高效, 主要缺点为公钥较大为O(N); 综合来看目前最高效的可撤销群签名方案是LPY 方案, 公钥为O(log N), 签名验证效率都为常量级O(1), 而且撤销成员是合法群成员也不需要更新私钥, 只是撤销开销为O(R). 表中也对各个方案所基于的数学假设, 和是否基于ROM 模型进行了比较; LPY 方案是基于标准模型, 安全性较高, 但其所基于的数学假设较复杂.

作为引例的我们的第一个方案效率较低, 公钥大小为O(N), 签名验证的效率都为O(N), 撤销成员的开销也是O(N), 优点就是撤销时合法成员不用更新私钥; 我们的第二个方案效率有所提高, 公钥大小、签名效率是O(L), 即依赖于所需要撤销的层次数, 验证效率是O(R)/O(1), 即假如撤销的单个成员, 那么验证效率是O(R), 而假如撤销的是一组成员, 那么效率比较高近似为O(1), 撤销操作也比较高效为O(1),即GM 只要把相关信息放入RL 中即可.

总体上看, 我们的方案的效率同其他可撤销群签名方案相比, 效率上并没有优势, 但我们的方案时支持层次撤销的, 具有其他方案所没有的可撤销小组、大组、更大组的功能.

表1 效率与安全性比较Table 1 Comparison of efficiency and security

5 结束语

本文提出一种新的群签名撤销的概念: 层次撤销, 即把所有成员组织成小组、大组、更大的组等这种层次结构, 这样撤销时可选择撤销个人、小组、大组等.

基于RSA 假设、多项式、NIZK 等技术给出了一个具体的方案, 撤销时对未撤销的用户没有任何影响, 只要GM 把成员、或小组或大组的相关信息加入RL 中即可, 签名验证者下载RL 后即可验证签名是否合法(即VLR 撤销), 但比传统VLR 撤销更高效, 因传统VLR 的RL 中每一项只能撤销一个成员, 而我们的方案的RL 中一项既可以撤销一个成员, 也可以撤销一组成员.

但我们构建方案的缺点是签名是可链接的, 即同一群成员的签名虽然是匿名的, 但是可被发现是同一成员签署的; 所以一个重要的公开问题就是如何构建不可链接的层次撤销群签名方案.