基于身份的常数级环签名

| 分类 论文笔记  | 标签 环签名  身份基签名 

0x00 写在前面

没错,又是一期的环签名,其实最近一直都在研究环签名的改进方向,论文看到现在,发现环签名或者说所有的签名机制的改进也无外乎这几个方面:时间效率(计算复杂度),签名长度(空间效率),安全性(证明方法,Random Oracle等)以及附加属性(Traceable,Linkable等等)。此外还有就是应用领域,这个就不能算是签名的改进了,但是能找到一个新的应用领域也是非常不错的。这次就从签名长度上来看,门罗币中的环签名长度是2*n,n是环中公钥的个数,后来改进成了n,这也几乎是所有现在环签名的空间效率了,但是在一个特殊的领域——基于身份加密中效率却可以达到常数级,其中所使用的方法也是十分的有趣。

0x01 准备知识

0x0101 基于身份加密(Identity-Based Encryption)

基于身份的加密和传统的公钥加密最大的不同就是用户的身份(id,例如邮箱或者用户名等)就是公钥(或者通过id来产生公钥),从而免除了公钥认证系统,但是同时也增加了一个可信的第三方密钥生成器(Private Key Generator, PKG),所有的用户都要通过这个PKG来成对应的公私钥,从而进行加密解密。基于身份的加密最开始是由Adi Shamir在《 Identity-Based Cryptosystems and Signature Schemes》中提出来的,一般而言基于身份的加密总共分为以下几个步骤:

  1. PKG首先公布一个Master public key,自己保留对应的Master private key(也直接称为master key)。
  2. 任何用户都可以使用Master public key和对应的id产生加密的公钥。
  3. 而产生签名的私钥,则需要用户使用自己的id向PKG进行身份认证,认证通过后PKG就使用Master private key和id来产生签名的私钥。

在实际的论文中,一般分为以下几个部分来进行描述:

  1. Setup($l$):PKG接收一个安全参数$l$,产生master private key和master public key以及其它的一些公开参数。
  2. KeyGen($id$)或者Extract($id$):这个是由用户请求产生私钥时PKG运行的,这个过程需要首先认证用户的身份,并且消息传输的安全性不由这个协议来保证。
  3. Encrypt或者Sign:用户使用从PKG得到的私钥进行加密或者签名操作。
  4. Decrypt或者Verify:其它用户通过从PKG获取master public key结合用户的id计算出加密者的公钥,从而对消息进行解密或者验证签名。

整个过程都需要用户对PKG的信任,这也就使得PKG成为了攻击者的首要目标,但同时也减少了公钥的认证与分发过程。

0x0102 双线性对

本节主要介绍一下双线性对的一些主要性质,而不深究其具体实现的原理。假设$G_1$是一个阶为质数$q$的加法循环群,$G_2$是阶同样为$q$的乘法群,如果映射$e:G_1$x$G_1 \to G_2$满足以下性质:

  • Bilinearlity(双线性):对于所有的$P,Q \in G_1,a,b \in Z_p^*$,满足$e(aP,bQ) = e(P, Q)^{ab}$。
  • Non-degeneracy(非退化性):存在一组$P,Q \in G_1$使得$e(P,Q) \neq 1$。
  • Computability(可计算性):存在一个有效(多项式级)的算法能快速计算$e(P,Q)$。

那么我们就称$e$是一个双线性映射,其中的每一个元素都是双线性对。

0x0103 Accumulator

看上去这是一个比较新的概念,但其实它的原理很简单,先讲一下它的完整定义,你会发现几乎所有的论文对它的定义都一模一样,然后举个例子就明白了。所谓Accumulator就是一个多元组$(\lbrace X_l,F_l \rbrace), l \in N$,其中$\lbrace X_l \rbrace$是Accumulator的定义域,$\lbrace F_l \rbrace$是一个函数对族,其中的每一个函数对$(f,g) \in F_l$定义为$f:U_f $ x $X_f \to U_f$并且$g:U_f \to U_g$是一个双射函数,此外还满足以下性质:

  • Efficient Generation:存在一个高效的算法输入一个安全参数,输出一个随机元素$(f,g) \in F_l$,可能还会输出一些辅助信息$a_f$
  • Quasi commutativity(半交换性):对于所有的$l \in N,(f,g) \in F_l,u \in U_f,x_1,x_2 \in X_l$都有$f(f(u,x_1),x_2) = f(f(u,x_2),x_1)$。对于所有的$l \in N,(f,g) \in F_l$和$X=\lbrace x_1, …, x_q \rbrace$,我们称$g(f(f(u,x_1),…,x_q))$为集合$X$在$u$上的累积值,由于半交换性的存在,累积值独立于所有的$x_i$,我们记为$f(u,X)$。
  • Efficient evaluation:存在一个多项式级别的算法能够计算$g(f(u,X))$,即使在没有辅助信息$a_f$的情况下。

