蔡兆政，瞿云云，包小敏

1. 西南大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶 400715；2. 重慶市第十八中學(xué)，重慶 400020；3. 貴州師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，貴陽 550001

秘密共享的概念最早由文獻(xiàn)[1-2]提出． 文獻(xiàn)[1]利用拉格朗日插值多項(xiàng)式構(gòu)造了一個門限秘密共享方案，其主要思想是二維平面內(nèi)任意t個點(diǎn)都可唯一確定一個t-1次多項(xiàng)式． 任何t個及t個以上的參與者聯(lián)合可以重構(gòu)多項(xiàng)式，得到的常數(shù)項(xiàng)即為分享的秘密． 反之，任何小于t個參與者的集合不能重構(gòu)多項(xiàng)式，從而不能獲得秘密． 文獻(xiàn)[2]利用線性投影幾何原理的性質(zhì)構(gòu)造的門限方案，t個t-1維超平面可以確定t維空間中一個點(diǎn)，但小于t個是無法確定的． 這兩個經(jīng)典的門限秘密共享方案為研究不同訪問結(jié)構(gòu)(access structure)上的秘密共享奠定了基礎(chǔ)[3]． 文獻(xiàn)[4]提出了基于中國剩余定理的門限秘密共享方案，秘密份額是秘密的同余類，滿足t個同余方程的解在取值范圍中是唯一的，少于t個方程，解無法確定． 文獻(xiàn)[5]利用矩陣乘法構(gòu)造了一個秘密共享方案，其原理等價于解含有t個未知數(shù)的線性方程組，每個共享份額相當(dāng)于一個線性方程，任意大于等于t個份額聯(lián)立可以求得t個未知數(shù)，而其中的一個未知數(shù)恰為分享的秘密，當(dāng)方程個數(shù)小于未知數(shù)個數(shù)的時候無法確定方程組的解，從而不能恢復(fù)共享的秘密． 上述幾種構(gòu)造秘密共享方案的方法是最常用的幾種方法，此外，文獻(xiàn)[6]中指出，一個RS碼對應(yīng)一個秘密共享方案． 文獻(xiàn)[7]利用糾錯碼巧妙構(gòu)造了一個秘密共享門限方案，該方案是一個(l，t+l)門限秘密共享方案，可以共享多個秘密．

任何在實(shí)際中應(yīng)用的密碼方案及其算法都應(yīng)該具有抵抗攻擊的能力，Shamir秘密共享方案[1]和其他秘密共享方案是在秘密分發(fā)者和參與者都可信的前提假設(shè)下設(shè)計(jì)的，這樣就導(dǎo)致了秘密共享方案在實(shí)際應(yīng)用場景中存在很多安全隱患． 例如內(nèi)部的參與者為了獲得其他參與者的份額而提供假的份額；或者由于受信道中噪音的干擾等導(dǎo)致份額在通信過程中出現(xiàn)錯誤；又或者外部攻擊者冒充授權(quán)的參與者進(jìn)行欺詐；另外，秘密分發(fā)者也可能存在欺詐行為． 這些情況都會導(dǎo)致秘密無法重構(gòu)或者重構(gòu)的秘密錯誤． 為了解決這些問題，許多學(xué)者提出了可驗(yàn)證的秘密共享方案．

1985年，文獻(xiàn)[8]提出了可驗(yàn)證秘密共享(verifiable secret sharing，VSS)的概念，其方法是在通常的秘密共享方案中添加一個驗(yàn)證算法，這樣份額持有者就能驗(yàn)證自己的份額與分發(fā)者分發(fā)的份額是否一致． 驗(yàn)證方式有交互式和非交互式兩種． 隨后，其他研究者提出了一系列的可驗(yàn)證的秘密共享方案，文獻(xiàn)[9]構(gòu)造了一個非交互式的VSS方案． 在VSS方案的基礎(chǔ)之上，文獻(xiàn)[10]提出了可公開驗(yàn)證秘密共享(publicly verifiable secret sharing，PVSS)的思想，不僅僅內(nèi)部參與者可以驗(yàn)證份額的有效性，非參與者也可以驗(yàn)證． 1999年，文獻(xiàn)[11]設(shè)計(jì)了一個更完善的非交互的PVSS方案，方案中有兩次非交互驗(yàn)證． 第一次是驗(yàn)證秘密分發(fā)者分發(fā)的加密的秘密份額，第二次是驗(yàn)證參與者解密后的秘密份額；前者可以預(yù)防秘密分發(fā)者的欺騙行為和通信中的錯誤，后者可以防止參與者之間的欺詐行為． 這樣確保了秘密份額的有效性，避免了由于份額錯誤而產(chǎn)生不必要的計(jì)算． 本文也采用兩次驗(yàn)證的思想．

在秘密共享中另外一個需要著重考慮的問題就是方案的效率，主要考慮數(shù)據(jù)傳輸量和計(jì)算量． 若秘密分發(fā)者和參與者之間使用一次一密的方式共享秘密，雖然安全性得以保證，但是在效率和成本上都有欠缺． 例如在Shamir門限方案中，參與者重構(gòu)一次秘密之后，若要共享新的秘密，分發(fā)者就必須重新設(shè)置參數(shù)、給參與者分發(fā)秘密份額，因?yàn)樵摲桨钢袇⑴c者持有的秘密份額是一次性的，不能重復(fù)使用，方案的效率較低．

