基于雙線性對(duì)的秘密分享方案

摘 要:提出了一種新的基于雙線性對(duì)的門(mén)限秘密分享方案，并對(duì)其正確性、安全性和性能進(jìn)行了分析討論;該方案將分享者私鑰計(jì)算和秘密分發(fā)過(guò)程分離，秘密份額可以重新利用，具有更好的性能，更適合實(shí)際應(yīng)用。

關(guān)鍵詞:秘密分享; 雙線性對(duì); 密鑰更新

中圖分類號(hào):TN918 文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)03-1045-02

doi:10.3969/j.issn.1001-3695.2010.03.066

Secret sharing scheme based on bilinear pairings

BAI Qin-xi1， HUANG Chong-chao2， LIUFeng1

(1.School of Mathematics Information， Ludong University， YantaiShandong264025， China;

2. School of Mathematics Statistics， Wuhan University， Wuhan 430072， China)

Abstract:This paper proposed a new secret sharing scheme based on the bilinear parings. And discussed its correctness， security and performance. At the same time， the proposed scheme departs the private keys of participants computation from the secret distribution process， which made this scheme more secure and more efficient. Therefore， the proposed scheme is more applicable than the existing ones.

Key words:secret sharing; bilinear pairings; key updating

0 引言

秘密分享(secret sharing)是信息安全和數(shù)據(jù)保密中的一項(xiàng)重要技術(shù)， 它在重要信息和秘密數(shù)據(jù)的安全保存、傳輸及合法利用中起著非常關(guān)鍵的作用。秘密分享的概念最早是由 Shamir[1] 和 Blakley[2]獨(dú)立提出?；镜拿孛芊窒矸桨赣擅孛芊蓊~的分配算法和秘密的恢復(fù)算法構(gòu)成。

當(dāng)前對(duì)于秘密分享的研究主要集中在可驗(yàn)證秘密分享、多秘密分享、秘密份額的有效分發(fā)、秘密分享的信息率等方面[3]，除此之外，基于新的設(shè)計(jì)思想和數(shù)學(xué)模型來(lái)設(shè)計(jì)秘密分享方案[4~8]也是一個(gè)研究熱點(diǎn)。

隨著雙線性對(duì)在公鑰密碼方面的成功應(yīng)用，利用雙線性變換構(gòu)造新型的秘密分享方案是一種新的嘗試。這種嘗試是合理的，因?yàn)閺膹V義上看，秘密分享方案也是一個(gè)特殊的公鑰算法，即由一個(gè)秘密分發(fā)者加密(加密密鑰為秘密分發(fā)者私鑰)，由符合條件的一組秘密分享者解密(解密密鑰為分享解密行為的各分享者私鑰或稱秘密份額)。

鑒于以上考慮，本文在Shamir門(mén)限秘密分享方案基礎(chǔ)上提出一種基于雙線性對(duì)的秘密分享方案，并分析了此方案的性能。該方案除了能夠?qū)崿F(xiàn)秘密分享系統(tǒng)的基本功能外，相對(duì)于現(xiàn)有方案，還具有一些新特性，使得其安全性和效率更好，更適合于實(shí)際應(yīng)用。

1 基礎(chǔ)知識(shí)

1.1 雙線性變換

定義 雙線性變換。設(shè)(G1，+)和(G2，#8226;)是兩個(gè)階為素?cái)?shù)p的循環(huán)群。其中前者為加法群，后者為乘法群。令g為G1的生成元。如果滿足以下性質(zhì)，則稱變換e:G1×G1→G2為雙線性變換:

a)雙線性。對(duì)任意P1、P2 和Q∈G1，有

e(P1+P2，Q)=e(P1，Q)e(P2，Q)

e(Q，P1+P2)=e(Q，P1)e(Q，P2)

b)非退化性。存在g∈G1 即e(g，g)≠1，也就是說(shuō)e(g，g)是G2的生成元。

c)可計(jì)算性。對(duì)任意P1、P2∈G1，存在有效的算法計(jì)算e(P1，P2)。

1.2 Shamir秘密分享方案

Shamir方案由系統(tǒng)初始化、秘密的分發(fā)、秘密的恢復(fù)三個(gè)階段組成。

