一种模糊性可明确废除的并发签名方法

摘要

本发明公开了一种模糊性可明确废除的并发签名方法，该方法称为可废除并发签名(RCS)，RCS提供了废除算法，可废除并发签名RCS包含参数设定、签名产生、验证签名、确定签名者身份等步骤。该方法在双方交换签名时只需要产生一个keystone，根据公布的keystone可以明确地废除签名的模糊性，从而使双方交换的签名具备了标准签名的性质，消除了针对并发签名模糊性方面的各种可能攻击，使得签名的安全性得到大大的提高。

说明书

技术领域

本发明属于数字签名领域，涉及网络环境中的并发签名机制，特别涉及一种模糊性可明确废除的并发签名方法。

背景技术

网络环境中公平交换数字签名是密码学领域广泛研究的问题，其典型应用包括合同签订、支付系统、电子商务和可认证电子邮件等。传统的解决方案有秘密逐步释放(G.Garay，C.Pomerance.Timed fair exchange of standardsignatures.In Proc.Financial Cryptography 2003，LNCS 2742，190-207，2003.)和基于在线或离线的半可信第三方(G.Ateniese.Verifiable encryption of digitalsignatures and applications，ACM Transactions on Information and SystemSecurity，7(1)：1-20，2004.)两种。

秘密逐步释放(gradual secret releasing)在协议参与者计算能力有较大差异时无法做到严格公平；而基于在线或离线的半可信第三方需要第三方的参与，并且公平性依赖于其半可信性。

Chen等人提出的并发签名(L.Chen，C.Kudla and K.G.Paterson.Concurrent signatures.In Advances in Cryptology-Eurocrypt 2004，LNCS 3027，287-305，2004.)在许多应用中可避免上述问题，其基本思想是首先由协议一方选择一种称为keystone的特殊信息，并计算出keystone印记；然后协议双方由keystone印记产生签名并进行交换。由于签名的产生使用了环签名技术，使得签名具有了模糊性，任何第三方只能断定模糊签名由两个签名者之一产生，而无法准确判定签名者身份，因此不会产生不公平的后果。最后公布keystone，第三方根据keystone印记产生的单向性可推断产生模糊签名的签名者身份。

并发签名的新颖性使其受到广泛研究，这些研究成果主要是发现并弥补了并发签名存在的各种各样的安全漏洞(W.Susilo，Y.Mu and F.Zhang，Perfect Concurrent Signature Schemes，ICICS 2004，LNCS 3269，14-27，2004；W.Susilo，Y.Mu，Tripartite concurrent signatures，IFIP/SEC’05，425-441，2005；D.Tonien，W.Susilo，R.Safavi-Naini.Multi-party Concurrent Signatures，ISC06，LNCS 4176，131-145，2006；G.L.Wang，F.Bao and J.Y.Zhou.TheFairness of Perfect Concurrent Signature.ICICS 2006，LNCS 4307，435-451，2006.)，其主要思想是在产生并发签名时由双方各产生一个keystone，来尽可能提高安全性。然而最近的研究(YF Li，DK He，XH Lu.Accountability ofPerfect Concurrent Signature.Proc.of  2008International Conference onComputer and Electrical Engineering，773-777，2008；CT Shieh.Fair Multi-partyConcurrent Signatures.Master′s Thesis，National Central University in Taiwan，2008.)发现上述解决安全性的方案仍存在不同方面的安全漏洞。

