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

前向安全的群签名 -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获得在签名的,tj。如此在m的签名仍然是正确的签名并且B不需要获得一个新的在m的签名。我们扩展由Ateniese等人提出的群签名方案，采用两种不同的方法构建两个不同的前向安全的群签名方案。第一个方案利用6中的技术而第二个方案采用一个新的技术24实现前向安全性。另外，我们指出前向安全性群签名方案确保其他想要的安全特性在一个很小的额外开销。例如，当新成员C加入，具有前向安全性的群签名方案，我们能限制新成员产生签名只在将来的时间段有效而不是在加入时间段之前没有额外的开销。更一般的，我们支持时限的群成员身份特性在一个额外的开销，也就是群成员值被允许在限定的时间段里代表群，签名。公开撤销特性：攻击者在时间段i窃取了A的群签名密钥。A的群签名密钥的泄露在时间段j被发现。GM撤消了A的群签名密钥在时间段j。所以没有人能在时间段j之后使用A的群签名密钥来产生正确的签名。这就叫做：公共撤销性。回溯公开撤销性：因为攻击者本来会在时间段i之后的任何时间，代表群使用A的群签名密钥签署文件，使用其他成员的签名密钥签署的签名应该仍旧保持有效、匿名和无关性。回溯公开撤销性包含公开撤销性，反之不然。后向无关性:在时间段i之前，使用A的群签名密钥产生的签名仍该保持有效，匿名和无关性，因为这些签名是A产生的，而不是攻击者。我们扩展的群签名方案提出支持回溯公开撤销性和后向无关性的前向安全的群签名方案，并且签名长度独立于撤销成员数量。弱前向安全性：假设一组群签名密钥=ki，ti1iL，ki，ti表示成员i在时间段ti的群签名密钥，并且t=min（t1，tL）。我们称（）是的弱跨距（weak-span），（）表示该组群签名密钥ki，wi1iL，twiT。我们认为如果攻击者给定一组群签名密钥不能产生一个在（）中正确的群签名密钥，那么群签名方案满足弱前向安全性。强前向安全性：给定一组群签名密钥=ki，ti1iL，ki，ti表示成员i在时间段ti的群签名密钥，我们称（）是的跨度（span），（）代表该组群签名ki，wi1uL，tiwiT。然后，如果攻击者给定一组群签名密钥，不能产生一个在（）里的正确的群签名，我们说，该群签名方案满足强前向安全性。时限的成员身份：GM能限制一个成员的群成员身份通过签发给他群成员密钥，该密钥只能在某些时间段产生正确的群签名。回溯公开撤销性：在时间段i，GM能从时间段j开始撤销一个群签名密钥，使得任何使用这个群签名密钥在时间段j之后产生的签名变得无效。而且，所有在时间段j之前使用这个群签名密钥产生的签名应该对任何除了GM的人仍保持匿名性和无关性。3. 预备知识我们的方案依靠强RSA假设和DDH假设。让n=pq成为RSA-Like模数并让G成为Zn*的循环子群。SRSA假设是：给定n和zG，难以找到vG和eZ1，使得zve（mod n）。DDH假设是：给定g，gx，gy和gz，难以确定gxygz（是否相等）。我们使用现有的零知识证明协议作为我们方案里的building blocks。这些零知识证明协议可以使用一个理想的哈希函数（也成为Fiat-Shamir启发式算法）实现。并且我们提到由此生成的知识签名。因为篇幅限制，我们不回顾这些协议的细节。我们使用PK来表示谢意是一个知识签名协议，希腊字母来表示被证明的秘密知识，所有其他的参数对于示证者（还没有成为群成员的用户）和验证方。离散对数的知识签名：让G=表示阶为q的一群素数，且yG。我们使用PK()：y=g（m）来表示在群G里，loggy的知识签名。这个协议由29,15设计并在辅助字符串模型指出零知识19。在QRn中的离散对数的知识签名：让n=pq，p=2p+1，q=2q+1，并且p、q、p和q都是素数。G是QRn的生成元，并且yQRn。我们使用PK（）：y=g（m）表示在群QRn中loggy的知识签名。一般的，示证者不容易证明y是一个二次剩余。所以我们使用协议PK（）：y2=(g2)代替，因为logg2y2=loggy,假如y是二次剩余。知识签名的表示法：让PK（1，v）：y=g11gvv（m）表示一个元素yG关于根（bases） g1，gvG的知识签名的表示法。离散对数相等性知识签名：PK（）：y1=gy2=h（m）表示对于根（bases）gG和hG，两个群元素y1，y2G的离散对数相等性的知识签名。知识签名的范围：PK（）：y=ga，b（m）表示yG关于gG离散对数的知识签名，使得loggy映射（lies）进整数区间a，b。如果示证者没有被提供分解的模数，这个协议能在SRSA假设下有效的完成。4.1 方案ISetup 步骤:GM选择两个 （ln/2）-bit 素数p=2p+1和q=2q+1，p和q也是素数。让n：=pq。GM也随机选择元素a，d，g，g1RQRn，一个秘密数(元素)xRZpq*,并使y：=gx mod n。它存储(p, q, x)作为他的密钥并且公开(n, a, d, g, g1, y)作为群公钥。GM同时也在群公钥是正确的时候分割时间成T个时间段，并让时间间隔公开。本文的剩余部分，我们使用下面概念。让和表示整数区间：=（-2l，2l），=（2l，2l+1），lT+l+2.直观.方案的直观如下：当用户U加入群，他和GM一起随机选择xuR，使得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，他首先选择r1R0，12ln，计算A=cu，jyr1,B=gr1，并且产生：一个验证方简单的检查以上知识签名的正确性。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间的文件，给定ij。两链的费用是不多的，也就是签名长度少于一个单链签名长度的两倍。4.4 撤销我们拓展方案I来支持具有后向无关的追溯的撤销。让h成为一个序列n循环群的生成元，DDH问题是困难的。当群成员U在i使用它的群签名密钥(cu,j, eu, xu)签署消息，除了基本的Sign步骤外，U也作如下：他随机性选择rZn并计算g2=hr，C=g2cu，j，并显示（reveals）（g2，C），我们称他为撤销token。U通过知识签名证明g2和C是正确的构成。当用户V从时间段i开始被从群剔除时，cv，i和i将被显示在撤销列表中。假设验证方有时间段j的签名，ji并且撤销token在签名中是（g2，C）。为了看是否签名密钥已经被剔除，验证方简单地计算cv,j并检查是否。如果他们相等，意思是签名被撤销。更细一步，对于U在j签署消息m，协议将如下：第一个协议PK是与我们原来的前向安全性群签名方案相同的。第二个PK2是一个新的零知识证明协议，我们在附录B构建并解释其细节。这个方案清楚的支持公共地撤销群成员资格。然而，后向无关性依靠一个新的加密假设，我们叫做log-square假设：n是两个安全素数产生的，如方案I。G是一个序列n的循环群，DDH问题是困难的，并且g2是G的生成元。给定随机的vRQRn，并且w=g2uRG，对攻击者，在没有知道n的情况下决定v=u2 mod n是很难的。在这个假设下，很容易看出我们的方案支持后向无关性。密码学假设减少到不是因子分解就是离散对数问题。我们猜测这个问题是难以解决的，尽管研究这个问题仍需要完成很多研究。5. 前向安全群签名IISetup 步骤:Setup步骤几乎与方案I一样。除了方案I的Setup之外，让i表示整数间隔。GM也详述一个确定性单向方法使得给定一个随机的素数eu，ii，一个可以产生一序列素数eu，i，eu，T，eu，jj，for ijT。给定只有eu，i对于某个ijT，后向计算是很难的，也就是eu，k，for kj。直观.这个前向安全群签名与方案I的在section 4是相似的，除了它使用不同的单向函数来evolve群签名密钥。当用户U加入群，与方案I相似，他和GM一起随机选择xu使得U知道xu并且GM只知道。GM之后随机选择一个素数eu，0i，0iT。Join步骤:加入步骤与方案I相似出咯额第三步。在第三步，GM随机地选择一个素数eu，00，然后产生一个序列的素数eu，ii，0iT。Evolve步骤:Sign和Verify步骤:假设U在j有群签名密钥(cu,j, eu,j, xu)。为了在j签署消息m，他首先选择r1R0,12ln, 一个验证方简单的检查上面知识签名的正确性。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步骤，他也做下面的：随机产生一个元素g3QRn并展示g3和，并用零知识证明D是正确构成的。我们叫（g3，D）签名的撤销token。更细一点Sign步骤如下：现在如果GM想从时间段i撤销U的签名，他简单地显示eu，i和i。如果用户V在ji获得签名并且签名的撤销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 t1it2并且之后能检查是否签名被撤销。6. 讨论我们的两个安全群签名方案都是基于3提出的群签名方案并且使用单向函数用作演变群签名密钥来实现前向安全性。这两个方案有不同的性能和安全权衡策略。方案I由有效的Evolve步骤（仅仅需要一个平方），尽管签名和验证效率较低（需要O（T）平方）。方案II由高效的签名和验证步骤并且没有额外的管理费用相比3中的非前向安全群签名方案。但是方案II在Evolve步骤中效率很低（需要O（T）exponentiations 取幂），尽管相似的技术在24能被用来减少开销with 存储空间权衡。方案II也能比方案I实现更灵活的时限的群成员身份。方案II支持强