一种对诚实参与者公平的理性多秘密分享方法

摘要

本发明提出了一种对诚实参与者公平的理性多秘密分享方法，所述方法包括系统参数设置模块、分发者认证模块、秘密分发模块、秘密重构模块；系统参数设置模块生成系统的公开参数以及分发者和参与者的公钥，公开参数发送给其他模块；分发者认证模块通过比特承诺协议验证分发者；秘密分发模块主要是分发者将子秘密分发给相应的参与者；秘密重构模块主要用于验证子秘密的正确性，并将具有欺骗行为的参与者从重构秘密的参与者集合中删除，并判断是否为有意义轮，从而重构出秘密。如果想要共享新的秘密，则只需要公开随机选取的参数和承诺值。此方案解决了对诚实参与者的不公平问题，并能高效的实现多秘密的分享。

说明书

技术领域

本发明属于信息安全技术领域，具体指的是一种对诚实参与者公平的理性多秘密分享方法。

背景技术

随着信息技术的发展以及计算机和通信系统的普及，人们对网络的依赖程度越来越高，如网上银行、电子拍卖、电子招标和电子现金交易等。因此，对如何保证信息在产生和传输过程中的安全性也受到了越来越多的关注，并成为了现代密码学的重要研究领域。而现代密码体制的设计和研究都是在Kerckhoff假设前提下进行的，在这样的假设前提下密码算法的安全性完全依赖于密钥的安全性，所以，对密钥的管理或共享控制问题在密码体制的安全性研究和设计中占有十分重要的地位。

秘密共享是在一组参与者中共享秘密的技术，它主要是用于保护重要的信息，以防止信息的丢失、破坏和篡改。用秘密共享方案保管秘密具有如下优点：

(1)为秘密合理地创建了备份，克服了以往保存副本的数量越大，安全性泄漏的危险就越大，保存副本的数量越小，则副本丢失的风险越大的缺点；

(2)有利于防止权力过分集中以致被滥用的问题；

(3)保证了秘密的安全性和完整性；

(4)在不增加风险的情况下，增强了系统的可靠性。

针对秘密共享问题，Shamir和Blakley于1979年独立地提出了秘密共享(secret sharing)的概念，并分别设计了具体的实现体制，他们提出的两种门限方案是比较简单的门限方案，只能满足最普通的需要，被称为传统秘密分享。

在传统的门限秘密共享方案中，一个普遍的假设是所有成员都是诚实的。这样就可能产生两个问题：第一，分发中心不诚实，它分发伪造的秘密份额，使份额的持有者即使全都汇集在一起也无法恢复秘密；第二，份额持有者不诚实，通过出示假份额阻止秘密的恢复。可验证秘密共享(Verifiable Secret Sharing，简称VSS)方案是对传统秘密共享方案的修正，主要用于解决不诚实的分发中心问题。最早提出这一概念的是Chor，Goldwasser等。一个正常执行的可证验秘密共享方案能够保证：秘密分发阶段，分发者发送给参与者的份额是正确的；在秘密恢复阶段，参与者提交的份额也是正确的。

然而，一般的VSS方案的秘密分发过程的正确性只能被参与者证实，因而在分发者和参与者勾结下是不安全的。于是Stadler提出了可公开验证的秘密共享(Publicly Verifiable Secret Sharing，PVSS)的概念，并给出了两个PVSS方案，允许任何人验证秘密分发者分发给参与者的秘密份额是否有效而不泄露共享的秘密和参与者持有的秘密份额，为系统提供了更好的鲁棒性。

上述方案均为单秘密共享方案，即每个参与者的秘密份额只能使用一次，而且一次共享过程只能在n个参与者中共享一个秘密。但在实际应用中，常常需要n个参与者来共享多个秘密。比如研究无条件安全的多方计算的通信复杂度等。最简单的做法是：对每个秘密都构造一个秘密共享方案来实现多个秘密的共享。其缺陷是很明显的：秘密份额太多、份额利用率低下和数据量太大。1993年Blundo,Santis等提出了多秘密共享的理论。