这些方案之所以存在安全问题，根源在于取消签名模糊性时所运用的方法存在缺陷。在这些方案中，当keystone发布后，双方签名实际上仍然维持模糊性；而当第三方需要确定签名者身份的时候也仅能通过推断的方式来确定。其推断方式为：由于产生模糊签名时需要使用keystone印记，而keystone印记只能通过keystone获得，现在某个签名者公布了该keystone，则必然说明一个模糊签名由该签名者产生，而另一个模糊签名必然由另一方产生。但是这种推断过程中的必然性在上述方案中并没有严谨地证明，因此带来了各种攻击的可能性。比如在提出的方案(W.Susilo，Y.Mu and F.Zhang，PerfectConcurrent Signature Schemes，ICICS 2004，LNCS 3269，14-27，2004)中，初始签名者选择keystone k及随机数t，并产生keystone印记s₂。而匹配签名者再利用s₂及t产生keystone印记s₁。双方根据各自产生的keystone印记进行签名，以防止不公平情况的发生。然而攻击者可以根据s₁与s₂及t的数学关系，公布一个新的keystone k′≠k，并且根据k′可以计算出相同的keystone印记s₂，其结果是匹配签名者的签名与身份绑定，而自己的签名并不与身份绑定，造成了不公平的结果。

Nguyen提出的非对称并发签名(K.Nguyen.Asymmetric concurrentsignatures.Proc.of 7th International Conference on Information andCommunications Security(ICICS 2005)，LNCS 3783，181-193，2005.)，在某种程度上也是解决并发签名方案的上述缺陷，但该方案要求交换双方采用不同的算法产生签名，不仅不便于实现，而且为攻击者推测双方的身份提供了一定的线索。

发明内容

本发明解决的问题在于提供一种模糊性可明确废除的并发签名方法，该方法称为可废除并发签名(Revocable Concurrent Signature，简称RCS)，RCS提供了废除算法，根据公布的keystone可以明确地废除签名的模糊性，从而使双方交换的签名具备了标准签名的性质，提高了并发签名的安全性。

本发明是通过以下技术方案来实现：

一种可明确验证的并发签名方法，初始签名者P_i和匹配签名者P_j之间的数字签名交换包括以下步骤：

1)P_i选择某个信息k作为keystone，并计算keystone印记f＝KGEN(k，m_i，m_j)，然后产生针对信息m_i的模糊签名σ_i＝<L_i，U_i，f>＝ASIGN(y_i，x_i，y_j，m_i，f)，并将σ_i发送给P_j；其中y_i、y_j分别为P_i、P_j的公钥，而x_i为P_i的私钥；

2)收到σ_i之后，P_j首先验证AVERIFY(σ_i，m_i)＝1，在成立的情况下P_j产生针对信息m_j的模糊签名σ_j＝<L_j，U_j，f>＝ASIGN(y_j，x_j，y_i，m_j，f)，并将σ_j发送给P_i，其中x_j为P_j的私钥；

若AVERIFY(σ_i，m_i)＝1不成立则退出协议或者等待P_i再次发送σ_i；

3)收到σ_j之后，P_i确定σ_j是否包含与σ_i相同的f，并验证AVERIFY(σ_j，m_j)＝1，在均成立的情况下P_i向P_j发送keystone k；

若AVERIFY(σ_i，m_i)＝1不成立则退出协议或者等待P_j再次发送σ_j；

4)P_i根据JUDGE(y_j，σ_j，k，m_i，m_j)＝1确定签名者P_j的身份；

P_j根据JUDGE(y_i，σ_i，k，m_i，m_j)＝1确定签名者Pi的身份；

上述步骤涉及的参数是由参数设置算法SETUP建立，该算法是一个输入是安全参数λ的概率算法，输出包括：参与者集合信息空间签名空间keystone空间keystone印记空间每个参与者P_i的公钥y_i和私钥x_i，以及系统参数δ；其中参与者集合N与λ呈多项式关系，keystone印记空间的产生函数为KGEN：

而信息m_i、当参与者为P_i和P_j时，其公钥分别为y_i和y_j，其私钥分别为x_i和x_j；

在上述步骤中涉及的算法为：

签名算法ASIGN是一个概率算法，其输入为<y_i，x_i，y_j，m，f>，而输出是信息的模糊签名σ＝<L，U，f>；其中L＝{y_i，y_j}或{y_j，y_i}，是参与者P_i、P_j的公钥列表，x_i为签名者P_i的私钥，而

