一個可公開驗證的多重秘密共享門限方案

蔡兆政，瞿云云，包小敏

1. 西南大學 數學與統計學院，重慶 400715；2. 重慶市第十八中學，重慶 400020；3. 貴州師范大學 數學與計算機科學學院，貴陽 550001

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

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

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

在秘密共享中另外一個需要著重考慮的問題就是方案的效率，主要考慮數據傳輸量和計算量． 若秘密分發者和參與者之間使用一次一密的方式共享秘密，雖然安全性得以保證，但是在效率和成本上都有欠缺． 例如在Shamir門限方案中，參與者重構一次秘密之后，若要共享新的秘密，分發者就必須重新設置參數、給參與者分發秘密份額，因為該方案中參與者持有的秘密份額是一次性的，不能重復使用，方案的效率較低．

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

1 基礎知識

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

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

(1)

身份識別的目的是使某人的身份被確認． 下面介紹Schnorr身份認證方案，該方案需要一個可信第三方發放證書和選擇系統參數．

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

在上述的方案中需要證明者和驗證者交互才能證實證明者的身份，顯然滿足不了本文所構造方案中非交互身份認證的需求，因此建立了一個非交互的身份認證方案．

2 方案構成

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

2.1 秘密分發階段

1) 秘密份額分發

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

2) 秘密份額的驗證

2.2 秘密生成階段

2.3 秘密重構階段

1) 秘密份額解密

2) 聯合解密

B可以計算

3 安全性分析

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

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

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

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

4 結束語

本文構造了一個可公開驗證的門限多重秘密共享方案．

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

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

本文所構造的方案是將可公開驗證和可共享多個秘密這兩個優點相結合，是對秘密共享作了進一步研究．