一个可验证的多秘密共享门限方案

吴星星，李志慧，李婧

陕西师范大学 数学与信息科学学院，西安 710062

一个可验证的多秘密共享门限方案

吴星星，李志慧，李婧

陕西师范大学 数学与信息科学学院，西安 710062

1 引言

秘密共享是信息安全中一个重要的研究课题，在密钥托管、电子商务、安全多方计算、导弹发射控制等诸多领域均有着广泛的应用。秘密共享最初由Shamir[1]和Blakky[2]于1979年各自独立提出，并分别给出了基于Lagrange插值多项式和射影几何理论的(t，n)门限秘密共享方案。但他们的方案不能防止秘密分发者和参与者的欺诈行为，而且参与者所得到的秘密份额只能使用一次，若有多个密钥需要同时共享时则需多次分发秘密份额。为了解决这些问题，研究人员提出了可验证的秘密共享方案[3-5]和多秘密共享方案[6-9]。

1995年，Ham[10]提出了一种可验证的多秘密共享方案，但在此方案中，为了验证秘密份额的正确性，要求参与者核对n!/((n-t)!t!)个方程，并且共享的密钥要被事先固定，这在实际应用中很难满足。2004年，Yang等人提出了一个简单有效的多秘密共享方案[8]（简称YCH方案），但该方案不能检测欺骗者。基于YCH方案，2005年，Shao等人[11]提出了一个新的可验证的多秘密共享方案，此方案可以检测欺骗者，但在参与者和分发者之间需要一个安全通道。2006年，Zhao等人[12]利用三次传输协议给出了一个可验证的多秘密共享方案，此方案不仅可以检测欺骗者，而且在参与者和分发者之间不再需要一个安全通道，从而克服了YCH方案的不足。但是，以上提出的可验证的多秘密共享方案都是(t，n)门限方案，即它的极小访问结构是由任意t个参与者的子集组成的，因此少于t个就无法获得任何一个密钥，这就大大降低了这些方案的实用性。

本文给出了一种新的可验证的多秘密共享门限方案，其访问结构不同于以上方案中的访问结构。假如要共享m个密钥s1，s2，…，sm，且每一个密钥si对应的极小访问结构定义为，若对于所有门限数有t1＜t2＜…＜tm，则t1个参与者只能恢复s1，ti个参与者就能恢复s1，s2，…si，其中i=2，3，…，m，参与重构的参与者越多可被重构的密钥就越多，因此此方案具有更强的实用性。

2 预备知识

这里给出与本文方案相关的一些基本概念的定义和定理。由于会利用双变量单向函数来隐藏秘密份额的信息，首先给出它的概念。

定义1[13]双变量单向函数f(r，s)将任意的r和s映射为一个固定长度的比特串。其中对应法则f必须满足如下性质：

（1）给定r和s，很容易计算f(r，s)；

（2）给出s和f(r，s)，很难计算r的值；

（3）不知道s，对任何r很难计算f(r，s)；

（4）给出s，很难找到两个不同的r1和r2，使得f(r1，s)=f(r2，s)；

（5）给出r和f(r，s)，很难计算s的值；

（6）给出ri和f(ri，s)这样的数对，也很难计算出f(r′，s)的值，其中r′≠ri。

定理1[14]设m是一个正整数，a是不能整除m的整数，则一次同余式ax≡b(modm)有解的充分必要条件是(a，m)|b，而且同余式有解时，其解数d=(a，m)。

3 方案的构成

在本方案中，访问结构不再是(t，n)门限，而是一种特殊的多秘密共享门限访问结构，实际上是由Shamir门限生成的。其具体结构如下[15]：令p是一个大素数，设P={P1，P2，…，Pn}是参与者集合，密钥空间分别为S1，S2，…，Sm，并且还有S1=S2=…=Sm=GF(p)。设Γ1，Γ2，…，Γm分别是密钥空间对应的极小访问结构，其中对于每一个极小访问结构Γj都存在一个正整数tj，使得Γj={A⊆P||A|=tj}，其中j=1，2，…，m，每一个密钥sj∈Sj通过极小访问结构Γj在P中被共享，并且对于i≠j，有Γi≠Γj。方案的对象除了上面定义的以外，还有秘密分发者D和一个公告牌，公告牌用于存取公开信息，该方案的参与者均可读取公告牌上的内容，但只有秘密分发者D才能发布或更新公告牌上的内容。

3.1 初始化阶段

在这一阶段，分发者和参与者分别执行如下步骤：

（1）分发者D对所有极小访问结构的门限数进行排序，使得t1＜t2＜…＜tm。