验证签名算法AVERIFY是一个确定性算法，输入为<σ，m>，其中σ＝<L，U，f>，输出为1或0，1表示签名有效的，0表示签名无效；

确定签名者身份算法JUDGE是一个确定性算法JUDGE，输入为<y_i，σ，k，m_i，m_j>，其中σ＝<L，U，f>，y_i∈L，并满足f＝KGEN(k，m_i，m_j)及AVERIFY(σ，m)＝1；输出为1或0，1表示签名σ是由拥有公钥y_i的参与者所产生，而0则表示不是。

所述的模糊性可明确废除的并发签名方法，任何第三方对于双方签名的验证为：

输入k、m_i、m_j和待验证签名σ，然后验证f＝KGEN(k，m_i，m_j)、AVERIFY(σ，m_i)＝1

若成立，则进一步判断JUDGE(y_i，σ，k，m_i，m_j)＝1是否成立，若成立则输出1，否则输出0；

1表示签名σ是由拥有公钥y_i的参与者所产生，而0则表示不是，从而确定签名者的身份。

所述的模糊性可明确废除的并发签名方法，包括以下步骤：

对于安全参数λ，参数设置算法SETUP选择两个大质数p和q，使得满足q|(p-1)，q≥2^λ，设G_q是上阶为q的子群，并且生成元为g；

在此基础上选择以及hash函数H₁，H₂：并将函数KGEN定义为：其中“||”表示拼接；

为每个参与者P_i随机选择私钥计算公钥mod p，并通过秘密信道将x_i发送给P_i；最后公布系统参数δ＝<p，q，g>；

ASIGN算法为：对于输入<y_i，x_i，y_j，m_i，f>，签名者P_i选择对于{i，j}的随机排列π，π以1/2概率将i，j映射为i，j或者j，i，并由此得到公钥列表L＝{y_π(i)，y_π(j)}；P_i选取随机数a_j，作如下计算：

$F=f^{x_i}\mathrm{mod}p---\left(F1\right)$

$R_j=g^{a_j}\mathrm{mod}p,$$S_j=f^{a_j}\mathrm{mod}p$

h_j＝H₂(L||m_i||f||F||R_j||S_j)

$R_i=g^{a_i}{y}_j^{-h_j}\mathrm{mod}p,$$S_i=f^{a_i}{F}^{-h_j}\mathrm{mod}p$

h_i＝H₂(L||m_i||f||F||R_i||S_i)

t＝a_i+a_j+x_ih_i mod q

最后P_i得到发给参与者P_j的签名为σ＝<L，U，f>＝<L，R_π(i)，S_π(i)，R_π(j)，S_π(j)，h_π(i)，h_π(j)，t，F，f>；

AVERIFY算法为：输入签名σ＝<L，R_i，S_i，R_j，S_j，h_i，h_j，t，F，f>及信息m_i，其中L＝{y_i，y_j}，P_j在验证了h_i、h_j的正确性后判断以下两式是否成立：

$g^t=R_i{R}_j{y}_i^{h_i}{y}_j^{h_j}\mathrm{mod}p---\left(F2\right)$

$f^t=S_i{S}_j{F}^{h_i}{F}^{h_j}\mathrm{mod}p---\left(F3\right)$

如果F2、F3均成立则输出1，否则输出0；

JUDGE算法为：输入信息m_i的签名σ＝<L，R_i，S_i，R_j，S_j，h_i，h_j，t，F，f>及收到的交换信息m_j，其中L＝{y_i，y_j}；在满足及AVERIFY(σ，m_i)＝1的情况下，验证是否成立；

如果成立则输出1，否则输出0。

所述的签名为σ＝<L，R_π(i)，S_π(i)，R_π(j)，S_π(j)，t，F，f>。

所述的模糊性可明确废除的并发签名方法，当必要的时候，任何第三方对于双方签名的验证为：

