一種公開的可驗證秘密共享方案

摘 要：公開的可驗證秘密共享(PVSS)方案是一種任何一方均能公開地驗證共享正確性的可驗證秘密共享方案，驗證并不局限于共享所屬的參與者本人，所以它比一般的可驗證秘密共享方案有著更廣泛的應用。提出了一個基于公鑰密碼和零知識證明的，非交互式的，信息論安全的PVSS方案。該方案實現簡單，且易于擴展和更新，特別適宜于一般接入結構上公開的可驗證秘密共享。

關鍵詞：秘密共享； 接入結構； 零知識證明； 公鑰密碼

中圖分類號：TP309文獻標志碼：A

文章編號：1001—3695(2007)03—0146—03

秘密共享在現代密碼學中有著非常重要的應用。一個秘密共享方案至少包含兩個基本協議：①分配協議。秘密分發者（Dealer）將秘密s分割成n份s₁，s₂，…，s_n，每一份稱為共享（Share）或影子，分發給每一個參與者。②重構協議。授權子集中的所有參與者合作，能夠恢復秘密s。最早的秘密共享是一種(k，n)門限方案，分別由Blakley[1]和Shamir[2]于1979年提出；接著Ito[3]和Benaloh[4]提出了更一般接入結構（Access Structure）上的秘密共享。

最初的秘密共享方案要求所有參與者都是誠實的。但在現實生活中，可能會出現一些惡意的行為：秘密分發時，分發者將不正確的共享分發給某個或某些參與者；秘密恢復時，參與者提供不正確的共享。為了防止以上惡意行為的出現，Chor[5]第一次提出了可驗證秘密共享。在文獻[5]中，秘密分發者通過秘密信道將共享分發給各參與者，并且各參與者能夠根據公開的信息檢驗屬于自己份額的共享的正確性。在后來的實際應用中，Chor方案又顯示出了不足之處：需要秘密信道傳送共享，共享不能被公開驗證。為了彌補這一缺陷，Stadler[6]提出了一種公開的可驗證秘密共享方案。在文獻[6]中，秘密分發者將各參與者的共享加密并附加上一個證明，在公開信道上傳送，使得共享能夠被公開驗證，但又不被泄露。

顯然，與前面的方案相比，Stadler方案更有實用價值。但是，它還不是一個完備的方案。雖然能夠公開地驗證分發給各參與者的共享的正確性，但并不能保證各參與者提交正確的共享。針對Stadler方案的不足，Schoenmakers[7]提出了一個更完整的非交互式的PVSS方案；接著，文獻[8]也提出了一個類似的方案。不同的是，前者是計算安全的，而后者是信息論安全的（無條件安全的）。

在Schoenmakers的公開可驗證秘密共享方案中，任何一方都能公開地驗證共享的正確性，驗證并不局限于共享所屬的參與者本人，所以它比一般的可驗證秘密共享方案應用更廣。例如，可以作為密鑰托管（Key Escrow）、電子投票（Electronic Voting）、電子支付（Electronic Cash）等系統中的基本密碼協議。目前，多數PVSS方案均是基于拉格朗日多項式插值的方法。多項式插值的方法在處理門限方案時非常有效，但推廣到一般的接入結構上時卻很復雜。

1 非交互式PVSS模型

在PVSS方案中，秘密分發者希望在n個參與者中分享秘密s。令P={P₁，P₂，…，P_n}是參與者集合；Γ 2^P，是由P的子集所組成的集合，且Γ中任意子集均能夠恢復秘密，則稱Γ為接入結構（Access Structure），Γ中的元素稱之為授權子集（Authorized Subset）。在文獻[7]中，Schoenmakers定義了一個非交互式的PVSS模型。與一般的VSS相比，PVSS有一個最明顯的特征：在秘密分發者與各參與者之間沒有秘密信道，所有的信息加密后，在公開信道上傳輸。

（1）系統初始化。采用公開有效的算法生成所需的系統參數。這部分并不需要分配者與各參與者之間交互信息，而且參與者可以動態地加入或離開。加入時，參與者P_j秘密選擇一個私鑰x_j，注冊其公鑰y_j。假定執行以下協議的參與者均已注冊。

（2）共享分發。這部分協議可細分為兩個子協議。

①共享的分發。秘密分發者D選擇一個秘密s，在n個參與者P₁，P₂，…，P_n中分享。首先，D為每個參與者P_j生成一個共享s_j（j=1，…，n），公開加密的共享E_j(s_j)。其次，為了確保E_j(s_j)中加密了正確的共享s_j，需要加上相應的證明PROOFD。另外，PROOFD還作為D對秘密s的一個承諾，保證在重構協議中得到同樣的s。

②共享的驗證。知道加密算法E_j及其相應公鑰的用戶均可以驗證加密共享的正確性。運行PROOFD的一個非交互式的驗證算法，驗證E_j(s_j)中s_j的正確性。一個或多個共享驗證失敗時，中止協議的繼續執行。因為任何人可以根據公開信息驗證共享的正確性，這樣就能排除以下情況的出現：參與者正確收到共享后依然抱怨從而使得協議錯誤地中止執行。

