群签名、环签名、盲签名

群签名方案是算法组ΠGS=(Gen,Sign,Ver,Open)ΠGS=(Gen,Sign,Ver,Open)，Gen(1λ,n)Gen(1λ,n)：密钥生成算法，nnn为群成员数，输出gvkgvkgvk：群公钥，用于验签gmskgmskgmsk：主私钥，由管理员持有，用于追踪成员身份gsk=(gsk[1],⋯,g。

山登绝顶我为峰 3(^v^)3

3768人浏览 · 2022-11-23 22:19:21

山登绝顶我为峰 3(^v^)3 · 2022-11-23 22:19:21 发布

文章目录

群签名
环签名
盲签名

群签名

定义

群签名方案是算法组 $\Pi_{GS}=(Gen, Sign, Ver, Open)$ ，

$Gen(1^\lambda,n)$ ：密钥生成算法， $n$ 为群成员数，输出
- $g v k$ ：群公钥，用于验签
- $g m s k$ ：主私钥，由管理员持有，用于追踪成员身份
- $gsk=(gsk[1],\cdots,gsk[n])$ ：成员私钥，用于签名
$S i g n (g s k [i], m)$ ：签名算法，任意成员可以独立签署消息 $m$ ，输出签名 $\sigma$
$Ver(gvk,m,\sigma)$ ：验签算法，根据验签通过与否，输出 $0 / 1$
$Open(gmsk,m,\sigma)$ ：公开算法，如果签名正确，则输出签名者身份 $i$ ，否则输出 $\perp$

我们说 $\sigma$ 是 $m$ 的正确签名，如果存在 $\in [1,n]$ 以及随机带 $r$ ，使得 $\sigma=Sign(gsk[i],m;r)$ 成立。

安全性

群签名的安全性只需两条：完全匿名性、完全可追踪性。其他奇奇怪怪的安全性要求都可以由这两条推出。

匿名性实验：

在这里插入图片描述

定义敌手的优势为：
$\begin{aligned} Adv_{\Pi,A}^{anon}(\lambda,n) &= 2\left| Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,n,U_1)=1\right] - \frac{1}{2} \right|\\ &= \left| Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,n,1)=1\right] - Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,n,0)=0\right] \right| \end{aligned}$

我们说 $\Pi_{GS}$ 是完全匿名的，如果对于任意 PPT 敌手 $A$ ，优势 $Adv_{\Pi,A}^{anon}(\lambda,n)$ 是可忽略的。

可追踪性实验：

在这里插入图片描述

定义敌手的优势为：
$Adv_{\Pi,A}^{trace}(\lambda,n) = Pr\left[Expt_{\Pi,A}^{trace}(1^\lambda,n)=1\right]$

我们说 $\Pi_{GS}$ 是完全可追踪的，如果对于任意 PPT 敌手 $A$ ，优势 $Adv_{\Pi,A}^{trace}(\lambda,n)$ 是可忽略的。

构造

密码学部件：

一般签名算法 $\Pi_s = (Gen_s, Sign, Ver)$
公钥加密方案 $\Pi_e = (Gen_e, Enc, Dec)$
非交互零知识证明 $(P, V)$

在这里插入图片描述

令 $P_0$ 是组管理员。为了让组内的每个成员都可以签名并验证，可以简单地执行 $n$ 次 $Gen_s$ ，为各个成员生成私钥公钥，将 $\{vk_i\}_{i \in I}$ 作为群公钥。但是这会泄露成员身份。
我们不再公开公钥，而是在签名时附加上一个证明 $\pi$ ，使得验签者相信确实存在一个群成员 $i$ 签署了消息。但这有个问题，就是没有证明 $vk_i$ 是属于这个组的。
让 $P_0$ 再为每个成员的公钥添加上证书 $cert_i$ ，同时要证明 $vk_i$ 确实是组成员的公钥。但是这必须公布 $cert_i$ ，又把成员身份泄露了。
因此我们把证书加密后再发布，签名者对于 $m$ 输出 $(C,\pi)$ ，验签者验证 $\pi$ 确实是对 $m, C$ 之间关系的证明。