输入k、信息m_i、待验证签名σ＝<L，R_i，S_i，R_j，S_j，h_i，h_j，t，F，f>及其收到的交换信息m_j，其中L＝{y_i，y_j}；在满足及AVERIFY(σ，m_i)＝1的情况下，验证是否成立，如果成立则输出1，否则输出0；

1表示签名σ是由拥有公钥y_i的参与者所产生，而0则表示不是，从而确定签名者的身份。

与现有技术相比，本发明具有以下有益的技术效果：

1、本发明提供的模糊性可明确废除的并发签名方法，双方交换签名时只需要产生一个keystone，在keystone公布之后可以明确地废除并发签名的模糊性，从而使双方交换的签名具备了标准签名的性质，消除了针对并发签名模糊性方面的各种可能攻击，使得签名的安全性得到大大的提高。

2、本发明所指的签名的安全性包括正确性、不可伪造性、模糊性和公平性；本发明提供的方法能够明确的实现对于上述特性进行了定义，并在随机预言模型下证明，基于DDH假设和DL假设，本发明提供的方案是安全的。

3、如果在必要的时候，任何第三方可以通过确定的废除算法公开验证签名者的身份；而不是采用缺乏严谨性的推断方式来推定签名者的身份，实现网络环境中数字签名的公平性。

4、与并发签名相比，RCS要求keystone印记f由k，m_i，m_j三者共同产生而不是只由k产生，其目的是防止攻击者利用f再产生对其它信息的模糊签名，并替换自己原来产生的模糊签名，从而造成不公平的情况；另一方面，在交换签名时，双方针对均已经明确的交换信息m_i和m_j，因此上述keystone印记的产生方法也是合理的；而且对于交换双方的多次交易，包含信息m_i和m_j的签名也排除了交易与交易之间错误绑定的可能，尽可能的实现签名的公平；

与其他消除并发签名的模糊性的方法相比，在保证签名的安全性的情况下，本发明提供的方法在交换签名时双方只需产生一个keystone，简化了签名交换协议。

与采用不同的算法产生签名解决交换模糊性废除的方法相比，本发明提供的方法在交换签名时采用相同的签名算法，更加方便了并发签名的应用；而且减少了攻击者的攻击机会，尽可能的保证了签名的安全性。

附图说明

图1为模糊性可明确废除的并发签名方法实现签名交换的流程图；

图2为第三方对签名验证的的流程图。

具体实施方式

本发明公开了可废除并发签名的方法(Revocable Concurrent Signature，简称RCS)，RCS提供了废除算法，根据公布的keystone可以明确地废除签名的模糊性，而不是采用不严谨的推断方式，从而使双方交换的签名具备了标准签名的性质；消除了针对并发签名模糊性方面的各种可能攻击。下面结合附图对本发明做进一步详细描述，所述是对本发明的解释而不是限定。

可废除并发签名RCS包含参数设定、数字签名、验证签名、确定签名的步骤，其具体设定为：

RCS方法中涉及的参数是由参数设定算法SETUP产生的，该算法是一个概率算法，其输入是安全参数λ，而输出包括：

参与者集合信息空间签名空间keystone空间keystone印记空间以及系统参数δ；

keystone印记产生函数KGEN：设参与者集合N与λ呈多项式关系，并且为每个参与者P_i输出其公钥y_i和私钥x_i。

RCS方法中的数字签名是由签名算法ASIGN产生的，ASIGN算法是一个概率算法，其输入为<y_i，x_i，y_j，m_i，f>，其中y_i、y_j为参与者P_i、P_j的公钥，x_i为签名者P_i的私钥，而是keystone印记；

输出由私钥x_i决定的关于信息的模糊签名σ＝<L，U，f>，其中L＝{y_i，y_j}或{y_j，y_i}，是参与者P_i、P_j的公钥列表，而

RCS方法中的验证签名是通过验证签名算法AVERIFY来验证，AVERIFY算法是一个确定性算法，其输入为<σ，m>，其中σ＝<L，U，f>，而输出为表示签名有效的1或表示签名有效的0。

