吳星星，李志慧，李婧

陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710062

一個(gè)可驗(yàn)證的多秘密共享門限方案

吳星星，李志慧，李婧

陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710062

1 引言

秘密共享是信息安全中一個(gè)重要的研究課題，在密鑰托管、電子商務(wù)、安全多方計(jì)算、導(dǎo)彈發(fā)射控制等諸多領(lǐng)域均有著廣泛的應(yīng)用。秘密共享最初由Shamir[1]和Blakky[2]于1979年各自獨(dú)立提出，并分別給出了基于Lagrange插值多項(xiàng)式和射影幾何理論的(t，n)門限秘密共享方案。但他們的方案不能防止秘密分發(fā)者和參與者的欺詐行為，而且參與者所得到的秘密份額只能使用一次，若有多個(gè)密鑰需要同時(shí)共享時(shí)則需多次分發(fā)秘密份額。為了解決這些問題，研究人員提出了可驗(yàn)證的秘密共享方案[3-5]和多秘密共享方案[6-9]。

1995年，Ham[10]提出了一種可驗(yàn)證的多秘密共享方案，但在此方案中，為了驗(yàn)證秘密份額的正確性，要求參與者核對(duì)n!/((n-t)!t!)個(gè)方程，并且共享的密鑰要被事先固定，這在實(shí)際應(yīng)用中很難滿足。2004年，Yang等人提出了一個(gè)簡單有效的多秘密共享方案[8]（簡稱YCH方案），但該方案不能檢測欺騙者?；赮CH方案，2005年，Shao等人[11]提出了一個(gè)新的可驗(yàn)證的多秘密共享方案，此方案可以檢測欺騙者，但在參與者和分發(fā)者之間需要一個(gè)安全通道。2006年，Zhao等人[12]利用三次傳輸協(xié)議給出了一個(gè)可驗(yàn)證的多秘密共享方案，此方案不僅可以檢測欺騙者，而且在參與者和分發(fā)者之間不再需要一個(gè)安全通道，從而克服了YCH方案的不足。但是，以上提出的可驗(yàn)證的多秘密共享方案都是(t，n)門限方案，即它的極小訪問結(jié)構(gòu)是由任意t個(gè)參與者的子集組成的，因此少于t個(gè)就無法獲得任何一個(gè)密鑰，這就大大降低了這些方案的實(shí)用性。

本文給出了一種新的可驗(yàn)證的多秘密共享門限方案，其訪問結(jié)構(gòu)不同于以上方案中的訪問結(jié)構(gòu)。假如要共享m個(gè)密鑰s1，s2，…，sm，且每一個(gè)密鑰si對(duì)應(yīng)的極小訪問結(jié)構(gòu)定義為，若對(duì)于所有門限數(shù)有t1＜t2＜…＜tm，則t1個(gè)參與者只能恢復(fù)s1，ti個(gè)參與者就能恢復(fù)s1，s2，…si，其中i=2，3，…，m，參與重構(gòu)的參與者越多可被重構(gòu)的密鑰就越多，因此此方案具有更強(qiáng)的實(shí)用性。

2 預(yù)備知識(shí)

這里給出與本文方案相關(guān)的一些基本概念的定義和定理。由于會(huì)利用雙變量單向函數(shù)來隱藏秘密份額的信息，首先給出它的概念。

定義1[13]雙變量單向函數(shù)f(r，s)將任意的r和s映射為一個(gè)固定長度的比特串。其中對(duì)應(yīng)法則f必須滿足如下性質(zhì)：

（1）給定r和s，很容易計(jì)算f(r，s)；

（2）給出s和f(r，s)，很難計(jì)算r的值；

（3）不知道s，對(duì)任何r很難計(jì)算f(r，s)；

（4）給出s，很難找到兩個(gè)不同的r1和r2，使得f(r1，s)=f(r2，s)；

（5）給出r和f(r，s)，很難計(jì)算s的值；

（6）給出ri和f(ri，s)這樣的數(shù)對(duì)，也很難計(jì)算出f(r′，s)的值，其中r′≠ri。

定理1[14]設(shè)m是一個(gè)正整數(shù)，a是不能整除m的整數(shù)，則一次同余式ax≡b(modm)有解的充分必要條件是(a，m)|b，而且同余式有解時(shí)，其解數(shù)d=(a，m)。

3 方案的構(gòu)成

