A Survey on Ring Signature

| 分类 论文笔记  | 标签 门罗币  环签名 

0x00 写在前面

研究门罗币有段时间了,之前对其中的基本技术做了一些简单的介绍,今天来对其中的环签名做详细的解释,包括起源、发展和最新的进展,算是一个详细的科普文。环签名,区别于一般签名机制的是它选取了一堆其他人的公钥来对原始签名者的身份进行隐藏,使得验证者验证签名后可以确定是一堆公钥中某一个人产生的,但无法确定具体签名的人的身份。

0x01 How to Leak a Secret

这可以算是现在环签名思想上一篇元老级的论文了,发表于2001年的ASIACRYPT。其实在这之前也有类似的签名出现,例如1991年EUROCRYPT上的一篇《Group Signature》,但是这个Group signature却包含一个Group manager,签名者必须信赖这个manager,因为只有这个manager可以追溯签名者的身份,同时这也就造成了信任的问题,如果manager被攻击或者它本身就是恶意的,那么这个签名也就变得毫无意义。所以最新的环签名机制几乎全部抛弃了这个中心化的manager机制,为了和原来进行区别现在的环签名前面全部加上了Spontaneous(自发的,也就是不需要中心机构管理)这个词。

为了给这篇文章一个良好的动机,作者Ronald L. Rivest还给我们编造了一个优美的无中生有的情景故事:假设Bob是某个Lower Keyptonia(没有翻译器能翻译出的某国家名字)的一位内阁大臣,某天他偶然撞见发现首相做了某些不可描述的事并准备叛逃,为了国家的安全着想,他打算将这个消息告诉记者,但是又不想记者知道是他泄的密,防止被灭口,但同时由于消息太过于震惊毕竟涉及到国家的命运,记者也必须要确定这消息是某位位高权重的人透露出来的。由于这双方面的要求,Bob就无法使用一般的签名(假设那个时候电子数字签名已经普及世界),此时一个很好的方式就是本文提出的环签名技术。

0x0101 陷门置换(Trapdoor permutation)

陷门置换就是一类具有某种功能的函数,这类函数正向计算很容易,但是在不知道密钥的情况下求逆的概率可以忽略。例如RSA就是一种陷门置换,假设有公钥$Pk=(n,e1)$和私钥$Sk=(n,e2)$,在已知公钥的情况下,任何人都可以从明文A计算密文B,$B=A^{e1} mod \text{ }n$,但是如果不知道私钥,从B计算出A的概率是可以忽略的;而如果知道私钥,那么就可以计算$A=B^{e2} mod \text{ }n$,是很容易的。

在后文中,我们用$g(x)=x^{e} mod\text{ }n$来表示正向计算,$g^{-1}(x)$来表示求逆。

0x0102 组合函数

这个组合函数可谓是整个环签名的精华所在,这个函数输入一个密钥$k$,一个初始值$v$,以及一系列随机数$y_1,y_2,…,y_n$,对于每一个参数都使用一个子过程$E_k$,在本文中这个子过程就是一个对称加密函数,最终输出一个值$z \in \lbrace0,1\rbrace^b$。作者构造的一个函数是这样的:

实际使用的时候令$C_{k,v}(y_1,y_2,…,y_n) = v$,也就是令初始值和结果相等,这样就相当于将等式构成了一个环,再缺少其中任何一项时都可以用其他项算出缺少的那一项,这也就是环签名的关键所在:随机选择若干项($x_1,…x_n$, 除了$x_s$)构建一个等式,然后通过等式算出真正签名者应该对应的那一项($x_s$),随机选择的项就混淆了签名者实际对应的项,而验证者通过验证那个构造的方程,便可以确定签名者必然是若干项($x_1,…,x_n,包括x_s$)中的一个。

0x0103 签名