2004年Halpern和Teague最先提出了理性秘密分享的概念，其中参与者不再只是诚实的和恶意的参与者，而是引进了理性参与者的概念，并为理性参与者提出了效用假设，理性参与者根据效用函数计算效用值来选择执行策略，并证明了在博弈论中固定交互次数的秘密分享是无法保证有限时间内完成的。与只有诚实和恶意的参与者的传统秘密分享方案相比，Halpern和Teague的方案显然更现实一些。之后许多研究人员和学者在Halpem和Teague工作的基础上进行了研究和扩展，Gordon,Katz解决了不能（2,2）秘密分享的问题，Abraham等引入k-resilient纳什均衡，Maleka提出了基于重复博弈的方案；Micali和Shelat使用可验证的可信通道提供了一个纯粹的理性秘密共享方案，表明了要想达到平衡不仅要理性而且要有信念；William等通过异步信道实现了理性秘密分享。但是上述方案中都存在着一个问题，如果有欺骗者欺骗，则所有参与者都不能获得秘密，这对于一直诚实的理性参与者来说是不公平的。

发明内容

本发明所要解决的技术问题在于克服现有技术的不足，对现有的理性秘密分享方案进行改进，给出一种对诚实参与者公平的理性多秘密分享方法，所述方法能够有效地减少欺骗并保证公平性，实现一次共享过程共享多个秘密，并且可以动态进行增加共享秘密。所述方法的核心思想是参与者分发的消息具有随机性，然后通过公开消息验证子秘密的正确性来判断参与者是否欺骗，如果欺骗则下一轮从重构秘密的参与者集合排除，否则继续进行重构秘密；最后通过公开消息验证该轮是否为有意义轮，如果为有意义轮则协议结束，得到了共享秘密；否则进入下一轮继续交互，直到得到了共享秘密。

为了解决上述技术问题，本发明所采用的技术方案是：一种对诚实参与者公平的理性多秘密分享方法，其特征在于，具体步骤如下：

步骤A，系统参数设置：

步骤A1：选择两个大素数p和q，满足q能整除(p-1)，选择非零模p剩余类环Z_p^*={1,2,…,p-2,p-1}，Z_p^*的生成元为g且满足g^q=1modp；选取一个正整数M，M为因网络错误允许最多发送的次数；公开参与者的公钥，用于验证其他参与者广播子秘密时发送的签名；

步骤A2：需要共享的r个秘密分别为K₁,K₂,…,K_r，r为共享秘密的个数，是正整数，随机选择r个随机数m₁,m₂,…,m_r，计算T_j=K_j-m_j^ld,j=1,2,…,r，公布T_j、m_j和其中l=n!，d为实际共享的秘密值；

步骤A3：秘密分发者对n个参与者分别选取n个互不相等的x_i∈Z_p={0,1,2,…,p-1}作为参与者的身份并公开，每个参与者用P_i表示，其中i=1,2,…,n；

步骤B，分发者认证：

步骤B1：分发者向参与者P_i随机发送两个字符串s_i1和s_i2，计算H(s_i1||s_i2||x_i)并公开，其中H(·)为单向函数，||表示字符串级联；

步骤B2：参与者P_i接收到分发者发送的s_i1和s_i2，计算H(s_i1||s_i2||x_i)并与公开的H(s_i1||s_i2||x_i)进行比较，若不相等则承诺的信息不对，否则进入分配阶段；步骤C，秘密分发：

秘密分发分为多轮执行，分发者在每一轮都构造一个t-1次多项式f(x)=d'+a₁x+a₂x²+…+a_t-1x^t-1，在每一轮执行中分发正确秘密的概率为β,0<β<1，即d'=d的概率为β，d_i'=f(x_i)modp为分发者分发给参与者P_i的子秘密，公开d、d'保密，其中d为真正的秘密值，d'为实际共享的秘密值；同时公开和L为执行轮次；

步骤D，秘密重构：

步骤D1：参与者接收分发者分发的子秘密d_i'，通过承诺值验证是否与分发者分发的一样，然后计算并对自己的身份进行签名sign(x_i)，将{x_i,sign(x_i),m_j,S_ij}发送给其他的参与者；具体步骤如下：

步骤D1-1：P_i将从分发者那接收到的子秘密d_i'进行计算与公开的比较，相同则接受d_i'，否则拒绝d_i'；

步骤D1-2：P_i计算$>S_{\mathrm{ij}}={m_j}^{{d_i}^{\prime }}\mathrm{mod}p;$>

