环签名方案

请注意，本文编写于 820 天前，最后修改于 544 天前，其中某些信息可能已经过时。

Abstract

形式化了环签名的概念，可以指定一组可能的签名者且不揭示是几千名的成员

与群签名不同，环签名没有群管理员，没有设置和撤销过程，没有协调，任何用户都可以选择包括自己在内的任何一组可能的签名者，并使用其密钥和其他人的公钥对任何消息进行签名且无需获得他们的批准或协助

环签名以匿名的方式泄露权威机密，只能由预期收件人验证的方式签署临时电子邮件，并解决多方安全计算中的其他问题

本文主要贡献是，此类签名是无条件模糊签名者的，在RO模型下是可证明安全的，且非常搞笑，添加环成员会增加单个模乘法和对称加密进行签名或验证的成本

1 Introduction

群签名方案的一般概念是由Chaum和van Heyst于1991年提出的$[2]$，该方案中可信群管理器预定义某些用户组，并向其成员分发特殊密钥，这些成员可以用这些密钥代表其组对消息进行匿名签名，不同群成员生成的签名对其验证者而言是无法区分的，但对可以撤销恶意签名的群管理者来说是可区分的

本文形式化了环签名方案的相关概念，这些都是简化的群签名方案，只有用户没有管理者（因为环是均匀边缘无中心的），群签名在成员希望合作时才有效，而环签名在成员不希望合作时仍然有效

群签名和环签名都是签名者模糊的，但是环签名中没有预先安排的用户群，没有设置、更改或删除群的过程，没有分发专用密钥和撤销实际签名者的匿名性（除非该签名者决定公开自己）

本文唯一假设是每个成员都已经有标准签名方案的公钥，为了产生环签名，实际签名者声明一组包含他自己的任意可能的签名人，并仅是用他自己的私钥和其他人的公钥完成签名计算

Chaum等人$[2]$的方案三和方案四，以及Camenisch论文$[1]$定义2中和定义中的两个签名方案可以视为环签名方案，然而，前一种方案需要对每个签名进行零知识证明，后一种方案需要与环中成员数量相同的模幂

Cramer等人$[3]$展示了如何生成证人无法区分的交互证明，这种证明可以与Fiat-Shamir技术相结合，生成环签名方案，类似地，DeSantis等人$[10]$证明了随机自约语言的交互式SZK在单调布尔运算下是闭合的，并证明了该结果对构造环签名方案的适用性（尽管他们没有使用该术语）

本文提出的环签名的直接构造基于一种完全不同的思想，对于大型环特别有效（每个环成员仅添加一个模乘和一个对称加密来生成和验证此类签名），在随机预言模型中，生成的签名是无条件的签名者模糊的，并且是可证明安全的

2 Definitions and Applications

2.1 Ring Signatures

称一组可能的签名者为一个环，其中真正签名的那个人称为signer，不签名的人称为non-signer

假设每个可能的签名者（通过PKI目录或证书）与公钥$P_k$相关联，公钥定义了其签名方案并指定了验证密钥，验证密钥以$S_k$表示

环签名方案不需要单独签名方案的任何特殊属性，但是本文最简单的构造假设他们都是基于单向陷门置换的RSA来生成和验证签名

环签名由两个过程定义

$ring-sign(m,P_1,P_,...,P_r,s,S_s)$：对消息$m$生成一个签名值$\sigma$，其中$P_1,...,P_r$为环的$r$个成员，$S_s$为第$s$个成员，也即实际签名者的私钥
$ring-verify(m,\sigma)$：签名的验证，输出true或false

环签名方案无需初始设置，也即签名者无需其他环成员的知识、同意或协助即可完成将其他成员加入环中，签名者需要的只是了解其公钥

不同的成员之间可以使用独立的公钥签名方案，密钥和签名大小都可以不同，但是验证必须满足一般的合理性和完备性

此外我们希望签名是模糊的，因为验证者不能以大于$\frac{1}{r}$的概率确定实际签名者的身份，这种有限匿名性可以是计算性的也可以是无条件的