1.2.1 系統(tǒng)初始化

秘密分發(fā)者SD選擇如下系統(tǒng)參數(shù):

a)SD從ZP中選取n個(gè)不同的非零元IDi，并將IDi分配給秘密分享者Pi(1≤i≤n)，作為Pi的身份標(biāo)志符。

b)SD在公布欄NB中公布信息{p，IDi}。

1.2.2 秘密的分發(fā)階段

1)SD隨機(jī)選擇一個(gè)次數(shù)為t-1的秘密多項(xiàng)式f(x)=a0+a1x+…+at-1xt-1。

2)SD為系統(tǒng)每一個(gè)秘密分享者Pi計(jì)算其秘密份額xi=f(IDi)， SD將參與者的秘密份額xi通過(guò)一條安全信道發(fā)送給相應(yīng)的秘密參與者。

1.2.3 秘密的恢復(fù)

不失一般性， 若前t個(gè)參與者合作想要恢復(fù)秘密s，則他們都給出自己相應(yīng)的身份標(biāo)志符IDi和秘密分享份額xi(1≤i≤t)。利用{(IDi，xi)|i=1，2，…，t}t個(gè)點(diǎn)，以及Lagrange插值公式構(gòu)造如下多項(xiàng)式:

f(x)=∑ti=1f(IDi)∏tj≠ix-IDjI(xiàn)Di-IDj=∑ti=1xi∏tj≠ix-IDjI(xiàn)Di-IDj

從而得到s=f(0)=a0， 即可恢復(fù)秘密s。

2 雙線性對(duì)秘密分享方案

設(shè)(G1，+)和(G2，#8226;)是兩個(gè)階為素?cái)?shù)p的循環(huán)群。其中前者為加法群，后者為乘法群。且滿足G1中Diffie-Hellman計(jì)算問(wèn)題為困難問(wèn)題。令g為G1的生成元;令e為G1和G2上的雙線性變換， 即e:G1×G1→G2 ;令w為包括n個(gè)參與者的集合。本文提出的秘密分享方案包括以下三部分。

2.1 系統(tǒng)建立過(guò)程

系統(tǒng)建立過(guò)程由秘密分發(fā)者執(zhí)行，主要用于建立系統(tǒng)公鑰和秘密分發(fā)者的私鑰。

令w={P1，P2，…，Pn}，其中IDi(i=1，2，…，n)是Pi(1≤i≤n)的身份標(biāo)志符，是不等于零的正整數(shù)。不同的分享者Pi身份標(biāo)志符IDi互不相同，即i≠j時(shí)，IDi≠I(mǎi)Dj。分發(fā)者隨機(jī)地選取x∈zp作為私鑰，令y=xg為系統(tǒng)的公鑰。

2.2 秘密分發(fā)過(guò)程

為了在這n個(gè)分享者集合W中分享秘密信息m∈G2，使得至少t個(gè)分享者合作才可以重構(gòu)秘密， 秘密分發(fā)者可以執(zhí)行如下過(guò)程:

a)分發(fā)者隨機(jī)選擇一個(gè)次數(shù)為t-1的秘密多項(xiàng)式f(x)=a0+a1x+…+at-1xt-1，為系統(tǒng)每一個(gè)秘密分享者Pi計(jì)算其秘密份額xi=f(IDi)，SD將分享者的秘密份額xi通過(guò)一條安全信道發(fā)送給相應(yīng)的秘密分享者作為私鑰。

b)分發(fā)者隨意選取k∈Zp計(jì)算

s=a0gl=l(kg+xs)a-10v=me(g，kg)(1)

然后將s銷毀， 將l、v以廣播的形式公開(kāi)。

2.3 秘密重構(gòu)過(guò)程

對(duì)于任意階數(shù)為t的分享者集合都可以恢復(fù)秘密，假設(shè)前t個(gè)分享者合作恢復(fù)秘密，將t個(gè)人的私鑰xi、IDi匯集，通過(guò)以下方法可得到

m=v∏ti=1e(y，xig)e(xig，l)∏tj≠i-IDjI(xiàn)Di-IDj(2)

下面證明式(2)的正確性。

