实用的前向安全性群签名方案

------By Song

前向安全性：当群公钥保持不变，一个群成员的群签名密钥evolves over time使得当前时间段的群签名密钥泄露不能使攻击者伪造过去时间段的群签名。前向安全性对于减少密钥泄露引起的损害是非常重要的，并且特别的是，对群签名是非常可取的（desirable）因为签名密钥泄露的危害随着群规模大小的增加而增加。

我们拓展前向安全的群签名方案提供群成员撤销问题的解决方法（不需要re-key所有其他群成员）。我们提供第一个解决方法，该方法支持回溯公开的撤销和后向无关性以及签名长度于撤销成员数量。

在先前的群签名方案，一个群成员签名密钥的暴露不仅仅需要改变群公钥和签名密钥，而且使所有先前得到的群签名失效，因为GM不能分辨一个签名是产生自攻击者所获得群签名之后还是被攻击者获得群签名之前的合法群成员。

前向安全的群签名如何减少群签名密钥泄露的损害。攻击者在时间段j破坏一个群成员的系统，得到该成员的群签名密钥SKj。因为单向性（one-way），攻击者不能计算相应的先前时间段的群签名密钥。假设用户B得到一个时间段j之前文件m的群签名。B希望能使用签署过的文件m在相当长的时间（长到过了时间段j后）。当发现SKj已经被泄露，群公钥被撤销。如果群签名方案不具有前向安全性，显然，B在文件m上获得的群签名就会变得无效并且B需要得到一个新的在文件m的签名。但是，当群签名被构建成前向安全的方案，攻击者不能计算关于先前时间段的群签名密钥，因此群只能撤销在任何时间段j后面的群公钥。如此任何关于时间段j之前的正确的签名仍可接受。因为在B获得在签名的,t仍然是正确的签名并且B不需要获得一个新的在m的签名。

我们扩展由Ateniese等人提出的群签名方案，采用两种不同的方法构建两个不同的前向安全的群签名方案。第一个方案利用[6]中的技术而第二个方案采用一个新的技术[24]实现前向安全性。另外，我们指出前向安全性群签名方案确保

其他想要的安全特性在一个很小的额外开销。例如，当新成员C加入，具有前向安全性的群签名方案，我们能新成员产生签名只在将来的时间段有效而不是在加入时间段之前没有额外的开销。更一般的，我们支持时限的群成员身份特性在一个额外的开销，也就是群成员值被允许在限定的时间段里代表群，签名。

公开撤销特性：攻击者在时间段i窃取了A的群签名密钥。A的群签名密钥的泄露在时间段j被发现。GM撤消了A的群签名密钥在时间段j。所以没有人能在时间段j之后使用A的群签名密钥来产生正确的签名。这就叫做：公共撤销性。

回溯公开撤销性：因为攻击者本来会在时间段i之后的任何时间，代表群使用A的群签名密钥签署文件，使用其他成员的签名密钥签署的签名应该仍旧保持有效、匿名和无关性。回溯公开撤销性包含公开撤销性，反之不然。

后向无关性:在时间段i之前，使用A的群签名密钥产生的签名仍该保持有效，匿名和无关性，因为这些签名是A产生的，而不是攻击者。

我们扩展的群签名方案提出支持回溯公开撤销性和后向无关性的前向安全的群签名方案，并且签名长度于撤销成员数量。

弱前向安全性：假设一组群签名密钥ф={ki，ti}1≤i≤L，ki，ti表示成员i在时间段ti的群签名密钥，并且t=min（t1，…，tL）。我们称Ω（ф）是ф的弱跨距（weak-span），Ω（ф）表示该组群签名密钥{ki，wi}1≤i≤L，t≤wi≤T。我们认为如果攻击者给定一组群签名密钥ф不能产生一个在Ω（ф）中正确的群签名密钥，那么群签名方案满足弱前向安全性。

强前向安全性：给定一组群签名密钥ф={ki，ti}1≤i≤L，ki，ti表示成员i在时间段ti的群签名密钥，我们称ψ（ф）是ф的跨度（span），ψ（ф）代表该组群签名{ki，wi}1≤u≤L，ti≤wi≤T。然后，如果攻击者给定一组群签名密钥ф，不能产生一个在ψ（ф）里的正确的群签名，我们说，该群签名方案满足强前向安全性。

时限的成员身份：GM能一个成员的群成员身份通过签发给他群成员密钥，该密钥只能在某些时间段产生正确的群签名。