本文主要构造了无条件匿名性，也即敌手即便有无限算力和可以访问同一环成员产生的无限数量的指定消息的签名，也无法将签名与签名者关联起来

2.2 Leaking Secrets

讲故事

2.3 Designated Verifier Signature Schemes

指定验证者签名方案中，签名只能由签名者选择的单个验证者进行验证，该概念由Jakobsson Sako和Impagliazzo at Eurocrypt 96$[6]$首次提出

一个典型的应用程序可以使用户能够对临时电子邮件进行身份验证而不受内容的法律约束，例如，两家公司可以交换拟议合同的草案，他们希望在每封电子邮件中添加一个验证器，但不是一个可以向第三方（立即或几年后）显示的真实签名，以证明某个特定草案是由另一家公司提出的

指定验证者的方案可被视为轻签名方案，可以向预期的收件人验证消息且具备不可否认性

这个方案可以用零知识交互证明实现，但是只能说服指定的验证者，且需要交互，很难和电子邮件系统和匿名者结合使用，尽管可以使用非交互式零知识证明，但是随后Verifier可以向第三方展示签名，这不太好

另一种方法是协商一个共享秘密对称密钥$k$，并通过为使用密钥$k$计算的草案附加MAC来认证每个合同草案，此时必须向第三方揭示密钥来验证MAC，这样第三方也不知道这两家公司中的哪一家计算了MAC，但是这样需要初始设置来协商密钥$k$，因此仍然没有解决在没有实际签名情况下通过电子邮件发送的$k$进行身份验证的问题

指定验证者方案提供了一个简单的解决方案：A公司可以对其发送的每个草案进行签名，然后将B公司指定为验证者，这样通过使用A,B两个公司作为环成员的环签名方案来实现，此时B直到消息来自A（因为没有第三方可以生成环签名），但B无法向任何其他人证明草案是A签名的，因为B可以自己生成草案

与MAC情况不同，该方案使用公钥密码，因此A可以向B发送任何未经请求的、使用环签名的电子邮件且无需任何准备、交互或密钥交换

通过该环签名方案可以将标准签名方案转换为指定Verifier的方案，该方案几乎可以无消耗添加到任何电邮系统中

2.4 Efficiency of Our Ring Signature Scheme

基于RSA签名方案时本文效率很高，签名值需要一次模指数和每个non-signer的两次模乘，验证需要每个环成员一到两次的模乘

本质上生成或验证环签名的成本和生成或验证常规签名加上每个non-signer的一到两次模乘法的成本相同，因此即便环中由上百个成员，该方案也具有实用性

本文比Camenisch方案快2到3个数量级，Camenisch方案声称的效率是基于其比早期已知方案快4倍的事实（见其论文$[1]$第476页底部），此外类Camenisch方案在指数中使用线性代数，因此要求所有成员在各自的签名方案中使用相同的素模$p$

本文的设计标准之一是signer应当能够在不与其他环成员进行任何协商的情况下构造任意环，这些成员可能是RSA，或者DLOG，不同的用户也可能具有不同的模数，因此采用类似Camenisch的签名方案唯一实现方法是拥有一组同意方

需要注意的是，任何环签名的大小会随着环线性增长，因为其必须列出环成员，与使用预定义群的签名相比，这是环签名的一个本质缺点

3 The Proposed Ring Signature Scheme(RSA Version)

假设Alice希望为$r$个实体$A_1,...,A_r$在消息$m$上进行环签名，其中签名者为Alice（记为$A_s,1\leq s\leq r$）

为了简化标识和证明，先描述一个环签名方案，其中所有环成员使用RSA$[9]$作为个人签名方案，该构造同样适用于其他基于单向陷门置换的方案，但需要稍加修改来使用单向陷门函数（比如Rabin签名）

3.1 RSA Trap-Door Permutations