為了提高秘密共享方案的效率，文獻(xiàn)[12-13]提出了一個多階段秘密共享方案，方案中的每個份額可以使用l次，但是在重構(gòu)過程中要求參與者提供相應(yīng)順序的秘密份額，這在實(shí)際的應(yīng)用有很大的局限性． 隨后，文獻(xiàn)[14]構(gòu)造了克服了上述缺點(diǎn)的一個方案，參與者可以用同一個子秘密共享任意多個秘密，子秘密可使用任意多次，但該方案為防止秘密分發(fā)者欺詐，每個參與者需要運(yùn)行多次模指數(shù)運(yùn)算來驗(yàn)證，計(jì)算量非常大． 同時為了防止參與者之間的相互欺詐，方案采用交互式驗(yàn)證方式． 針對上述缺陷，文獻(xiàn)[15]提出一個新的方案，但在該方案中，對每一個共享秘密，秘密分發(fā)者除了要計(jì)算秘密份額外，還需要利用各參與者的子秘密計(jì)算一個驗(yàn)證向量，而向量的每一個分量都是模指數(shù)運(yùn)算，因而秘密分發(fā)者計(jì)算壓力很大． 文獻(xiàn)[16]在門限秘密共享和RSA數(shù)字簽名的基礎(chǔ)之上，提出了門限多重秘密共享方案，但是該方案需要將子秘密通過秘密信道發(fā)送給參與者，在動態(tài)秘密共享情形下，秘密共享者的工作量較大，同時維護(hù)秘密信道增加了通信開支． 本文提出了一個安全有效的可公開驗(yàn)證的(t，n)多重秘密共享門限方案． 方案加密采用ElGamal公鑰密碼體制[17]，不需要維護(hù)秘密信道而增加通信成本；計(jì)算的驗(yàn)證參數(shù)可以多次利用，Dealer要想共享新的秘密，只需要在公告牌上發(fā)布新的數(shù)據(jù)即可，Dealer的計(jì)算量較小，具有廣泛的適用性．

1 基礎(chǔ)知識

定義1(拉格朗日插值多項(xiàng)式) 設(shè)(x0，y0)，(x1，y1)，…，(xt-1，yt-1)是二維平面上任意給定的t個點(diǎn)的坐標(biāo)，則有且僅有一個與這t個點(diǎn)的坐標(biāo)對應(yīng)的t-1次多項(xiàng)式p(x)，滿足p(xi)=yi，0≤i

p(x)可以通過下面的公式計(jì)算得到：

(1)

身份識別的目的是使某人的身份被確認(rèn)． 下面介紹Schnorr身份認(rèn)證方案，該方案需要一個可信第三方發(fā)放證書和選擇系統(tǒng)參數(shù)．

下面的同余式成立說明Alice能夠向Bob證明自己的身份

在上述的方案中需要證明者和驗(yàn)證者交互才能證實(shí)證明者的身份，顯然滿足不了本文所構(gòu)造方案中非交互身份認(rèn)證的需求，因此建立了一個非交互的身份認(rèn)證方案．

2 方案構(gòu)成

設(shè)P={P1，P2，…，Pn}是n個參與者的集合，Dealer是秘密分發(fā)者． 該方案在系統(tǒng)中需要一個公告牌，只有Dealer可以修改、更新公告牌上的內(nèi)容，其他人只能閱讀和下載．hash()是一個安全的密碼學(xué)Hash函數(shù)．

2.1 秘密分發(fā)階段

1) 秘密份額分發(fā)

Dealer保存p(x)，在公告牌上發(fā)布相關(guān)系數(shù)Ci=gαimodq，i=0，1，…，t-1．

2) 秘密份額的驗(yàn)證

2.2 秘密生成階段

2.3 秘密重構(gòu)階段

1) 秘密份額解密

2) 聯(lián)合解密

B可以計(jì)算

3 安全性分析

定理1攻擊者無法從Yi或Sij中計(jì)算得到p(i)．

定理2若參與者數(shù)量少于門限值t則不能從Tj，mj得到共享秘密Kj．

而p(i)是一個t-1次多項(xiàng)式，需要t個點(diǎn)才能確定p(i)，所以若參與者數(shù)量少于t則無法從Tj，mj得到共享秘密Kj．

在解密的過程中，沒有直接用到p(i)，也無法從解密參數(shù)中獲取p(i)，可以保證p(x)安全，所以可以用設(shè)定的參數(shù)安全共享多個秘密．

4 結(jié)束語

本文構(gòu)造了一個可公開驗(yàn)證的門限多重秘密共享方案．

該方案基于拉格朗日插值多項(xiàng)式，且采用兩次非交互的驗(yàn)證協(xié)議，第一次驗(yàn)證是為了防止Dealer作弊或信息在傳遞過程中受到信道中噪音的干擾而出現(xiàn)錯誤；第二次驗(yàn)證是檢測參與解密的參與者提供的秘密份額是否為Dealer發(fā)送． 只有通過兩次驗(yàn)證的秘密份額才能作為重構(gòu)秘密的份額．

共享多個秘密的思想是將秘密和一個隨機(jī)參數(shù)作二進(jìn)制加法隱藏起來，只有達(dá)到或超過門限值個數(shù)的參與者聯(lián)合才能計(jì)算得到這個隨機(jī)參數(shù)． 共享新的秘密只需選擇新的參數(shù)，因此可以共享任意多個秘密．

本文所構(gòu)造的方案是將可公開驗(yàn)證和可共享多個秘密這兩個優(yōu)點(diǎn)相結(jié)合，是對秘密共享作了進(jìn)一步研究．