在本方案中，訪問結(jié)構(gòu)不再是(t，n)門限，而是一種特殊的多秘密共享門限訪問結(jié)構(gòu)，實(shí)際上是由Shamir門限生成的。其具體結(jié)構(gòu)如下[15]：令p是一個(gè)大素?cái)?shù)，設(shè)P={P1，P2，…，Pn}是參與者集合，密鑰空間分別為S1，S2，…，Sm，并且還有S1=S2=…=Sm=GF(p)。設(shè)Γ1，Γ2，…，Γm分別是密鑰空間對(duì)應(yīng)的極小訪問結(jié)構(gòu)，其中對(duì)于每一個(gè)極小訪問結(jié)構(gòu)Γj都存在一個(gè)正整數(shù)tj，使得Γj={A?P||A|=tj}，其中j=1，2，…，m，每一個(gè)密鑰sj∈Sj通過極小訪問結(jié)構(gòu)Γj在P中被共享，并且對(duì)于i≠j，有Γi≠Γj。方案的對(duì)象除了上面定義的以外，還有秘密分發(fā)者D和一個(gè)公告牌，公告牌用于存取公開信息，該方案的參與者均可讀取公告牌上的內(nèi)容，但只有秘密分發(fā)者D才能發(fā)布或更新公告牌上的內(nèi)容。

3.1 初始化階段

在這一階段，分發(fā)者和參與者分別執(zhí)行如下步驟：

（1）分發(fā)者D對(duì)所有極小訪問結(jié)構(gòu)的門限數(shù)進(jìn)行排序，使得t1＜t2＜…＜tm。

每一個(gè)參與者選取一個(gè)正整數(shù)si作為他們的秘密份額，然后把si代入f(r，s)，將計(jì)算后的f(r，si)發(fā)送給D，D收到f(r，si)后，要確保所有的f(r，si)不等，如果有相等的，就將這些值返回給相應(yīng)的參與者讓他們重新選擇，直到收到的所有的偽秘密份額都不相等。

3.2 構(gòu)造階段

（1）分發(fā)者D構(gòu)造一個(gè)tm-1次多項(xiàng)式：

h(x)的系數(shù)定義如下：首先在(0，M)上任意選t1-1個(gè)正整數(shù)作為系數(shù)a0，a1，…，at1-2，并定義。而對(duì)于剩下的系數(shù)ati，ati+1，…，，其中i=1，2，…，m-1，D可用以下方式來定義：令，其中j=ti，ti+1，…，ti+1-2，rj是任意選取的整數(shù)，bj∈{0，1，…，pi-1}。

根據(jù)上面的構(gòu)造知aj≡0(modpk)，其中j≥tk,k=1,2,…, i-1，因此記

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

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

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

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

3.3 重構(gòu)階段

參與者可根據(jù)需要重構(gòu)部分密鑰，假設(shè)有tj個(gè)參與者想要重構(gòu)密鑰s1，s2，…，sj，不妨設(shè)由參與者P1，P2，…，Ptj來重構(gòu)。那么這tj個(gè)參與者就會(huì)提交出他們的偽秘密份額f(r，sk)，其中k=1，2，…，tj，在重構(gòu)密鑰之前，參與者Pi可使用下式來驗(yàn)證其他參與者提供的偽秘密份額的真實(shí)性：Gk=gf(r，sk)(modp)，其中k=1，2，…，tj，且k≠i。而且可由拉格朗日插值公式唯一確定多項(xiàng)式：

4 安全性分析

以上構(gòu)造的方案的安全性，基于Shamir(t，n)門限秘密共享方案的安全性、有限域上離散對(duì)數(shù)的難解性以及雙變量單向函數(shù)的保密性。

4.1 tj-1個(gè)或更少的參與者試圖重構(gòu)密鑰sj

當(dāng)tj-1個(gè)或更少的參與者試圖重構(gòu)密鑰sj時(shí)，他們會(huì)采用以下兩種方法來重構(gòu)：

（1）利用Lagrange插值公式直接求解hj(x)。但由Shamir門限體制可知tj-1次多項(xiàng)式至少需要tj個(gè)不同的數(shù)值才能重構(gòu)，所以任何tj-1或更少的參與者的合作不能重構(gòu)多項(xiàng)式，同時(shí)也不可能獲得任何和sj相關(guān)的信息，因此此方法不可能重構(gòu)密鑰sj。