先来看一下典型的DH公钥密码模型，每个环成员$A_i$有一个公钥$P_i=(e_i,n_i)$，满足$\Z_{n_i}$上的单向陷门置换$f_i$

$$ f_i(x)=x^{e_i} \ mod \ n_i $$

同时假设只有$A_i$知道陷门信息，也即高效计算$f^{-1}_i$的方法

Extending trap-door permutations to a common domain

由于各个环成员的陷门RSA置换都可能有不同大小的域（$n_i$具有相同长度的比特数时也可能有不同大小的域），这意味着组合单个签名会很困难，因此我们扩展了所有陷门置换，使其公共域具有相同的集合$\{0,1\}^b$，满足$2^b>\max _i\{n_i\}$，也即$2^b$比所有环成员的模数$n_i$都要大

对于每个$\Z_{n_i}$上的单向陷门置换$f_i$，定义一个$\{0,1\}^b$上的扩展陷门置换$g_i$，具体如下

对于任意$b$比特输入$m$，定义非负整数$q_i,r_i$，满足$m=q_in_i+r_i,0\leq r_i<n_i$，然后定义$g_i$

$$ g_i(m)=\begin{cases} q_im_i+f_i(r_i);\ if \ (q_i+1)\cdot n_i \leq 2^b\\ m;\ otherwise \end{cases} $$

简单来说$g_i$就是通过用$f_i$来表示$m$的低比特位，高比特位不变，如果选择恰当的$b$（比如$b$为160 bit且大于所有的模数$n_i$），则随机选择的消息$m$经过$g_i$处理后不变的概率可忽略（也即$g_i(m)=m$的概率可忽略）

显然$g_i$是$\{0,1\}^b$上的一个置换，且是单向陷门置换，因为只有知道$f^{-1}_i$的人才可以有效的计算$g^{-1}_i$

3.2 Symmetric Encryption

假设存在一个公开定义的对称加密算法$E$，对于长度为$l$的任意密钥$k$，记函数$E_k$为$b$比特串上的置换，此处本文采用RO模型（Random Permutation Oracle），在该模型下任意参与方都可以访问Oracle，且Oracle对$E_k(x),E_k^{-1}(y)$的请求返回真随机的响应$[7]$

3.3 Hsh Functions

假设存在一个公开定义的抗碰撞hash函数$h$，将任意长度输入映射到$l$比特长的串，该串将作为$E$的密钥

本文将$h$视为一个RO，且$h$不必是置换，不同的请求可能有相同的响应，拒绝对$h^{-1}$的请求

3.4 Combining Functions

定义密钥组合函数$C_{k,v}(y_1,...,y_r)$，以密钥$k$、初始值$v$、任意值$y_i,...,y_r\in \{0,1\}^b$作为输入

每个此类组合函数都使用$E_k$作为子过程，并在$\{0,1\}^b$中生成一个值$z$作为输出

对于给定的$k,v$，该组合函数具有下列属性

每个输入上的置换：对于$\forall 1\leq s\leq r$和任意给定的其他输入$y_i,i\neq s$，$C_{k,v}$为一个一对一映射，将$y_s$映射到$z$
可有效求解任何单一输入：对于$\forall 1\leq s\leq r$，给定一个$b$比特的$z$和所有输入$y_i,i\neq s$，可以高效找到一个$b$比特的$y_s$，满足$C_{k,v}(y_1,...,y_r)=z$
无陷门条件下求解所有输入的验证方程不可行：给定$k,v,z$，对于给定的$x_1,..,x_r$，任何敌手在无法计算$g^{-1}_i$的条件下都无法计算$C_{k,v}(g_1(x_1),...,g_r(x_r))=z$

举个例子。比如定义$C_{k,v}$如下

$$ C_{k,v}(y_1,...,y_r)=y_1\oplus y_2\oplus ...\oplus y_r $$