RCS方法中的确定签名是由确定签名算法JUDGE产生的，JUDGE算法是一个确定性算法，其输入为<y_i，σ，k，m_i，m_j>，其中σ＝<L，U，f>，y_i∈L，并满足f＝KGEN(k，m_i，m_j)及AVERIFY(σ，m)＝1。算法输出为1或0，表示签名σ是否由签名者P_i(拥有公钥y_i)产生，m_i和m_j是交换双方分别拥有的、签名所针对的公开信息，签名双方通过上述方法来实现包含m_i和m_j信息的签名交换。

参见图1，本发明以具体的算法来说明初始签名者P_i和匹配签名者P_j之间欲交换信息的签名，通过以下步骤来实现：

选择两个大质数p和q，满足q|(p-1)，q≥2^λ，设G_q是上阶为q的子群，生成元为g；

参数设置SETUP算法选择hash函数H₁，H₂：将和分别定义为：公布系统参数δ＝<p，q，g>；

而函数KGEN定义为其中“||”表示拼接；并为每个参与者P_i随机选择私钥计算公钥并通过秘密信道将x_i发送给P_i。

ASIGN的算法为：对于输入<y_i，x_i，y_j，m_i，f>，签名者P_i选择对于{i，j}的随机排列π，π以1/2概率将i，j映射为i，j或者j，i，并由此得到公钥列表L＝{y_π(i)，y_π(j)}。P_i选取随机数a_j，作如下计算：

$F=f^{x_i}\mathrm{mod}p---\left(F1\right)$

$R_j=g^{a_j}\mathrm{mod}p,$$S_j=f^{a_j}\mathrm{mod}p$

h_j＝H₂(L||m_i||f||F||R_j||S_j)

$R_i=g^{a_i}{y}_j^{-h_j}\mathrm{mod}p,$$S_i=f^{a_i}{F}^{-h_j}\mathrm{mod}p$

h_i＝H₂(L||m_i||f||F||R_i||S_i)

t＝a_i+a_j+x_ih_i mod q

得到的签名为σ＝<L，U，f>＝<L，R_π(i)，S_π(i)，R_π(j)，S_π(j)，h_π(i)，h_π(j)，t，F，f>；

其中使用随机排列π的目的是隐藏签名者的身份，使得攻击者无法根据公钥排列次序判定签名者身份；签名中的h_π(i)、h_π(j)可以省略，以减少签名长度。

根据以上设定，P_i选择k作为keystone，并计算keystone印记f＝KGEN(k，m_i，m_j)，然后产生信息m_i的模糊签名σ_i＝<L_i，U_i，f>＝ASIGN(y_i，x_i，y_j，m_i，f)＝<L，R_π(i)，S_π(i)，R_π(j)，S_π(j)，h_π(i)，h_π(j)，t，F，f>，并将σ_i发送给P_j。

AVERIFY的算法为：输入签名σ＝<L，R_i，S_i，R_j，S_j，h_i，h_j，t，F，f>及信息m_i，其中L＝{y_i，y_j}，验证者验证h_i、h_j的正确性后判断以下两式是否成立：

$g^t=R_i{R}_j{y}_i^{h_i}{y}_j^{h_j}\mathrm{mod}p---\left(F2\right)$

$f^t=S_i{S}_j{F}^{h_i}{F}^{h_j}\mathrm{mod}p---\left(F3\right)$

如果F2、F3均成立则输出1，否则输出0。

根据以上设定，收到σ_i之后，P_j首先验证AVERIFY(σ_i，m_i)＝1，在成立的情况下P_j产生信息m_j的模糊签名σ_j＝<L_j，U_j，f>＝ASIGN(y_j，x_j，y_i，m_j，f)＝<L，R_π(j)，S_π(j)，R_π(i)，S_π(i)，h_π(j)，h_π(i)，t，F，f>，并将σ_j发送给P_i；

若AVERIFY(σ_i，m_i)＝1不成立则退出协议或者等待P_i再次发送σ_i；