步骤D1-3：选取其中δ₁,δ₂为安全参数且有0≤δ₁≤1，0≤δ₂≤1，计算b_ij=H(g,m_j,S_ij,W_i,w',m')，在整数环Z上计算y_ij=c_ij+b_ijd_i'，P_i公开验证值{y_ij,b_ij}；

步骤D1-4：参与者P_i广播{x_i,sign(x_i),m_j,S_ij}，其中sign(x_i)是对x_i的签名；

步骤D2：P_i接收其他参与者广播的子秘密，并用其他参与者公开的承诺值验证是否和其发送的子秘密相同，如果相同且参与者人数不小于t则重构秘密值，否则在下一轮将欺骗的参与者从重构秘密的参与者集合中排除；利用公开承诺值验证重构的秘密是否为有效的秘密值，如果不是有效的秘密值则进入下一轮继续交互，否则通过对秘密值的运算得出共享的秘密；具体步骤如下：

步骤D2-1：如果没有接收到某个参与者的子秘密，则在下一轮将该参与者从重构秘密的参与者集合中排除；

步骤D2-2：对其他参与者发送的信息中的签名进行验证，防止有参与者冒充其他参与者，若发现有冒充则在下一轮将冒充的参与者从重构秘密的参与者集合中排除；

步骤D2-3：计算并和公开的b_ij进行比较，若不相等则要求重新发送且次数不超过M次，否则在下一轮将参与者P_i从重构秘密的参与者集合中排除；若相等则接收到的S_ij与P_i提供一致；

步骤D2-4：计算并与公开的比较，若不一致则参与者P_i欺骗，则在下一轮将P_i从重构秘密的参与者集合中排除；

步骤D2-5：实际参与者人数为n'，若n'<t则终止协议；若n'≥t则重构出秘密值；取l=n!，在整数环Z上计算出再利用$>S_j=\underset{i=1}{\overset{t}{\Pi }}{S_{\mathrm{ij}}}^{{\alpha }_i}=\underset{i=1}{\overset{t}{\Pi }}{m_j}^{{\alpha }_i{d_i}^{\prime }}={m_j}^{\underset{i=1}{\overset{t}{\Sigma }}{\alpha }_i{d_i}^{\prime }}={m_j}^{l\underset{i=1}{\overset{t}{\Sigma }}{\beta }_i{d_i}^{\prime }}={m_j}^{\mathrm{ld}}\mathrm{mod}p$>计算出S_j，然后利用K_j'=T_j-m_j^ldmodp=T_j-S_j计算出共享秘密，若则得到秘密，若不相等则进入下一轮交互。

本发明的有益效果是：本发明提出了一种对诚实参与者公平的理性多秘密分享方法，所述方法包括系统参数设置模块、分发者认证模块、秘密分发模块、秘密重构模块；系统参数设置模块生成系统的公开参数以及分发者和参与者的公钥，公开参数发送给其他模块；分发者认证模块通过比特承诺协议验证分发者；秘密分发模块主要是分发者将子秘密分发给相应的参与者；秘密重构模块主要用于验证子秘密的正确性，并将具有欺骗行为的参与者从重构秘密的参与者集合中删除，并判断是否为有意义轮，从而重构出秘密。如果想要共享新的秘密，则只需要公开随机选取的参数和承诺值。此方案解决了对诚实参与者的不公平问题，并能高效的实现多秘密的分享。

附图说明

图1是本发明的结构图。

具体实施方式

下面结合附图，对本发明提出的一种对诚实参与者公平的理性多秘密分享方法进行详细说明：

如图1所示，依照本发明一种对诚实参与者公平的理性多秘密分享方法包括系统参数设置模块A、分发者认证模块B、秘密分发模块C、秘密重构模块D。

系统参数设置模块A用于生成系统的公开参数以及分发者和参与者的公钥，公开参数发送给分发者认证模块B、秘密分发模块C、秘密重构模块D；

分发者认证模块B通过比特承诺协议验证分发者防止分发者进行欺骗；

秘密分发模块C主要是分发者将子秘密分发给相应的参与者，且分发者分发正确秘密的概率为β；

秘密重构模块D主要用于验证子秘密的正确性，并将具有欺骗行为的参与者从重构秘密的参与者集合中删除，并判断是否为有意义轮，从而重构出秘密。