回溯公开撤销性：在时间段i，GM能从时间段j开始撤销一个群签名密钥，使得任何使用这个群签名密钥在时间段j之后产生的签名变得无效。而且，所有在时间段j之前使用这个群签名密钥产生的签名应该对任何除了GM的人仍保持

匿名性和无关性。

3. 预备知识

我们的方案依靠强RSA假设和DDH假设。

让n=pq成为RSA-Like模数并让G成为Zn*的循环子群。SRSA假设是：给定n和z∈G，难以找到v∈G和e∈Z＞1，使得z≡ve（mod n）。

DDH假设是：给定g，gx，gy和gz，难以确定gxy？gz（是否相等）。 我们使用现有的零知识证明协议作为我们方案里的building blocks。这些零知识证明协议可以使用一个理想的哈希函数（也成为Fiat-Shamir启发式算法）实现。并且我们提到由此生成的知识签名。因为篇幅，我们不回顾这些协议的细节。我们使用PK来表示谢意是一个知识签名协议，希腊字母来表示被证明的秘密知识，所有其他的参数对于示证者（还没有成为群成员的用户）和验证方。

离散对数的知识签名：让G=表示阶为q的一群素数，且y∈G。我们使用PK{(α)：y=gα}（m）来表示在群G里，logg的知识签名。这个协议由[29,15]设计并在辅助字符串模型指出零知识[19]。

在QRn中的离散对数的知识签名：

让n=pq，p=2p’+1，q=2q’+1，并且p、q、p’和q’都是素数。G是QRn的生成元，并且y∈QRn。我们使用PK{（α）：y=gα}（m）表示在群QRn中loggy的知识签名。一般的，示证者不容易证明y是一个二次剩余。所以我们使用协议PK{（α）：y2}=(g2)α}代替，因为logg2y2=loggy,假如y是二次剩余。

知识签名的表示法：

让PK{（α1，…，αv）：y=g1α1…gvαv}（m）表示一个元素y∈G关于根（bases） g1，…，gv∈G的知识签名的表示法。

离散对数相等性知识签名：

y

PK{（α）：y1=gα∧y2=hα}（m）表示对于根（bases）g∈G和h∈G，两个群元素y1，y2∈G的离散对数相等性的知识签名。

知识签名的范围：

PK{（α）：y=gα∧α∈[a，b]}（m）表示y∈G关于g∈G离散对数的知识签名，使得loggy映射（lies）进整数区间[a，b]。如果示证者没有被提供分解的模数， 这个协议能在SRSA假设下有效的完成。

4.1 方案I

Setup 步骤:GM选择两个 （ln/2）-bit 素数p=2p’+1和q=2q’+1，p’和q’

也是素数。让n：=pq。GM也随机选择元素a，d，g，g1∈RQRn，一个秘密数(元素)x∈RZp’q’*,并使y：=gx mod n。它存储(p, q, x)作为他的密钥并且公开(n, a, d, g, g1, y)作为群公钥。GM同时也在群公钥是正确的时候分割时间成T个时间段，并让时间间隔公开。

本文的剩余部分，我们使用下面概念。让Г和Λ表示整数区间：Г=（-2lГ，

2lГ），Λ=（2lΛ，2lΛ+1），lΛ＞T+lГ+2. 直观.方案的直观如下：

当用户U加入群，他和GM一起随机选择xu∈RГ，使得U知道xu和GM只知道yu：=axu。GM之后随机选择一个素数eu∈Λ，计算cu，0：=（yud）1/（eu2T） mod n，并发送U（cu，0，eu）。如此，（xu, cu,0, eu）是U的群签名密钥。在强RSA假设下，除了GM没人能产生正确的群签名密钥。GM然后使用平方（squaring）作为一个公共单向函数来evolve群签名密钥。特别的，U在时间段i的群签名密钥是（xu，cu，i，eu），cu，i=c2u，i-1 mod n。为了在时间段i签署消息m，U产生非交互的知识证明，

用户知道（xu，cu，i，eu）使得，xu∈Г，并且eu∈Λ，

在非交互式证明的挑战是依靠m作为在标准Fiat-Shamir 启发式算法。为了启用Open步骤，签名者也使用GM的公钥加密cu，i并产生加密是正确形式的非交互式证明。万一发生争议，GM可以简单地解密cu，i的值来确定实际的签名者。

Join步骤:

Evolve 步骤：假如U有在时间段j的群签名密钥(cu,j, eu, xu)。然后，在

时间段j+1，他的群签名密钥变成(cu,j+1, eu, xu), cu,j+1：=c2u，j mod n.

Sign和Verify 步骤:假设U在时间段j有群签名密钥(cu,j, eu, xu)。为了在时间段j签署消息m，他首先选择r1∈R{0，1}2ln，计算A=cu，