环签名

定义

环签名方案是算法组 $\Pi_{RS}=(Gen, Sign, Ver)$ ，

$Gen(1^\lambda)$ ：密钥生成算法，输出 $(s k, v k)$
$S i g n (s k, R, m)$ ：签名算法，验签密钥集合 $R=(vk_i,\cdots,vk_n)$ （环），任何人可以独立签署消息 $m$ ，输出签名 $\sigma$
$Ver(R,m,\sigma)$ ：验签算法，根据验签通过与否，输出 $0 / 1$

若验签通过，那么说明签名是由 $R$ 中的某个 $vk_i$ 对应的 $sk_i$ 所签署的。与群签名相比，环签名是去中心化的，并且参与者的加入退出很容易。缺点是没法追踪恶意的签名者。

安全性

无内部攻击的不可伪造性实验

在这里插入图片描述

内部攻击的不可伪造性实验

在这里插入图片描述

定义敌手的优势为：
$Adv_{\Pi,F}^{EUF-CMA}(\lambda) = Pr\left[ Expt_{\Pi,F}^{euf-corrupt-cma}(1^\lambda)=1 \right]$

我们说 $\Pi_{RS}$ 是**（内部攻击下）不可伪造的**，如果对于任意 PPT 敌手 $F$ ，优势 $Adv_{\Pi,F}^{EUF-CMA}(\lambda)$ 是可忽略的。

基本匿名性实验：

在这里插入图片描述

定义敌手的优势为：
$\begin{aligned} Adv_{\Pi,A}^{anon}(\lambda) &= 2\left| Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,U_1)=1\right] - \frac{1}{2} \right|\\ &= \left| Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,1)=1\right] - Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,0)=0\right] \right| \end{aligned}$

我们说 $\Pi_{GS}$ 是基本匿名的，如果对于任意 PPT 敌手 $A$ ，优势 $Adv_{\Pi,A}^{anon}(\lambda)$ 是可忽略的。

（有内部攻击的）匿名性实验：

在这里插入图片描述

定义敌手的优势为：
$\begin{aligned} Adv_{\Pi,A}^{anon-corrupt}(\lambda) &= 2\left| Pr\left[Expt_{\Pi,A}^{anon-corrupt}(1^\lambda,U_1)=1\right] - \frac{1}{2} \right|\\ &= \left| Pr\left[Expt_{\Pi,A}^{anon-corrupt}(1^\lambda,1)=1\right] - Pr\left[Expt_{\Pi,A}^{anon-corrupt}(1^\lambda,0)=0\right] \right| \end{aligned}$

我们说 $\Pi_{GS}$ 是匿名的，如果对于任意 PPT 敌手 $A$ ，优势 $Adv_{\Pi,A}^{anon-corrupt}(\lambda)$ 是可忽略的。

构造

方法一：类似群签名，使用 NIZKP 将一般签名方案转化为环签名方案。

方法二：真的构成一个环 [RST01]，使用 trapdoor OWP 群成员可以在环的某个位置上打开环，然后再关闭环。

设 ${H_s\}$ 是 CRHF， ${F_k,F_k^{-1}\}$ 是 trapdoor OWP，对应的公私钥为 $(p k, s k)$ ， $\Pi=(Gen, Enc, Dec)$ 是对称加密算法，签名算法如下：

选取 $(pk_1,\cdots,pk_n)$ ，包含自己的公钥 $pk_j$
计算 $r=H_s(m)$ ，生成 $\leftarrow Gen(1^\lambda;r)$
随机选取 $x_1,\cdots,x_{j-1},x_{j+1},\cdots,x_n$ ，计算 $y_i = F(pk_i, x_i), j \neq i$
随机选取 $t_j'=v$ ，计算 $t_{j+1}=Enc(k,t_j')$ ，然后依次计算 $t_{i+1} = Enc(k, t_i \oplus y_i), i=j+1,\cdots,n,1,\cdots,j-1$ （令 $\equiv 1$ ）得到 $t_j$ ，接着求逆 $x_j = F^{-1}(sk_j, t_j \oplus t_j')$
输出 $t_n, x_1, \cdots, x_n)$ 作为消息 $m$ 的签名。