JUDGE的算法为：输入信息m_i的签名σ＝<L，R_i，S_i，R_j，S_j，h_i，h_j，t，F，f>及收到的交换信息m_j，其中L＝{y_i，y_j}，在满足及AVERIFY(σ，m_i)＝1的情况下，验证是否成立；

如果成立则输出1，否则输出0。

P_i根据JUDGE(y_j，σ_j，k，m_i，m_j)＝1确定签名者P_j的身份；

P_j根据JUDGE(y_i，σ_i，k，m_i，m_j)＝1确定签名者P_i的身份。

参见图2，当必要的时候，任何第三方对于双方签名的验证为：

输入k、信息m_i及其签名σ＝<L，R_π(i)，S_π(i)，R_π(j)，S_π(j)，h_π(i)，h_π(j)，t，F，f>和信息m_j，其中L＝{y_i，y_j}，在满足及AVERIFY(σ，m)＝1的情况下，算法验证等式是否成立；

若成立则输出1，否则输出0。

为了验证本发明公开的RCS的安全性，下面首先给出安全性的定义，并在具体的模型给予安全性的证实。

若可废除并发签名RCS具有正确性、不可伪造性模糊性和公平性，则称其为安全的。

a、正确性的定义

对于任意y_i、y_j、x_i、m_i和f，如果满足以下两个条件，则RCS是正确的：

(1)AVERIFY(ASIGN(y_i，x_i，y_j，m_i，f)，m_i)＝1；

(2)存在有f＝KGEN(k，m_i，m_j)，则JUDGE(y_i，ASIGN(y_i，x_i，y_j，m_i，f)，k，m_i，m_j)＝1。

b、不可伪造性的定义

考虑由概率多项式时间(PPT)攻击者和挑战者执行的实验：

-初始化：执行SETUP(1λ)，产生KGEN和系统参数δ，以及每个P_i的公钥和私钥y_i、x_i，公钥均输出给而私钥由保存。

-查询：可执行以下查询操作：

(1)印记查询：向提交信息选择一个keystone并返回f＝KGEN(k，m_i，m_j)。存放元组<f，m_i，m_j，k>到印记查询列表中，以便实现Keystone查询。

(2)Keystone查询：向提交元组<f，m_i，m_j>，若在印记查询列表中找到元组<f，m_i，m_j，k>，则输出否则输出无效。

(3)私钥查询：提交任意公钥y_i，若y_i为产生的公钥，则返回相应的私钥x_i。

(4)签名查询：提交形式为<y_i，y_j，m_i，f>的信息，其中y_i和y_j为任意参与者公钥，并且y_i≠y_j。返回模糊签名σ＝<L，U，f>＝ASIGN(y_i，x_i，y_j，m_i，f)。可用AVERIFY算法验证返回结果。

-输出：最终输出签名σ＝<L，U，f>，其中L＝{y_i，y_j}，若AVERIFY(σ，m_i)＝1，并且没有针对<y_i，y_j，m_i，f>或<y_j，y_i，m_i，f>进行过签名查询，也没有针对y_i和y_j进行过私钥查询，但可以通过印记查询得到f，甚至可以再通过keystone查询得到使得存在信息f＝KGEN(k，m_i，m_j)，则在本次实验中获胜。

若任何攻击者在实验中获胜概率相对于安全参数λ可忽略，则RCS具有自适应选择消息攻击下的存在性不可伪造性。

上述定义只包含了外部攻击的情况，即攻击者在不知道双方私钥的情况下，根据已公布或自行产生的keystone，或者在只知道keystone印记的情况下伪造任一方的模糊签名；而对于内部攻击的情况则包含在公平性的定义中。

c、模糊性的定义

考虑以下由PPT攻击者和挑战者执行的实验：

-初始化、第一阶段查询：同定义b。