下面将结合一种对诚实参与者公平的理性多秘密分享方法的流程图对该方法中的各个模块的操作进行具体说明。

该方案的系统参数设置模块A执行以下步骤：

步骤A1：选择两个大素数p和q，满足q能整除(p-1)，选择非零模p剩余类环Z_p^*={1,2,…,p-2,p-1}，Z_p^*的生成元为g且满足g^q=1modp；选取一个正整数M，M为因网络错误允许最多发送的次数；公开参与者的公钥，用于验证其他参与者广播子秘密时发送的签名。

步骤A2：需要共享的秘密分别为K₁,K₂,…,K_r，r(r>0)为共享秘密的个数，随机选择r个随机数m₁,m₂,…,m_r，计算T_j=K_j-m_j^ld(j=1,2,…,r)，公布T_j、m_j和其中l=n!，d为实际共享的秘密值。

步骤A3：秘密分发者对n个参与者分别选取个n个互不相等的x_i∈Z_p(i=1,2,…,n)作为参与者的身份并公开，每个参与者用P_i(i=1,2,…,n)表示。

该分发者认证模块B执行以下步骤：

步骤B1：分发者向参与者P_i(i=1,2,…,n)随机发送两个字符串s_i1和s_i2(i=1,2,…,n)，计算H(s_i1||s_i2||x_i)并公开，其中H(·)为单向函数，||表示字符串级联。

步骤B2：参与者P_i(i=1,2,…,n)接收到分发者发送的s_i1和s_i2(i=1,2,…,n)，计算H(s_i1||s_i2||x_i)并与公开的H(s_i1||s_i2||x_i)进行比较，若不相等则承诺的信息不对，否则进入分配阶段。

该秘密分发模块C执行以下步骤：

秘密分发分为多轮执行，每一轮执行用L表示，分发者在每一轮都构造一个t-1次多项式f(x)=d'+a₁x+a₂x²+…+a_t-1x^t-1，在每一轮执行L中分发正确秘密的概率为β(0<β<1)，即d'=d的概率为β，d_i'=f(x_i)modp(i=1,2,…,n)为分发者分发给参与者P_i的子秘密，公开d、d'保密，其中d为真正的秘密值，d'为实际共享的秘密值；同时公开$>g^{L\left|\right|{d_i}^{\prime }}\mathrm{mod}p(i=\mathrm{1,2},···,n)$>和$>g^{S_{\mathrm{ij}}}=g^{{m_j}^{{d_i}^{\prime }}}\mathrm{mod}p(i=\mathrm{1,2},···,n;j=\mathrm{1,2},···,r).$>

该秘密重构模块D执行以下步骤：

步骤D1：参与者接收分发者分发的子秘密d_i'，通过承诺值验证是否与分发者分发的一样，然后计算$>S_{\mathrm{ij}}={m_j}^{{d_i}^{\prime }}\mathrm{mod}p(i=\mathrm{1,2},···,n;j=\mathrm{1,2},···,r),$>并对自己的身份进行签名sign(x_i)，将{x_i,sign(x_i),m_j,S_ij}发送给其他的参与者。

步骤D1具体步骤如下：

步骤D1-1：P_i将从分发者那接收到的子秘密d_i'进行计算与公开的比较，相同则接受d_i'，否则拒绝d_i'。

步骤D1-2：P_i计算$>S_{\mathrm{ij}}={m_j}^{{d_i}^{\prime }}\mathrm{mod}p(i=\mathrm{1,2},···,n;j=\mathrm{1,2},···,r).$>

步骤D1-3：选取$>c_{\mathrm{ij}}\in \left[n^{1+{\delta }_1+{\delta }_2}\right](i=\mathrm{1,2},···,n;j=\mathrm{1,2},···,r),$>其中δ₁,δ₂为安全参数且有0≤δ₁，δ₂≤1，计算b_ij=H(g,m_j,S_ij,W_i,w',m')，在整数环Z上计算y_ij=c_ij+b_ijd_i'(i=1,2,…,n;j=1,2,…,r)，P_i公开验证值：{y_ij,b_ij}。

步骤D1-4：参与者P_i广播{x_i,sign(x_i),m_j,S_ij}，其中sign(x_i)是对x_i的签名。