介绍完了定义,可能对于这个Accumulator实际有什么作用还是一头雾水,下面我们来举个例子。假设我们定义$f:(u,x) \to (x+s)u, g:u \to uP$,那么实际$f(u,X) = u(x1+s)…(x_q+s), f(u,X) \in Z_p$,而$g$就将$Z_p$上的$f(u,X)$映射到$G_1$上,在实际的应用中就可以先将一个集合压缩成一个值,然后再将这个值映射到加法循环群中,从而构造双线性对。

0x02 Improved ID-based Ring Signature Scheme with Constant-size Signatures

原本还打算将几篇常数级的环签名全部介绍一下,后来觉得它们其实都一样,所以就介绍一下几篇之中保证同样安全性但效率最高的一篇,懂了这篇其它的也就顺水推舟了。

和之前介绍的ID-based身份加密一样,签名也是分为以下几个部分:

  • Setup:定义一个安全参数$l$,随机选,生成一个accumulator,包括函数,其中是环中用户的个数上界,令,$H_0,H_1$分别是哈希函数,最后公开的参数有,主私钥$mk \gets s$。
  • KeyGen:通过用户的id计算出对应的私钥$s_{id_i} \gets \frac{1}{H_0(id_i) + s}P$, 公钥就直接使用id,用户可以通过验证$e(H_0(id_i)Q + Q_{pub}, s_{id_i}) = e(Q,P)$是否成立来验证生成的私钥是否正确。
  • MakeGPK:给定一个身份集合$R = {id_i}^k_{i=1}$,计算集合$X = {H_0(id_i)}^k_{i=1}$,并且生成群公钥$gpk = V \gets g(f(u,X))$。
  • MakeGSK:每一个用户$id_s \in R, R={id_i}^k_{i=1}$生成自己的群私钥$gsk = (h_{id_s}, s_{id_s},W)$,其中$h_{id_s} \gets H_0(id_s), W \gets g(f(u,X’)), X’ = {H_0(id_i)}^k_{i=1,i \ne s}$。
  • Sign:给定一个消息$m$,一个身份集合$R$,其中签名者的身份$id_s \in R$.
    • 随机选择$r_1, r_2, k_1, k_2, k_3, k_4, k_5 \in _RZ_P^*$。
    • 计算$U_1 = s_{id_s} + r_1P, U_2 \gets W + r_2Q$。
    • 计算$\Pi_1 = e(Q, U_1)^{-k_5} \cdot e(Q,P)^{k_2} \cdot e(Q_{pub}, P)^{k_1}$, $\Pi_2 = e(P, U_2)^{-k_5} \cdot e(P, Q)^{k_4} \cdot e(P_{pub}, Q)^{k_3}$。
    • 计算$c = H_1(m,U_1,U_2,\Pi_1, \Pi_2,R)$。
    • 然后计算$s_1 = k_1 + cr_1, s_2 = k_2 + cr_1h_{id_s}, s_3 = k_3 + cr_2, s_4 = k_4 + cr_2h_{id_s}, s_5 = k_5 + ch_{id_s}$。
    • 最终的签名就是$\sigma = (U_1, U_2, \Pi_1, \Pi_2, s_1, s_2, s_3, s_4, s_5)$
  • Verify:给定一个签名$\sigma$和一个身份集合$R$
    • 计算$c’ = H_1(m,U_1,U_2,\Pi_1, \Pi_2,R)$。
    • 验证$\Pi_1 = e(Q, U_1)^{-s_5} \cdot e(Q,P)^{s_2} \cdot e(Q_{pub}, P)^{s_1} \cdot e(Q_{pub}, U_1)^{-c’} \cdot e(P, Q)^{c’}$, $\Pi_2 = e(P, U_2)^{-s_5} \cdot e(P, Q)^{s_4} \cdot e(P_{pub}, Q)^{s_3} \cdot e(P_{pub}, U_2)^{-c’} \cdot e(P, V)^{c’}$,若成立则接受签名,否则拒绝。

上一篇     下一篇