jy,B=g，并且产生：r1

r1

一个验证方简单的检查以上知识签名的正确性。

Open步骤：DAA不需要。

4.2 安全性分析

在这个小部分，我们指出方案I是一个安全的群签名方案并满足弱前向安全性。我们在这儿陈述我们的定理并想提供给读者附录A为细节证明。

4.3 时限的群成员身份

当群成员U在时间段i加入，如果他只在时间段i得到群签名密钥(cu,i, eu, xu)，然后他只能在接下来的时间段i产生正确的群签名并而不会在i之前产生。如此，他的群成员身份只能在他加入的时间段有效。

我们可以很容易的拓展方案I来支持一个时限群成员身份更普通的形式，也

就是一个群成员只被允许在限定的时间期间代表群签名。基本思想是两链群签名密钥。一链evolve 前向 over time（正如方案I）而另一链是后向的。注意到，前后两链共享同一个xu。签名者需要知道在时间段i前链和后链的签名密钥产生一个在时间段i的正确的签名。知道在前向链时间段i的签名密钥可以让签名者计算所有时间段i之后在前向链的所有签名，知道后向链在时间段i的所有签名密钥能使签名者计算出时间段i之前后向链内的所有签名。所以知道i的签名密钥在前链和j的签名密钥在后链允许成员签署i和j间的文件，给定i4.4 撤销

我们拓展方案I来支持具有后向无关的追溯的撤销。让h成为一个序列n循环

群的生成元，DDH问题是困难的。当群成员U在i使用它的群签名密钥(cu,j, eu, xu)签署消息，除了基本的Sign步骤外，U也作如下：他随机性选择r∈Zn并计算g2=hr，C=g2cu，j，并显示（reveals）（g2，C），我们称他为撤销token。U通过知识签名证明g2和C是正确的构成。当用户V从时间段i开始被从群剔除时，cv，i和i将被显示在撤销列表中。假设验证方有时间段j的签名，j≥i并且撤销token在签名中是（g’2，C’）。为了看是否签名密钥已经被剔除，验证方简单地计算cv,j并检查是否

。如果他们相等，意思是签名被撤销。更细一步，对于U

在j签署消息m，协议将如下：

第一个协议PK是与我们原来的前向安全性群签名方案相同的。第二个PK2是

一个新的零知识证明协议，我们在附录B构建并解释其细节。

这个方案清楚的支持公共地撤销群成员资格。然而，后向无关性依靠一个新

的加密假设，我们叫做log-square假设：n是两个安全素数产生的，如方案I。G是一个序列n的循环群，DDH问题是困难的，并且g2是G的生成元。给定随机的v∈RQRn，并且w=g2u∈RG，对攻击者，在没有知道n的情况下决定v=u2 mod n是很难的。在这个假设下，很容易看出我们的方案支持后向无关性。密码学假设减少到不是因子分解就是离散对数问题。我们猜测这个问题是难以解决的，尽管研究这个问题仍需要完成很多研究。

5. 前向安全群签名II

Setup 步骤:Setup步骤几乎与方案I一样。除了方案I的Setup之外，让Λi表

示整数间隔

。GM也详述一个确定性单向方法使得给定一个随机的素数eu，i∈Λi，一个可以产生一序列素数eu，i，…，eu，T，eu，j∈Λj，for i≤j≤T。给定只有eu，i对于某个i≤j≤T，后向计算是很难的，也就是eu，k，for k＜j。

直观.这个前向安全群签名与方案I的在section 4是相似的，除了它使用不同的单向函数来evolve群签名密钥。当用户U加入群，与方案I相似，他和GM一起随机选择xu∈Г使得U知道xu并且GM只知道

0

。GM之后随机选择一个素数eu，

∈Λi，0≤i≤T。

Join步骤:加入步骤与方案I相似出咯额第三步。在第三步，GM随机地选择一

个素数eu，0∈Λ0，然后产生一个序列的素数eu，i∈Λi，0≤i≤T。

Evolve步骤:

Sign和Verify步骤:假设U在j有群签名密钥(cu,j, eu,j, xu)。为了在j签

署消息m，他首先选择r1∈R{0,1}2ln,

一个验证方简单的检查上面知识签名的正确性。

5.2 安全性分析

我们show方案II是一个安全的群签名方案并满足强前向安全性。我们陈述我们的定理并给读者附录A用于细节证明。

5.3 时限群成员身份

使用方案II，我们实际上能正确的支持群成员身份for 时间段的子群with几