盲签名

定义

盲签名方案是算法组 $\Pi_{BS}=(Gen, <S,U>, Ver)$ ，其中 $< S, U >$ 是签名者和用户之间的交互协议，

$Gen(1^\lambda)$ ：密钥生成算法，输出 $(s k, v k)$
$< S (s k), U (v k, m) >$ ：签名交互协议，签名者输出 $O u t = O K / F a i l$ （签名是否成功），用户输出 $m$ 的签名值 $\sigma$
$Ver(vk,m,\sigma)$ ：验签算法，根据验签通过与否，输出 $0 / 1$

安全性

不可伪造性实验：因为挑战者 $C h$ 看不到 $m$ ，因此不能像一般签名算法那样设置一个签名历史记录 $Q_s$ 使得 $m^* \not\in Q_s$ ，而是需要敌手 $F$ 询问 $k$ 次签名后，应当输出至少 $k + 1$ 个不同消息的合法签名。

在这里插入图片描述

定义敌手的优势为：
$Adv_{\Pi,F}^{EUF-CMA}(\lambda) = Pr\left[ Expt_{\Pi,F}^{euf-cma}(1^\lambda)=1 \right]$

我们说 $\Pi_{BS}$ 是**（内部攻击下）不可伪造的**，如果对于任意 PPT 敌手 $F$ ，优势 $Adv_{\Pi,F}^{EUF-CMA}(\lambda)$ 是可忽略的。

盲签实验：

在这里插入图片描述

定义敌手的优势为：
$\begin{aligned} Adv_{\Pi,A}^{blind}(\lambda) &= 2\left| Pr\left[Expt_{\Pi,A}^{blind}(1^\lambda,U_1)=1\right] - \frac{1}{2} \right|\\ &= \left| Pr\left[Expt_{\Pi,A}^{blind}(1^\lambda,1)=1\right] - Pr\left[Expt_{\Pi,A}^{blind}(1^\lambda,0)=0\right] \right| \end{aligned}$

我们说 $\Pi_{BS}$ 是盲的，如果对于任意 PPT 敌手 $A$ ，优势 $Adv_{\Pi,A}^{blind}(\lambda)$ 是可忽略的。

构造

密码学部件：

一般签名算法 $\Pi_s = (Gen_s, Sign, Ver)$
公钥加密方案 $\Pi_e = (Gen_e, Enc, Dec)$
非交互零知识证明 $(P, V)$
非交互承诺方案 $\Pi_c = (Com,Open)$

盲签名的密钥生成算法 $Gen(1^\lambda)$ 为：

获得公共随机串 $CRS_{ZK}$ 和 $CRS_{Com}$
执行 $(pk_s,sk_e) \leftarrow Gen_e(1^\lambda)$ 和 $Gen_s(1^\lambda)$
输出公钥 $vk_{BS} = (CRS_{ZK},CRS_{Com},pk_e,vk)$ ，私钥 $sk_{BS} =(CRS_{ZK},CRS_{Com},sk_e,sk)$

盲签协议（Blind-signing protocol） $< S, U >$ 构造如下：

在这里插入图片描述

验签算法 $Ver(vk_{BS},m,(C_\sigma,\pi))$ 为：

设置 $(C_\sigma,pk_e,CRS_{Com},vk,m)$
输出 $V(CRS_{ZK},x,\pi)$

其中，NIZKP $< P, V >$ 所证明的关系为：
$R_L(x,w)=1 \iff \begin{aligned} &x = (C_\sigma,pk_e,CRS_{Com},vk,m)\\ &w = (u,v,\sigma,C)\\ &\textbf{1) }C = Com(CRS_{Com},m;u)\\ &\textbf{2) }1 = Ver(vk,C,\sigma)\\ &\textbf{3) }C_\sigma = Enc(pk_e,C\|\sigma;v)\\ \end{aligned}$