步骤D2：P_i接收其他参与者广播的子秘密，并用其他参与者公开的承诺值验证是否和其发送的子秘密相同，如果相同且参与者人数不小于t则重构秘密值，否则在下一轮将欺骗的参与者从重构秘密的参与者集合中排除；利用公开承诺值验证重构的秘密是否为有效的秘密值，如果不是有效的秘密值则进入下一轮继续交互，否则通过对秘密值的运算得出共享的秘密。

步骤D2具体步骤如下：

步骤D2-1：如果没有接收到某个参与者的子秘密，则在下一轮将该参与者从重构秘密的参与者集合中排除。

步骤D2-2：对其他参与者发送的信息中的签名进行验证，防止有参与者冒充其他参与者，若发现有冒充则在下一轮将冒充的参与者从重构秘密的参与者集合中排除。

步骤D2-3：计算并和公开的b_ij进行比较，若不相等则要求重新发送且次数不超过M次，否则在下一轮将参与者P_i从重构秘密的参与者集合中排除；若相等则接收到的S_ij与P_i提供一致。

步骤D2-4：计算并与公开的比较，若不一致则参与者P_i欺骗，则在下一轮将P_i从重构秘密的参与者集合中排除。

步骤D2-5：实际参与者人数为n'，若n'<t则终止协议；若n'≥t则重构出秘密值。取l=n!，在整数环Z上计算出再利用$>S_j=\underset{i=1}{\overset{t}{\Pi }}{S_{\mathrm{ij}}}^{{\alpha }_i}=\underset{i=1}{\overset{t}{\Pi }}{m_j}^{{\alpha }_i{d_i}^{\prime }}={m_j}^{\underset{i=1}{\overset{t}{\Sigma }}{\alpha }_i{d_i}^{\prime }}={m_j}^{l\underset{i=1}{\overset{t}{\Sigma }}{\beta }_i{d_i}^{\prime }}={m_j}^{\mathrm{ld}}\mathrm{mod}p$>计算出S_j，然后利用$>{K_j}^{\prime }=T_j-{m_j}^{\mathrm{ld}}\mathrm{mod}p=T_j-S_{\text{j}}$>计算出共享秘密，若$>G_j=g^{{K_j}^{\prime }}\mathrm{mod}p$>则得到秘密，若不相等则进入下一轮交互。

下面将如上所述的依照本发明的一种对诚实参与者公平的理性多秘密分享方法应用于密钥协商中的情形进行说明。

分布式的密钥生成是解决密钥协商的重要部分，运行多个参与者合作生成公钥和私钥，公钥公开，私钥被当作秘密进行共享，可拥有群组的密码系统。

在改进的分布式的密钥生成中参与者都是理性参与者，改进的分布式的密钥生成由以下步骤组成：

密钥生成：通过密钥生成协议生成相应的公钥pk_i(i>0)和私钥sk_i(i>0)，其中公钥pk_i公开，私钥sk_i则是需要共享的一个秘密。

系统参数设置：执行系统参数设置模块A中的算法，生成相应的公开参数T_j、m_j和其中K_j=sk_i，即将私钥sk_i作为需要共享的一个秘密。

分发者认证：分发者通过执行分发者认证模块B的算法，利用比特承诺协议对参与者进行认证。

秘密分发：分发者通过执行秘密分发模块C的算法，构造一个t-1次多项式f(x)=d+a₁x+a₂x²+…+a_t-1x^t-1，以概率β分发正确的秘密，并公开认证秘密的公开消息。

秘密重构：参与者执行秘密重构模块D的算法，利用系统公开参数对重构出的秘密的正确性进行验证，并同时将存在欺骗的参与者下一轮从重构秘密的参与者集合中排除，最后可以重构出秘密。

改进的分布式的密钥生成算法引入了理性参与者的概念，使更加接近现实生活，保证了诚实的参与者的公平性，并且实现了可动态增减的多秘密分享。

该技术领域的普通技术人员来说，根据以上实施类型可以联想到其他的优点和变形。所以本发明不局限于上述具体的实例，其仅仅是对本发明的一种具体的实施实例。在不背离本发明宗旨的范围内，该技术领域的普通技术人员可以根据上述实例进行等同替换所得到的技术方案应该包含在本发明的权利要求范围及其等同范围之内。