（3）秘密重構。同樣也包括兩個子協議。

①共享的解密。參與者從E_j(s_j)中解密出共享s_j（j=1，…，n）。并不要求所有參與者都這樣做，僅只要求授權子集中的參與者能夠成功地解密各自的共享。這些參與者公開s_j，并加上另外一個證明PROOFP_j，證明s_j的正確性。

②秘密的恢復。PROOFP_j能夠排除不誠實的參與者提交錯誤的共享。根據授權子集中所有參與者的共享重構秘密s。

與Stadler模型相比較，上面的模型增加了證明PROOFP_j，用于證明共享的正確性。而且以上所有的證明均要求是非交互式的。

2 零知識證明

所謂零知識證明，是指一方(證明者)向另一方(驗證方)證明某個論斷正確的一種協議，同時要求在證明過程中不泄露證明方任何其他信息。零知識證明在設計密碼協議時非常有用，下面僅介紹本文中用到的零知識證明協議。

Chaum和Pedersen提出了一個協議[9]，證明logg₁h₁=logg₂h₂，即證明者知道x，并有h₁=gx₁和h₂=gx₂。用符號DLEQ(g₁，h₁，g₂，h₂)來標記這個協議，它包含以下步驟：

3 本文提出的方案

Schoenmakers方案以及后來Tang等人的方案均是門限PVSS方案，沒有涉及更一般接入結構上的秘密共享。然而在現實生活中，更多的應用需要在一般接入結構上。雖然以上方案在處理門限方案時非常有效，但當推廣到一般的接入結構上時卻非常復雜，很難實現。下面提出了一個簡單的PVSS方案，該方案基于公鑰密碼和Sign(X，Y，g₁，g₂，h₁，h₂)，適宜于一般接入結構上的可驗證秘密共享。

3.1 協議

3.2 有效性分析

秘密分發者D發布2n+1個屬于群G_q的元素（C，C_j，Y_j）加上2(n+m)+1個|q|位數（s′_i，t′_i，r_j1，r_j2和c）。另外，與Schoenmakers方案及Tang方案相似，整個協議中求冪的次數相對較少，而且冪指數也都是相對較小的數（實際應用中|q|=160）。所以該方案與以上方案等效，但是他們的方案僅是一種門限方案，而本方案則適宜于更一般的接入結構上的公開可驗證的秘密共享。

3.3 安全性分析

為了分析新方案的安全性，首先對新方案進行一些簡化約定：①g=h；②G=H；③s_j=t_j（1≤j≤n）。若簡化的方案是安全的，那么一般的方案更安全。

（2）分析共享秘密的安全性，將以定理的形式引出。

定理1 在Diffie—Hellman假定條件下，簡化的方案在隨機預言模式（Random Oracle Model）下是安全的：①授權子集中的所有參與者合作能夠恢復正確的秘密；②任意的非授權子集中的參與者合作不能獲得秘密。

但定理1并不聲明非授權子集中的參與者不能獲得任何（部分）秘密的信息。更進一步的結論需要建立在“ELGamal密碼是計算安全的”假設之上。而這一假設又等價于DDH假定（Decision Diffie—Hellman Assumption），即對于一個給定的三元組，確定是否是(g^α，g_β，g^αβ)或(g^α，g^β，g^δ)在計算上是不可行的。其中α，β，δ均是隨機的。定理2 在DDH假定條件下，簡化的方案在隨機預言模式下是計算安全的：①授權子集中的所有參與者合作能夠恢復正確的秘密；②任意的非授權子集中的參與者合作不能夠得到任何（部分）秘密信息。

簡化的方案是新方案的特殊情況，所以在簡化的方案中成立的定理1、定理2在一般的方案中依然成立。另外，簡化的方案和沒有簡化的方案之間的比較猶如Feldman’s VSS方案[12]與Pedersen’s VSS方案[13]一樣，前者是計算安全的，而后者則是信息論安全的（無條件安全的）。

定理3 在DDH假定條件下，本文的方案在隨機預言模式下是信息論安全的：①授權子集中的所有參與者合作能夠恢復正確的秘密；②任意的非授權子集中的參與者合作不能夠得到任何（部分）秘密信息。

4 結束語

本文提出了一種信息論安全的公開可驗證的秘密共享方案與Tang方案等效，但該方案能適宜于任意的接入結構。另外在該方案中，參與者的共享隨機生成，這樣易于擴展，真正能夠做到參與者動態地加入或離開。而且在處理秘密、共享更新時也非常簡單，只需更新相應的s′_i和t′_i。因而，本方案是一種動態的PVSS方案，實現簡單，可以作為密鑰托管、電子支付、電子投票等系統中的基本密碼協議，有著非常良好的應用前景。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。