（2）根據(jù)他們知道的偽秘密份額確定出多項(xiàng)式h1(x)，h2(x)，…，hj-1(x)，然后根據(jù)h1(x)，h2(x)，…，hj-1(x)的系數(shù)確定出hj(x)的部分系數(shù)，最后用他們的偽秘密份額通過待定系數(shù)法求解hj(x)的所有系數(shù)，這樣就有可能重構(gòu)出密鑰sj。但在此方法中，tj-1或更少的參與者雖然可能會(huì)確定出多項(xiàng)式h1(x)，h2(x)，…，hj-1(x)，然后由此就能確定出系數(shù)a0modp1,…,a0modpj-1,a1modp1,…,a1modpj-1,…,modpj-1的值，但不能確定出a0modpj，a1modpj，…，modpj，也就是說他們確定不了hj(x)的任何一個(gè)系數(shù)，所以此方法不可能重構(gòu)密鑰sj。

4.2 惡意的參與者欺騙其他參與者

此方案是可驗(yàn)證的多秘密共享門限方案，因此每個(gè)參與者都可以驗(yàn)證其他參與者提交的偽秘密份額的真實(shí)性。假設(shè)參與者Pk提交一個(gè)不真實(shí)的偽秘密份額，那么參與者Pi就可以利用公式gf(r，sk)≡Gk(modp)來驗(yàn)證。因此參與者Pk想要成功地欺騙過其他參與者，他就要找到另一個(gè)f(r，s′k)，使得，并且有g(shù)f(r，s′k)≡gf(r，sk)(modp)。而g是GF(p)的一個(gè)生成元，因此這樣的f(r，s′k)不存在，所以他就不可能成功地欺騙其他參與者。

4.3 其他參與者通過f(r，sj)和r來確定秘密份額sj

參與者選定了sj以后，利用公開的r和f(r，s)來計(jì)算自己的偽秘密份額f(r，sj)，重構(gòu)密鑰時(shí)將其提交，但是由雙變量單向函數(shù)的性質(zhì)，在知道f(r，sj)和r情況下，不能計(jì)算出sj的值，因此其他參與者不可能得到sj。

4.4 敵手E通過Gi來攻擊f(r，si)

由于Gi=gf(r，si)modp，并且Gi是公開的，由離散對(duì)數(shù)的難解性，敵手E不可能由Gi和g得到f(r，si)的值。

從上面的分析可以看出，本方案是一個(gè)安全可驗(yàn)證的多秘密共享門限方案。

5 結(jié)束語

本文提出了一個(gè)安全有效的基于Shamir門限方案的可驗(yàn)證的多秘密共享門限方案。以前的可驗(yàn)證的多秘密共享大都是(t，n)門限方案，這些方案中只有不少于t個(gè)參與者同時(shí)提交其偽秘密份額才能恢復(fù)所有的密鑰，而少于t個(gè)參與者就無法獲得任何密鑰的任何信息。本文方案可以根據(jù)實(shí)際的需要恢復(fù)需要的密鑰，更具有實(shí)用性。該方案還有以下優(yōu)點(diǎn)：（1）參與者的秘密份額是參與者自己選取的，因此可以防止莊家欺騙參與者。（2）參與者的秘密份額可以被重復(fù)使用，在更換所共享的密鑰時(shí)無需重新選擇秘密份額。（3）根據(jù)需要，多個(gè)密鑰可以被同時(shí)恢復(fù)。（4）此方案實(shí)現(xiàn)了可驗(yàn)證的秘密共享，能有效防止成員欺詐。

[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]陳恭亮.信息安全數(shù)學(xué)基礎(chǔ)[M].北京，清華大學(xué)出版社，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)門限方案、有限域上的模運(yùn)算和Lagrange插值多項(xiàng)式提出了一個(gè)可驗(yàn)證的多秘密共享門限方案。該方案中，每一個(gè)密鑰對(duì)應(yīng)的極小訪問結(jié)構(gòu)是一個(gè)門限訪問結(jié)構(gòu)，這樣的訪問結(jié)構(gòu)實(shí)現(xiàn)了在重構(gòu)階段可重構(gòu)部分密鑰，而且重構(gòu)的參與者越多可重構(gòu)的密鑰就越多；與以前的可驗(yàn)證的(t，n)門限多秘密共享方案相比，該方案更具有實(shí)用性。

多秘密共享；Shamir(t，n)門限方案；雙變量單向函數(shù)；離散對(duì)數(shù)

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.

國家自然科學(xué)基金（No.60873119）。

吳星星（1987—），女，碩士研究生，主要研究領(lǐng)域?yàn)橛邢抻?，密碼學(xué)；李志慧（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