-挑战：选择元组<y_i，y_j，m_i>作为向发送的挑战，要求没有针对y_i和y_j进行过私钥查询。随机选择计算f＝KGEN(k，m_i，m_j)，并随机选择b∈{0，1}，若b＝0，则输出签名σ₀＝<L₀，U₀，f>＝ASIGN(y_i，x_i，y_j，m_i，f)，否则输出σ₁＝<L₁，U₁，f>＝ASIGN(y_j，x_j，y_i，m_i，f)，并将σ_b交给-第二阶段查询：同定义b，同样要求不能针对y_i和y_j进行过私钥查询，并且不能针对f进行keystone查询。

-输出：输出对b的猜测b′，若b＝b′，则在本次实验中获胜。

定义攻击者获胜的优势为获胜概率大于猜测概率(1/2)的部分，则如果任何攻击者在实验中的获胜的优势相对于安全参数λ是可忽略的，则RCS具有模糊性。

模糊性的含义是指任何一个外部攻击者(不知道双方私钥)无法分辨产生模糊签名的签名者身份。该定义与文献(L.Chen，C.Kudla and K.G.Paterson.Concurrent signatures.In Advances in Cryptology-Eurocrypt 2004，LNCS 3027，287-305，2004.)的不同之处是要求攻击者不能获得产生模糊签名的keystone，否则可通过JUDGE算法废除模糊性。由于签名只需要在keystone公布前具有模糊性，因此要求是合理的。

d、公平性的定义

考虑以下由PPT攻击者和挑战者执行的实验：

-初始化、查询：同定义b。

-输出：选择元组<y_j，y_i，m_i，f>，输出签名σ＝<L，U，f>及信息m_j，使得AVERIFY(σ，m_i)＝1，要求没有针对y_i进行私钥查询，并且满足以下两个条件之一，则在本次实验中获胜：

(1)f是以前印记查询的输出，即的印记查询列表中存在元组<f，m_i，m_j，k>，但没有针对f进行过Keystone查询，并有JUDGE(y_j，σ，k，m_i，m_j)＝0；

(2)可以针对f进行过Keystone查询，以便得到k。在输出签名σ后，使用相同的f产生信息m_j的签名σ′＝<L′，U′，f>＝ASIGN(y_i，x_i，y_j，m_j，f)，其中L′与L包含相同公钥(但次序可不同)。得到σ′，在验证AVERIFY(σ′，m_j)＝1的情况下输出使得f＝KGEN(k，m_i，m_j)，并且有JUDGE(y_j，σ，k，m_i，m_j)＝0，JUDGE(y_i，σ′，k，m_i，m_j)＝1。

如果任何攻击者在实验中获胜的概率相对于安全参数λ是可忽略的，则RCS具有公平性。                                           □

上述定义中的条件(1)要求作为匹配签名者的攻击者不能产生一个有效的模糊签名，使得keystone发布后，JUDGE算法无法判定攻击者就是签名者，维护了初始签名者的公平性。条件(2)要求在双方使用相同印记产生模糊签名后，作为初始签名者的攻击者，不能只将一个模糊签名与匹配签名者绑定，维护了匹配签名者的公平性。公平性也排除了内部伪造的情况，即一方无法伪造一个模糊签名，并使之与对方的身份绑定。

根据上述定义对RCS的正确性及安全性的证明如下：

可废除签名算法RCS的正确性容易验证，因为有以下两式成立：

$g^t=g^{a_i}{g}^{a_j}{\left(g^{x_i}\right)}^{h_i}=g^{a_i}{g}^{a_j}{y}_i^{h_i}$

$R_i{R}_j{y}_i^{h_i}{y}_j^{h_j}=g^{a_i}{y}_j^{-h_j}{g}^{a_j}{y}_i^{h_i}{y}_j^{h_j}$

因此(F2)成立，同样可验证(F3)成立，说明ASIGN与AVERIFY的正确性。另外，故JUDGE算法也是正确的。

可废除签名算法的安全性由以下的定理1至3保证。证明过程采用随机预言模型，将H₁、H₂对应的随机Oracle分别称为H₁-Oracle、H₂-Oracle。