證明 由式(1)知，e(s，l)=e(a0g，(kg+xs)a-10)=e(g，kg+xs)=e(g，kg)e(g，xs)=e(g，kg)e(xg，s)=e(g，kg)e(y，s)，所以e(g，kg)-1=e(y，s)e(s，l)。

由式(1)的第一個(gè)式子和Shamir門(mén)限秘密分享方案可知:

s=a0g=∑ti=1f(IDi)∏tj≠i-IDiI(xiàn)Di-IDjg;

e(g，kg)-1=e(y，s)e(s，l)=e(y，∑ti=1f(I(xiàn)Di)∏tj≠i-IDiI(xiàn)Di-IDjg)e(∑ti=1f(IDi)∏tj≠i-IDiI(xiàn)Di-IDjg，l)=∏ti=1e(y，f(IDi)∏ti=1-IDiI(xiàn)Di-IDjg)∏ti=1e(f(IDi)∏ti=1-IDiI(xiàn)Di-IDjg，l)=∏ti=1e(y，f(IDi)g)e(f(IDi)g，l)∏ti≠j-IDiI(xiàn)Di-IDj

由式(1)的第三個(gè)式子得

m=v#8226;e(g，kg)-1=v#8226;∏ti=1e(y，f(IDi)g)e(f(I(xiàn)Di)g，l)∏tj≠i-IDiI(xiàn)Di-IDj

由此可見(jiàn)，式(2)正確。

3 安全與性能分析

3.1 安全性

攻擊1 w中某不良成員Pj企圖在秘密份額分發(fā)的階段獲取SD對(duì)秘密享有的秘密份額x。 不良成員不可能從公布欄中公布的公鑰y=xg中計(jì)算出x。 因?yàn)楣P者知道離散對(duì)數(shù)問(wèn)題是NP完全問(wèn)題，當(dāng)p是一個(gè)大素?cái)?shù)時(shí)，求解離散對(duì)數(shù)被認(rèn)為是不可行的，從而保證了方案的安全性，并且攻擊者也不可能從l=(kg+xs)a-10，v=me(g，kg)中計(jì)算出x。

攻擊2 當(dāng)某個(gè)秘密分享者Pi的秘密份額xi意外泄露時(shí)，秘密分發(fā)者只需要重新為秘密分享者選擇身份標(biāo)志符IDi(與之前所選取的身份標(biāo)志符不同)，計(jì)算新的秘密份額xi=f(IDi)并將其發(fā)送給分享者，當(dāng)然其他分享者的秘密份額無(wú)須改變。

3.2 性能分析

本節(jié)主要從可行性、秘密份額的重復(fù)利用性、成員的增加、存儲(chǔ)和通信等方面來(lái)分析。

從可行性來(lái)看，在秘密恢復(fù)階段，當(dāng)秘密參與者Pi從公告欄NB中下載到身份標(biāo)志IDi后，提供出自己對(duì)秘密持有的秘密份額xi，然后根據(jù)公開(kāi)的l、v和式(2)即可恢復(fù)出秘密m，這樣就可以實(shí)現(xiàn)秘密的分享。

從秘密份額的重復(fù)利用性來(lái)看，對(duì)于另一個(gè)秘密m′∈G2，由于秘密的恢復(fù)與所選取的多項(xiàng)式是獨(dú)立的，秘密分享者只需修改l，v為l′、v′，對(duì)于已經(jīng)分發(fā)過(guò)的秘密份額xi，可以重復(fù)利用而無(wú)須收回、銷毀或修改。該方案秘密可以更新，秘密份額可以重新利用，所以是一個(gè)動(dòng)態(tài)的秘密分享方案。

假設(shè)有新成員IDj加入到系統(tǒng)中，秘密分發(fā)者只需利用多項(xiàng)式計(jì)算出新成員的私鑰xj=f(I(xiàn)Dj)，其他秘密分享者不變動(dòng)而使得整個(gè)方案重新執(zhí)行。