假设Alice要对消息$m$进行签名,签名者随机选择一个公钥集合$P_1,P_2,…,P_n$作为混淆公钥,其中Alice自己的公钥对应的下标为$s$,私钥也就为$S_s$,Alice按照如下方式来产生最终的环签名:

  1. 首先计算一个对称密钥$k=H(m)$;
  2. 然后随机选择一个$v\in\lbrace0,1\rbrace^b$;
  3. 接着为所有公钥选择一个随机$x_i \in \lbrace0,1\rbrace^b ,1\le i \le n, i \ne s$,然后计算$y_i=g_i(x_i)$;
  4. 然后Alice通过下面的方程解出$y_s$:
  5. Alice通过自己的私钥使用陷门置换用$y_s$算出对应的$x_s$,
  6. 输出最终的环签名,

0x0104 签名验证

验证者收到对于消息$m$的签名$(x_1,x_2,…,x_n,v)$后,按照如下步骤来进行验证:

  1. 对于所有的$i=1,2,…,r$,计算
  2. 计算对称密钥,
  3. 验证环签名方程$C_{k,v}(y_1,y_2,…,y_n) = v$是否成立,是则接受,否则拒绝签名。

0x0105 小结

从上述签名过程可以看出,环签名的思想主要就是一个可以循环计算的函数,缺少其中一项都能用其它已知项计算出来,而应用的时候需要计算的就是签名者真正对应的那一项,然后就是用随机选择的项进行混淆,从而达到隐藏签名者身份发目的。

0x02 Linkable Spontaneous Anonymous Group Signature (LSAG) for Ad Hoc Groups

相对于上一篇的环签名技术,本篇文章最大的不同就是添加了一个新的属性:Linkability,也就是通过两个不同的签名可以判断它们是否由同一个人产生的。

0x0201 签名

给定一个消息$m$,一个公钥集合$L = \lbrace y_1,y_2,…,y_n \rbrace$,私钥$x_s$和对应的公钥$y_s,1 \le s \le n$,签名者按照如下方式产生最终的签名:

  1. 计算$h = H_2(L)和\widetilde{y} = h^{x_s}$;
  2. 随机选一个$u \in \mathbb{Z_q}$,然后计算$c_{s+1} = H_1(L,\widetilde{y},m,g^u,h^u)$;
  3. 对于所有的$i = s+1,…,n,1,…,s_1$,随机选择$s_i \in \mathbb{Z_q}$,然后计算$c_{i+1}=H1(L,\widetilde{y},m,g^{s_i}y^{c_i},h^{s_i}\widetilde{y}^{c_i}), c_1 = c_{n+1}$;
  4. 最后计算$s_s = u - x_sc_s$。

最后的签名为

0x0202 签名验证

  1. 首先计算$h = H_2(L)$,对于所有的$i=1,…,n,$计算,然后计算
  2. 验证,如果是则接受,否则拒绝签名。
  3. 对于两个不同的签名,通过比较$\widetilde{y}$是否相同来判断是否是由同一个人产生的签名。

0x0203 小结

这个签名相对于之前的机制优点是增加了linkability属性,也就是避免了同一个签名者使用同一组公钥多次进行签名,但是如果一组公钥每次都是重新随机选择,那么这个属性的价值也就变得微乎其微,因为选到同一组公钥的概率是指数次函数,当然作者提出这个新的属性自然有其应用领域,比如作者提出的电子投票系统。到如今Monero中同样引用了这样一个性质,这是作者万万没有想到的。

但是新的机制同样也有自己的缺点,首先是计算的复杂度明显增加了,多了很多次哈希运算;还有就是签名的长度也略有增长。

0x03 Linkable Ring Signature: Security Models and New Schemes

从这一篇开始后面所有的环签名相关的论文都是基于零知识证明,本篇的作者和前一篇是同一个人,时间上比前一篇晚一年,如题所说,最大的改变就是基于不同的安全模型。

给定一个消息$m$,一个公钥集合$L = \lbrace y_1,y_2,…,y_n \rbrace$,私钥$x_s$和对应的公钥$y_s,1 \le s \le n$,签名者按照如下方式产生最终的签名:

  1. 计算$h = H_2(L),y_0 = h^{x_s}$;
  2. 通过下面的方程解出$c_s$,其中对于所有的
  3. 计算$s_s = r - c_sx_s$。