这个$C_{k,v}$满足前两个条件，但是不满足第三个条件，因为对于任意选择的单向陷门置换$g_i$，当$r$足够大时，可以利用线性代数的知识找到$x_1,...,x_r$而无需知道$g^{-1}_i$，具体方法可以看原始论文$[1]$

本文提出的$C_{k,v}$如下

$$ C_{k,v}(y_1,...,y_r)=E_k(y_r\oplus E_k(y_{r-1}\oplus E_k(y_{r-2}\oplus E_k(...\oplus E_k(y_1\oplus v)...)))) $$

该函数适用于序列$(y_1,...,y_r)$，其中$y_i=g_i(x_i)$，如下图所示，得到的函数在RO模型中是可证明安全的

显然这是每个输入上的置换，因为$xor,g_i,E_k$都是置换，此外该函数对于任何单个输入都是可有效求解的，因为$k$确保了可以从初值$v$自前向后运算和从$z$自后向前运算，以确定唯一缺失的$y_i$

该函数可用于验证签名，方法时用$m$的hash值作为对称密钥$k$，并强制输出$z$等于输入$v$，一致性条件$C_{k,v}(y_1,...,y_r)=v$如下图所示

通过始终选择0作为$v$，可以获得更紧凑的环签名变体，该变体也是安全的接下来正式描述签名的生成和验证

Generating a ring signature：对于给定消息$m$，私钥$S_s$和环成员公钥序列$P_1,...,P_r$，计算环签名如下
Choose a key：signer先利用hash函数计算对称密钥$k=h(m)$（或者采用变体$k=(m,P_1,...,P_r)$，不过普通方案也可以确保安全）
Pick a random gule value：signer选择初值$v\in _R\{0,1\}^b$
Pick random $x_i$'s：signer为其他环成员均匀随机的选择$x_i\in_R\{0,1\}^b$并计算$y_i=g_i(x_i)$，其中$1\leq i\leq r,i\neq r$
Solve for $y_i$：之后signer找到一个$y_s$，满足一致性条件$C_{k,v}(y_1,...,y_r)=v$（根据假设，给定其他输入的任意值，有且仅有一个$y_s$满足该等式，且该值可以有效计算）
Invert the signer's trap-door permutation：signer用其计算得到的$y_s$计算陷门$x_s=g_s^{-1}(y_s)$
Output the ring signature：signer输出关于$m$的签名值，该签名值为一个$2r+1$的元组$(P_1,...,P_r;v;x_1,...,x_r)$

然后看看如何验证

Verifiying a ring signature：以消息$m$和签名值$(P_1,...,P_r;v;x_1,...,x_r)$作为输入
Apply the trap-door permutations：对于$i=1,2,...,r$，$k$：Verifier计算$y_i=g_i(x_i)$
Obtain $k$：Verifier计算对称密钥$k=h(m)$（如果采用变体的话还需要获取环成员的公钥）
Verify the ring equation：Verifier检查一致性条件$C_{k,v}(y_1,...,y_r)=v$，当且仅当满足一致性条件时签名正确

3.5 Security

本文提出的环签名方案无条件地保护了签名者的身份，对于每个$k$和$v$，一致性条件正好有$2^{b\cdot (r-1)}$个解，因此无论Signer的身份如何，签名生成过程都可以以相同的概率选择所有解，该方案不依赖于任何复杂性理论假设或预言的随机性

由于环签名的安全性不会比单一签名的方案更强，因此环签名的合理性必须是计算性的，本文的目标是证明在RO模型中，任何恶意算法$A$都可以通过分析其他多项式个消息$m_j\neq m$以及这些$m_j$对应的环签名来以一个不可忽略的概率生成消息$m$的签名值，都可被转化为另一算法$B$，该算法$B$以不可忽略的概率计算随机输入$y$上的一个单向陷门函数$g_i$

具体的证明和分析可以看原文$[1]$

4 Our Ring Signature Scheme（Rabin Version）

拉宾的公钥密码系统$[8]$比RSA具有更高效的签名验证，因为验证涉及平方而不是立方，这将模乘的次数从2减少到1