從存儲(chǔ)量來(lái)看，系統(tǒng)存儲(chǔ)量包括公開(kāi)信息大小和需要保密的秘密信息大小。對(duì)于秘密分發(fā)者來(lái)說(shuō)，需要保密的信息僅為私鑰y;對(duì)于每個(gè)分享者來(lái)說(shuō)，需要保密的信息同樣僅為其私鑰，其私鑰xi長(zhǎng)度與所共享秘密m的長(zhǎng)度相同，不會(huì)給系統(tǒng)造成過(guò)大的存儲(chǔ)負(fù)擔(dān)，因此，本文方案也是一個(gè)理想的方案。

從通信性能上來(lái)看，除了為分享者計(jì)算私鑰時(shí)需要點(diǎn)對(duì)點(diǎn)的單播通信外，其余信息都可以通過(guò)廣播形式進(jìn)行傳遞。眾所周知，廣播是最有效、最節(jié)約能量的通信方式，而本文方案可以有效地利用廣播通信方式， 因此具有較好的通信性能。

從實(shí)現(xiàn)過(guò)程上來(lái)看，與現(xiàn)有大多數(shù)方案相比，本文方案還有一個(gè)特點(diǎn)，就是分享者私鑰(或秘密份額)的計(jì)算與秘密分發(fā)過(guò)程是分離的。本文以文獻(xiàn)[1]的方案為代表與本文方案作一比較。文獻(xiàn)[1]的方案包含三個(gè)過(guò)程，即系統(tǒng)參數(shù)建立、秘密分發(fā)和秘密重構(gòu)過(guò)程。其中秘密分發(fā)過(guò)程融合了分享者私鑰的計(jì)算。在本文方案中，因?yàn)榉窒碚咚借€計(jì)算可以預(yù)處理完成，而在分發(fā)秘密時(shí)，只需要一次廣播即可;而文獻(xiàn)[1]的方案事先無(wú)法預(yù)計(jì)算分享者私鑰，只能在秘密分發(fā)過(guò)程中逐一安全發(fā)送，所以本文方案秘密分發(fā)效率更高。另外，在文獻(xiàn)[1]的方案中，只要給分享者分發(fā)了私鑰，就無(wú)法撤銷所分享的秘密;而在本文方案中，秘密分發(fā)者還有權(quán)決定是否要分享某個(gè)秘密，因此，本文方案從秘密分發(fā)效率和安全性上更適合應(yīng)用。

4 結(jié)束語(yǔ)

本文基于雙線性變換構(gòu)建了一個(gè)新的秘密分享方案。該方案將分享者私鑰計(jì)算與秘密分發(fā)過(guò)程分離，可以重復(fù)利用秘密份額，是一個(gè)動(dòng)態(tài)的秘密分享方案。本文方案是一個(gè)可證明安全的、有效的秘密分享方案，比現(xiàn)有方案更具安全性和有效性，更適合實(shí)際應(yīng)用。

參考文獻(xiàn):

[1]SHAMIR A. How to share a secret [J]. Communications of the ACM， 1979， 24(11):612-613.

[2]BLAKLEY G. Safeguarding cryptographic key[C]//Proc of AFIPS 1979 National Computer Conference.1979:313-317.

[3]JEFFERS J， ARAKALA A. Minutiae-based structures for a fuzzy vault[C]//Proc of IEEE Biometrics Symposium.2006:760-769.

[4]劉鋒，何業(yè)鋒，程學(xué)翰. 動(dòng)態(tài)的(t，n)門(mén)限多秘密分享方案[J]. 計(jì)算機(jī)應(yīng)用研究， 2008，25(1):240-241.

[5]ASMUTH C， BLOOM J. A modular approach to key safeguarding[J]. IEEE Trans on Information Theory， 1983， 29(2): 208-210.

[6]KARNIN E D， GREENE J W， HELLMAN M E. On sharing secret systems[J]. IEEE Trans on Information Theory， 1983， 29(1): 35-41.

[7]龐遼軍， 王育民.一個(gè)基于幾何性質(zhì)的(t， n)多重秘密共享方案 [J]. 西安交通大學(xué)學(xué)報(bào)， 2005， 39(4): 425-428.

[8]BONEH D， FRANKLIN M. Identity-based encryption from the Weil pairing[J]. SIAM Journal of Computation， 2003， 32(3): 586-615.