乎没有开支。例如，当用户U加入群，如果GM只想在时间段t1，…，tm签发U群成员身份正确，之后在第三部，代替计算bu作为整个序列eu，0，…，eu，T，GM计算

mod n。如此

U可以只在时间段t1，…，tm代表群签名，没有额外的开支在秘密存储和计算时间相比于方案II的基础。

5.4 撤销

方案II的撤销很简单。当用户U使用自己的群成员身份(xu, eu,i, cu,i)签

名，除了在方案II基本的Sign步骤，他也做下面的：随机产生一个元素g3∈QRn并展示g3和

，并用零知识证明D是正确构成的。我们叫（g3，D）签

名的撤销token。更细一点Sign步骤如下：

现在如果GM想从时间段i撤销U的签名，他简单地显示eu，i和i。如果用户V在j≥i获得签名并且签名的撤销token是（g’，D’），为检查是否签名被撤销，（也就是他是U签署的）V从eu，i计算eu，j并简单的检查是否D’=(g’)eu，j。如果他们相等，它意味着签名被撤销，因为他是在时间段i由U签署的。

这个撤销方案支持回溯公开的撤销。很容易看到所有由其他成员签署的签名

保持匿名性和无关性。。这个方案对于撤销的成员也支持后向无关性在DDH假设是困难的，因为不知道这个指数，给定在两个签名里的（g’,D’）和（g’’,D’’）两个撤销的token，如果一个能tell是否决DDH问题。

而且，withO（logT）存储开支，我们拓展方案II来允许时限撤销，也就是

之后他能解

只在某些时间段撤销群成员的签名。基本思想是代替产生序列eu，0，…，eu，T使用一个单向树。序列eu，0，…，eu，T构成自上而下的单向树的叶子节点。知道根，one能产生整个树；并且知道一个间隔节点，one能产生整个子树，但不是任何其他在这个书上的节点。如此，当GM只想在时间段t1撤销群成员U的签名，他reveals间隔节点作为子树的根that覆盖时间段从t1到t2.如此，任何用户可以计算eu，i，for t1≤i≤t2并且之后能检查是否签名被撤销。

6. 讨论

我们的两个安全群签名方案都是基于[3]提出的群签名方案并且使用单向函

数用作演变群签名密钥来实现前向安全性。这两个方案有不同的性能和安全权衡策略。方案I由有效的Evolve步骤（仅仅需要一个平方），尽管签名和验证效率较低（需要O（T）平方）。方案II由高效的签名和验证步骤并且没有额外的管理费用相比[3]中的非前向安全群签名方案。但是方案II在Evolve步骤中效率很低（需要O（T）exponentiations 取幂），尽管相似的技术在[24]能被用来减少开销with 存储空间权衡。方案II也能比方案I实现更灵活的时限的群成员身份。方

案II支持强前向安全，and 方案I只能证明满足弱前向安全性。方案II相比方案I有更高效的撤销机制并且不需要新的为保证安全的密码学假设，而方案I需要一个新的具有后向安全性的用于撤销的假设。注意到两个方案也都满足一个有趣的性质，即使攻击者在时间段i learns （学习获得）群成员U的群签名密钥，他仍不能确定那个签名是U在时间段i产生的，也就是U的签名在时间段i依旧保持匿名性和无关性。

7. 结论

本文，我们提出我们的前向安全群签名方案。我们的方案满足前向安全性的同时也满足先前传统的群签名方案的安全特性。我们的方案在群成员数量的性和签名长度的性和群密钥在群公钥生命周期期间于时间段的数量上都是有效的。而且我们扩展我们的方案来提供第一个解决方法使得回溯公开的撤销的群成员身份具有后向无关性并且签名长度于撤销成员数量。

我们的方法阐明前向安全性是一个对群签名方案特别重要的性质。不仅因为签名密钥的泄露的危险会随着群大小的增长而增加，而且因为前向安全帮助使其他所期望的安全特性处于一个小的额外开支中，比如时限群成员和回溯撤销。我们前向安全的群签名方案也有一个附带的好处，及时攻击者在时间段i learns（学到获得）群成员U的群签名密钥，他仍然不能确定那个签名是由U在时间段i产生的，也就是在时间段i，所有U的签名都保持匿名性和无关性。

致谢

我们想要感谢Giuseppe Ateniese和Gene Tsudik关于他们对第5部分（特别是5.4）很有帮助的讨论和贡献。我们想要感谢匿名的评论者关于他们有帮助的反馈，Doug Tygar 和 Adrian Perrig 对于他们关于本文的鼓励和帮助。