定理1(模糊性)

在随机预言模型下，假定存在PPT攻击者在定义4的实验中在限定时间τ内获得了不可忽略的优势ε，则存在另一个攻击者在时间τ′≤τ+(Q_f+Q_h+Q_s)τ_h+Q_sτ_s之内，以不可忽略优势解决DDH问题，其中Q_f、Q_h和Q_s分别表示印记查询(H₁-Oracle查询)、H₂-Oracle查询和签名查询次数，τ_h、τ_s表示H₂-Oracle查询和签名查询的时间。

证明：模拟挑战者与交互，利用解决DDH问题。给定DDH问题实例<g，g^α，g^β，g^γ>及随机数随机选择b∈{0，1}及参与者将其公钥设置为并按照定义c应答的查询。当给出挑战元组<y_i，y_j，m_i>时，若i，j∈{u₀，u₁}时(概率为)，将f和F的值设置为g^β、g^γ，并且当的输出b′＝b时输出1，否则输出0，表示判断g^γ＝g^αβ成立和不成立。对于DDH问题实例<g，g^α，g^β，g^γ>，当g^γ＝g^αβ立时，则f和F满足(F1)，因此输出的b′＝b正确判断了签名者，则以同样概率正确判断DDH问题；而当g^γ＝g^αβ不成立时，若输出b′＝1-b，输出的0也是正确判断。由于为随机数，因此计算正确判断的概率分为两种情况：第一，以1/q的概率成立，此时正确判断了签名者；第二，以(1-1/q)的概率不成立，此时f和F，或者f和F都不满足(F1)，只能猜测签名者。因此对<g，g^α，g^β，g^γ>正确判断的概率为：即正确解决DDH问题的优势大于考虑在模拟的过程中可能停机的概率，因而得证。

定理2(不可伪造性)

在随机预言模型下，假定存在PPT攻击者在定义3的实验中，在限定时间τ之内以不可忽略概率伪造了一个有效的RCS签名，则可在期望时间之内解决DL问题。

证明：本发明提出的RCS签名在形式上完全符合一般环签名的要求，因此可适用Forking引理(J.Herranz，G.Saez.Forking lemmas for ring signatureschemes.Proc.of Indocrypt’03，LNCS 2904，266-279，2003.)。运用Forking引理，通过重放攻击者使输出针对某个信息m_i的两个有效的RCS签名<L，R_i，S_i，R_j，S_j，h_i，h_j，t，F，f>及<L，R_i，S_i，R_j，S_j，h′_i，h′_j，t′，F，f>(为了简单起见，将π设为恒等映射)。若h_i＝h′_i，h_j≠h′_j，根据(F2)有则故可计算出而当h_j＝h′_j，h_i≠h′_i时，同样可计算出x_i。这意味着攻击者由参与者公钥可计算出对应私钥，故解决了DL问题。

定理3(公平性)

不存在PPT攻击者能够在定义d的实验中以不可忽略的概率胜出。

证明：对于定义d的情况(1)，由于m_i的签名σ＝<L，R_i，S_i，R_j，S_j，h_i，h_j，t，F，f>(其中L＝{y_i，y_j})经过算法AVERIFY验证，而且不知道私钥x_i，则只能用私钥x_j产生签名，否则违背定理2。又由于JUDGE(y_j，σ，k，m_i，m_j)＝0，则存在x_s≠x_j，使得根据Forking引理，可产生m_i的两个有效的签名<L，R_i，S_i，R_j，S_j，h_i，h_j，t，F，f>及<L，R_i，S_i，R_j，S_j，h′_i，h′_j，t′，F，f>，并且h_i＝h′_i，h_j≠h′_j，否则可计算出私钥x_i。由于h_j≠h′_j，因此可得到而根据(F3)有则可计算出因此有x_s＝x_j，与假设矛盾。情况(2)可类似证明。

因此在随机预言模型下证明，基于DDH假设和DL假设，可废除并发签名RCS方案是安全的。