每一个参与者选取一个正整数si作为他们的秘密份额，然后把si代入f(r，s)，将计算后的f(r，si)发送给D，D收到f(r，si)后，要确保所有的f(r，si)不等，如果有相等的，就将这些值返回给相应的参与者让他们重新选择，直到收到的所有的伪秘密份额都不相等。

3.2 构造阶段

（1）分发者D构造一个tm-1次多项式：

h(x)的系数定义如下：首先在(0，M)上任意选t1-1个正整数作为系数a0，a1，…，at1-2，并定义。而对于剩下的系数ati，ati+1，…，，其中i=1，2，…，m-1，D可用以下方式来定义：令，其中j=ti，ti+1，…，ti+1-2，rj是任意选取的整数，bj∈{0，1，…，pi-1}。

根据上面的构造知aj≡0(modpk)，其中j≥tk,k=1,2,…, i-1，因此记

其中j=1，2，…，m。

（2）D计算yi=h(f(r，si))(modM)，i=1，2，…，n。

（3）D计算Gi=gf(r，si)(modp)，i=1，2，…，n。

（4）D在公告牌上公开G1，G2…，Gn，y1，y2，…yn。

3.3 重构阶段

参与者可根据需要重构部分密钥，假设有tj个参与者想要重构密钥s1，s2，…，sj，不妨设由参与者P1，P2，…，Ptj来重构。那么这tj个参与者就会提交出他们的伪秘密份额f(r，sk)，其中k=1，2，…，tj，在重构密钥之前，参与者Pi可使用下式来验证其他参与者提供的伪秘密份额的真实性：Gk=gf(r，sk)(modp)，其中k=1，2，…，tj，且k≠i。而且可由拉格朗日插值公式唯一确定多项式：

4 安全性分析

以上构造的方案的安全性，基于Shamir(t，n)门限秘密共享方案的安全性、有限域上离散对数的难解性以及双变量单向函数的保密性。

4.1 tj-1个或更少的参与者试图重构密钥sj

当tj-1个或更少的参与者试图重构密钥sj时，他们会采用以下两种方法来重构：

（1）利用Lagrange插值公式直接求解hj(x)。但由Shamir门限体制可知tj-1次多项式至少需要tj个不同的数值才能重构，所以任何tj-1或更少的参与者的合作不能重构多项式，同时也不可能获得任何和sj相关的信息，因此此方法不可能重构密钥sj。

（2）根据他们知道的伪秘密份额确定出多项式h1(x)，h2(x)，…，hj-1(x)，然后根据h1(x)，h2(x)，…，hj-1(x)的系数确定出hj(x)的部分系数，最后用他们的伪秘密份额通过待定系数法求解hj(x)的所有系数，这样就有可能重构出密钥sj。但在此方法中，tj-1或更少的参与者虽然可能会确定出多项式h1(x)，h2(x)，…，hj-1(x)，然后由此就能确定出系数a0modp1,…,a0modpj-1,a1modp1,…,a1modpj-1,…,modpj-1的值，但不能确定出a0modpj，a1modpj，…，modpj，也就是说他们确定不了hj(x)的任何一个系数，所以此方法不可能重构密钥sj。

4.2 恶意的参与者欺骗其他参与者

此方案是可验证的多秘密共享门限方案，因此每个参与者都可以验证其他参与者提交的伪秘密份额的真实性。假设参与者Pk提交一个不真实的伪秘密份额，那么参与者Pi就可以利用公式gf(r，sk)≡Gk(modp)来验证。因此参与者Pk想要成功地欺骗过其他参与者，他就要找到另一个f(r，s′k)，使得，并且有gf(r，s′k)≡gf(r，sk)(modp)。而g是GF(p)的一个生成元，因此这样的f(r，s′k)不存在，所以他就不可能成功地欺骗其他参与者。

4.3 其他参与者通过f(r，sj)和r来确定秘密份额sj

参与者选定了sj以后，利用公开的r和f(r，s)来计算自己的伪秘密份额f(r，sj)，重构密钥时将其提交，但是由双变量单向函数的性质，在知道f(r，sj)和r情况下，不能计算出sj的值，因此其他参与者不可能得到sj。

4.4 敌手E通过Gi来攻击f(r，si)

由于Gi=gf(r，si)modp，并且Gi是公开的，由离散对数的难解性，敌手E不可能由Gi和g得到f(r，si)的值。

从上面的分析可以看出，本方案是一个安全可验证的多秘密共享门限方案。

5 结束语

