环签名

环签名概述

环签名(ring signature)是一种数字签名方案，最初由Rivest等人提出，环签名可以看成一种简化的群签名, 环签名中只有环成员没有管理者, 不需要环成员间的合作。【在群签名中需要事先生成一个群，随后用户才能加入该群，从而代表该群进行签名】

环签名的定义

假定有 n 个用户，每一个用户拥有一个公钥和与之对应的私钥。环签名是一个能够实现签名者无条件匿名的签名方案，它主要由下述算法组成：

Gen：概率多项式时间(PPT)算法，输入安全参数 k 后输出公私钥对。这里假定Gen为每个用户产生一个公私钥对，并且不同用户的公私钥可能来自不同的公钥体制，如RSA或者DL。

Sign：一个PPT算法，在输入消息 m 和 n 个环成员的公钥 L={y1 , ⋯ , yn}以及其中一个成员的私钥 xs 后，对消息 m 产生一个签名 R，其中 R 中的某个参数根据一定的规则呈环状。

Verify：一个确定性算法，在输入(m,R)后，若 R 为m 的环签名则算法输出“True”，否则算法输出“False”。

环签名因为其签名隐含的某个参数按照一定的规则组成环状而得名。而在之后提出的许多方案中不要求签名的构成结构成环形，只要签名的形成满足自发性、匿名性和群特性，也称之为环签名。

环签名的性质：

正确性：如果按照正确的签名步骤对消息进行签名，并且在传播过程中签名没被篡改，那么环签名满足签名验证等式。

无条件匿名性：攻击者即使非法获取了所有可能签名者的私钥，他能确定出真正的签名者的概率不超过1/n这里n为所有可能签名者的个数。

不可伪造性：外部攻击在不知道任何成员私钥的情况下，即使能从一个产生环签名的随机预言者那里得到任何消息m的签名，他成功伪造一个合法签名的概率也是可以忽略的。

环签名与群签名的比较：

相同点：

都实现了匿名性。

在群签名中，签名者代表这个群进行签名，任何人都可以使用群公钥对这个签名进行验证。在验证过程中，验证者只知道签名者来自这个群，但是不知道签名者是群中的哪一个成员。

在环签名中，签名者代表这个环进行签名，任何人都可以对这个环签名进行验证，在验证过程中，验证者只知道签名者来自这个环，但是不知道签名者具体是环中的哪一个成员。

不同点：

匿名性不同：

群签名实现了有条件的隐私保护，群管理员可以从群签名中找出签名者的真实身份。

环签名是无条件的匿名性。没有任何人可以去除环签名的匿名性。

创建签名的难度方法不同：

用户想要代表某个群对某个消息进行签名，必须由群管理员完成群的【创建】，然后用户【加入】该群后才能进行。

环签名中，用户可以将自己的身份添加到他选择的任何其他用户集合中，并在这个集合上生成一个环签名，该签名只显示出签名者属于该集合，而不暴露其他信息。特别是，未签名的成员甚至可能完全不知道他们参与了这样的签名。 ○ 签名长度不同： ■ 群签名的长度很多都是固定的，与群成员的个数无关 ■ 环签名中，大多数的环签名方案中，签名的长度随环成员个数的增加而增加。

环签名方案

基于RSA的环签名方案【历史上第一个环签名方案】

假设环签名中有n个人，则一个真实用户的签名泄露自己身份的概率是 $1 / n$ ，为了简单起见，下面令n = 5 来举例说明RSA环签名方案。假设有5个用户，分别为1,2,3,4,5，且用户3要对消息m进行签名，则：

密钥生成Gen

为五个用户分别生成RSA公私钥对【（ $e_i,n_i$ ）,（ $d_i,n_i$ ）】。（ i = 1,2,3,4,5 ）

签名Sign

签名需要用到一个对称加密算法，这里使用AES算法。环签名的计算过程如下：

为了简化上述过程，不妨设有一个操作 $R_i(c_i)$ 定义为： $R_i(c_i)$ = $c_{i+1}$ ，其中 $x_i$ 为随机数。则RSA环签名计算过程如下：

$y_i=RSA\_Enc_{pk_i}(x_i)=x_i^{e_i}\ mod \ n_i$

$z_{i+1}=c_i \oplus y_i $

$c_{i+1}=AES\_Enc_{key}(z_{i+1})$

为了展示计算过程，上述操作表示为： $R_i(c_i)=c_{i+1}$ - - - - - 【 $x_i,y_i,z_{i+1},c_{i+1}$ 】通过上述符号假设，上述的计算过程可以简化为：签名者【用户3】选择随机数 $c_4$ ，然后依次计算：

R_4(c_4)=c_5 \text{ ----【} x_4, y_4, z_{5}, c_{5} \text{】}

R_5(c_5)=c_1 \text{ ----【} x_5, y_5, z_{1}, c_{1} \text{】}

R_1(c_1)=c_2 \text{ ----【} x_1, y_1, z_{2}, c_{2} \text{】}

R_2(c_2)=c_3 \text{ ----【} x_2, y_2, z_{3}, c_{3} \text{】}

R_3(c_3)'=c_4' \text{ ----【} x_3', y_3', z_{4}', c_{4}' \text{】}

分析

上面计算的 $R_3(c_3)'$ =\text{【} $x_3', y_3', z_{4}', c_{4}'$ \text{】}中， $c_4'$ 满足 $c_4'=c_4$ 的概率可以忽略不计，因为上述等式成立的概率仅为为 $1/2^{256}$ （因为AES加密的输出是256比特）

为了使其相等，令 $c_4'=c_4$ ，反向计算出 $z_4$ , 然后异或计算出 $y_3$ ，随后【用户3】可以使用自己的私钥（ $d_3, n_3$ ）解密 $y_3$ 得到 $x_3$ ；

将 $R_3(c_3)'=c_4'$ ----\text{【} $x_3', y_3', z_{4}', c_{4}'$ \text{】}替换为 $R_3(c_3)=c_4$ ----\text{【} $x_3, y_3, z_{4}, c_{4}$ \text{】}; 这样即可得到环签名 $σ=\{(e_1, n_1), (e_2, n_2), (e_3, n_3), (e_4, n_4), (e_5, n_5), c_1, x_1, x_2, x_3, x_4, x_5\}$ 。