最后的签名为$\sigma = (y_0,c_1,…,c_n,s_1,…,s_n)$。

验证就看第二步中的等式是否成立,是则接受,否则拒绝签名。另外通过$y_0$来判断linkability。

0x04 Traceable Ring Signature

这篇文章的签名又添加了一个新的属性:Traceable,即如果签名者使用同一个公钥集合对两个不同的消息进行签名,那么验证者就可以追查出签名者的身份。个人认为这个新加的属性看上去有点无用,环签名的本身就是要保证无法追踪签名者的身份,而这里还特意增加一个限制,使得可以追踪签名者的身份,不过既然提出来了,自然有其应用的领域。

文章的签名部分和0x03中几乎一样,所以就不再重复写了,额外添加的就是为保证traceable的几个步骤:

  1. 计算$h=H(L)和\sigma_s = h^{x_s}$;
  2. 令$A_0 = H’(L,m),A_1=(\frac{\sigma_s}{A_0})^{1/s}$;
  3. 对于所有的$j \ne s$,计算$\sigma_j=A_0A_1^j \in G$,其中$A_1$放入签名中。

然后比较两个签名的时候分别通过$\sigma_j=A_0A_1^j$算出所有对应的$\sigma_j$,假设分别为$\sigma,\sigma’$;接着对于所有的$i$,如果$\sigma_i = \sigma_i’$,那么就存下对应的公钥。最后,如果公钥个数为1,那么就是签名者的公钥;如果公钥为原始公钥集合,那么说明这两个签名是由同一个人产生的;其它情况则无法判断。

当签名者对两个相同的消息签名时,产生的$\sigma$自然是全部一样的,所以对应的结果就是最初的公钥集合;当签名者对两个不同的消息签名时,只有$\sigma_s$是一样的,结果也就是签名者对应的公钥,所以可以确定身份;其他情况包括结果为空集,或者个数大于1但小于集合大小,这就无法确定。

0x05 CryptoNote

这也是最新的环签名的应用领域之一,传送门请转门罗币基础技术介绍

0x06 Ring Confidential Transactions

这个签名是门罗币最新的应用,相比于CryptoNote,增加了哈希的次数,但是减少了一半签名的长度,对于数字货币来说,这无疑就提升了很大的竞争力,因为签名的缩短不仅减轻了网络负载,同样还减小了交易的大小,对于按字节数来进行计算交易费的机制来说,也就减小了每笔交易的交易费。

首先签名者随机选择一个公钥集合$P_i,i=0,1,…,n$,其中签名者的下标为$j$,对应的公钥为$P_j=x_jG$,然后计算一个密钥镜像$I=x_jH_p(P_j)$,这个镜像用来判断双花。签名者按如下步骤产生最终的签名:

  1. 随机选择$\alpha,s_i \in \mathbb{Z_q}, i \in \lbrace 1,…,n \rbrace,i \ne j,$;
  2. 计算
  3. 循环计算
  1. 上面一步就算出了所有的$c_i$,最后计算$s_j = \alpha - c_jx_j$;

最后的签名就是$\sigma = (I,c_1,s_1,…,s_n)$。

验证过程就是算出所有的$L,R,c$,然后判断$c_{n+1} = c_1$,是则接受,否则拒绝,接受的前提是$I$之前没有出现过。

相比于门罗币改进之前的版本,我们可以发现将原来随机选择的$c$用哈希来进行替代,从而减少了最终签名的长度,从结果上看这似乎很显而易见。那么我们能否用同样的原理将$s$也减少一半呢,这是个值得思考的问题。

参考文献

  • Ronald L.Rivest 《How to Leak a Secret》
  • Joseph K.Liu 《Linkable Spontaneous Anonymous Group Signature (LSAG) for Ad Hoc Groups》
  • Joseph K.Liu 《Linkable Ring Signature: Security Models and New Schemes》
  • E.Fujisaki and K.Suzuki 《Traceable Ring Signature》

上一篇     下一篇