本文提出了一个安全有效的基于Shamir门限方案的可验证的多秘密共享门限方案。以前的可验证的多秘密共享大都是(t，n)门限方案，这些方案中只有不少于t个参与者同时提交其伪秘密份额才能恢复所有的密钥，而少于t个参与者就无法获得任何密钥的任何信息。本文方案可以根据实际的需要恢复需要的密钥，更具有实用性。该方案还有以下优点：（1）参与者的秘密份额是参与者自己选取的，因此可以防止庄家欺骗参与者。（2）参与者的秘密份额可以被重复使用，在更换所共享的密钥时无需重新选择秘密份额。（3）根据需要，多个密钥可以被同时恢复。（4）此方案实现了可验证的秘密共享，能有效防止成员欺诈。

[1]Shamir A.How to share a secret[J].Communication of the ACM，1979，22（11）：612-613.

[2]Blakley G.Safeguarding cryptographic keys[C]//Proc AFIPS 1979 Natl Conf，New York，USA，1979：313-317.

[3]Chor B，Goldwasser S，Micali S，et al.Verifiable secret sharing and achieving simultaneity in the presence of faults[C]//Proceeding of 26th IEEE Symposium on Foundations of Computer Science，1985：383-395.

[4]Feldman A.A practical scheme for non-interactive verifiable secret sharing[C]//Proceedings of 28th IEEE Symposium on Foundations of Computer Science，1987：427-437.

[5]Pedersen T P.Non-interactive and information theoretic secure verifiable secret sharing[C]//Proceedings of the CRYPTO’91，1991：129-139.

[6]Jackson W A，Martin K M，O’Keefe C M.On sharing many secrets[C]//Proceedings of the Asiacrypt’94，1994：42-54.

[7]Chien H Y，Jan J K，Tseng Y M.A practical（t，n）multi-secret sharing scheme[J].IEICE Transactions on Fundamentals，2000，E83-A（12）：2672-2675.

[8]YangC，Chang T，HwangM.A（t，n）multis-ecretsharing scheme[J].Applied Mathematics and Computation，2004，151：483-490.

[9]Pang L，Wang Y.A new（t，n）multi-secret sharing scheme based on Shamir’s secret sharing[J].Applied Mathematics and Computation，2005，167：840-848.

[10]Ham L.Efficient sharing（broad casting）of multiple secrets[J]. IEE Proc Comput Digit Tech，1995，142（3）：237-240.

[11]Shao J，Cao Z F.A new efficient（t，n）verifiable multi-secret sharing（VMSS）based on YCH scheme[J].Applied Mathematics and Computation，2005，168：135-140.

[12]Zhao J，Zhang J，Zhao R.A practical verifiable multi-secret sharing scheme[J].Computer Standards and Interfaces，2007，29（1）：138-141.

[13]Hadian Dehkordi M，Mashhadi S.New efficient and practical verifiable multi-secret sharingschemes[J].InformationSciences，2008，178：2264-2274.

[14]陈恭亮.信息安全数学基础[M].北京，清华大学出版社，2009.

[15]Chan C W，Chang C C.A scheme for threshold multi-secret sharing[J].AppliedMathematicsandComputation，2005，166：1-14.

WU Xingxing,LI Zhihui,LI Jing

College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710062,China

A threshold verifiable multi-secret sharing scheme is proposed,which is based on Shamir(t，n)-threshold scheme, modular arithmetic over finite field and the Lagrange interpolation polynomial.The minimum access structure of each secret is a threshold access structure.This access structure realizes that a part of secrets is recovered in the reconstruction phase,and the more participants there are,the more secrets can be recovered.Compared with the previous verifiable(t，n)-threshold multi-secret sharing scheme,this scheme is more practical.

multi-secret sharing;Shamir(t，n)-threshold secret sharing scheme;two-variable one-way function;discrete logarithm problem

利用Shamir(t，n)门限方案、有限域上的模运算和Lagrange插值多项式提出了一个可验证的多秘密共享门限方案。该方案中，每一个密钥对应的极小访问结构是一个门限访问结构，这样的访问结构实现了在重构阶段可重构部分密钥，而且重构的参与者越多可重构的密钥就越多；与以前的可验证的(t，n)门限多秘密共享方案相比，该方案更具有实用性。

多秘密共享；Shamir(t，n)门限方案；双变量单向函数；离散对数

A

TP309

10.3778/j.issn.1002-8331.1110-0628

WU Xingxing,LI Zhihui,LI Jing.Threshold verifiable multi-secret sharing scheme.Computer Engineering and Applications,2013,49（13）：65-67.

国家自然科学基金（No.60873119）。

吴星星（1987—），女，硕士研究生，主要研究领域为有限域，密码学；李志慧（1966—），女，通讯作者，博士，教授；李婧（1986—），女，硕士研究生。E-mail：wuxingxing1010@126.com

2011-11-03

2012-01-03

1002-8331（2013）13-0065-03

CNKI出版日期：2012-03-21http://www.cnki.net/kcms/detail/11.2127.TP.20120321.1738.052.html