但是需要处理Rabin的映射$f_i(x_i)=x^2_i \ mod \ n_i$，这个映射在$\Z^*_{n_i}$上不是置换，因此实际上只有1/4的消息可以签名，且这些消息具有多个签名

因此我们可以这么修改：在签名时，如果$g_s^{-1}(y_s)$未定义，则更改最后一个随机选择的$x_{s-1}$，由于只需要反转一个单向陷门函数，因此Signer在成功生成环签名前平均尝试次数的期望为四次，无论换的大小如何，这样的复杂性基本上与原本的Rabin签名的情况相同

更重要的是无条件匿名性的证明，它依赖于所有映射都是置换，当$g_i$不是置换时，给定环签名中随机选择值和计算$x_i$的值之间的分布可能存在显著差异，从而导致可能在所有可能的Signer之间识别出真正的Signer，且可以证明在许多具体类型的单向陷门置换中这种问题真实存在

具体看原文$[1]$

5 Generalizations and Special Cases

环签名的概念有许多有趣的扩展和特例，比如用Rabin Version时，在$r=1$时可以视为Rabin签名方案的随即版本

如下图所示，验证条件可以写为$(x^2 \ mod \ n)=v\oplus E^{-1}_{h(m)}(v)$，等号右侧为消息$m$在随机性$v$下的hash

当$r=2$时，环等式可以写成

$$ (x^2_1 \ mod \ n_1)=E_{h(m)}(x^2_2 \ mod \ n_2) $$

其中模平方以常规方式扩展到$\{0,1\}^b$，这个等式不是恒等的，但是具有相同的安全属性，因此本文推荐这个方案在电邮系统中实现指定Verifier的签名方法，其中$n_1$表示发件人的公钥，$n_2$为收件人的公钥

常规环签名中，对方不可能暴露Signer的身份，但是某些情况下Signer自己可能希望能够选择在以后证明匿名电邮的发送者身份

还有一种可能是Signer$A$最初希望使用$(A,B,C)$作为可能的Signer列表，但是后来证明$C$不是真正的Signer，有一种简单的方法来实现这种方案，也即以伪随机而非真随机的方式为non-signer选择$x_i$，为了证明$C$不是Signer，$A$可以揭示用于生成$C$相关签名的伪随机种子而为了证明$A$时Signer，$A$可以揭示用于生成签名中所有non-signer部分的种子，$A$不能滥用这个技术来证明他不是Signer，因为他自己的部分是计算出来的而非生成出来的，且这样的计算不应当有对应的种子

总结

[ ] todo

后记

[ ] todo

Reference

$[1]$ Ronald L. Rivest, Adi Shamir, Yael Tauman:How to Leak a Secret. ASIACRYPT 2001: 552-565

$[2]$ David Chaum, Eugène van Heyst:Group Signatures. EUROCRYPT 1991: 257-265

$[3]$ Ronald Cramer, Ivan Damgård, Berry Schoenmakers:Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. CRYPTO 1994: 174-187

$[4]$ Whitfield Diffie, Martin E. Hellman:New directions in cryptography. IEEE Trans. Inf. Theory 22(6): 644-654 (1976)

$[5]$ G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Oxford,fifth edition, 1979.

$[6]$ Markus Jakobsson, Kazue Sako, Russell Impagliazzo:Designated Verifier Proofs and Their Applications. EUROCRYPT 1996: 143-154

$[7]$ Michael Luby, Charles Rackoff:How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM J. Comput. 17(2): 373-386 (1988)

$[8]$ M. Rabin. Digitalized signatures as intractable as factorization. Technical ReportMIT/LCS/TR-212, MIT Laboratory for Computer Science, January 1979.

$[9]$ Ronald L. Rivest, Adi Shamir, Leonard M. Adleman:A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21(2): 120-126 (1978)

$[10]$ Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung:On Monotone Formula Closure of SZK. FOCS 1994: 454-465

签名方案环签名

Abstract

1 Introduction