無可信第三方的可驗證多秘密共享

朱錦華

摘 要：一般秘密共享方案需要有可信第三方作為分發(fā)者進行秘密分配，實際應用中，不存在完全可信的第三方，因此已有方案均存在安全隱患，降低了實用性。為提高方案的實用性，提出了一種無可信第三方的可驗證多秘密共享方案。方案利用哈希函數(shù)作為安全假設，減少了計算開銷。通過廣播消息避免了對安全信道的需求并且降低了通信代價。方案無需無可信第三方，提高了秘密共享方案的安全，方案一次可共享多個秘密，且可驗證秘密份額的有效性。

關(guān)鍵詞：秘密共享；可驗證；無可信第三方

秘密共享是密碼學中密鑰管理的重要分支之一，最早由Shamir提出。Shamir的（t， n）門限共享方案基于多項式插值實現(xiàn)的，該方案準許誠實的分發(fā)者將秘密S分成n份子秘密發(fā)送給n個參與者，使得大于等于t個分發(fā)者可以重構(gòu)秘密S，任意小于t個參與者無法獲得秘密的信息。秘密共享思想得到廣泛應用，如電子投票、電子拍賣、數(shù)字簽名等。

Shamir門限共享方案具有簡單、實用的特點，但方案仍存在不足。首先，方案為單秘密共享方案，共享效率較低；其次，方案可能存在欺騙攻擊，在秘密重構(gòu)階段，參與者可能發(fā)送虛假子秘密導致重構(gòu)失??；最后，完全可信的第三方現(xiàn)實中不存在，實際應用中存在安全隱患。為解決上述問題，有的方案提出了多秘密共享方案，方案一次可共享多個秘密，有效的提高了共享效率。方案1提出了可驗證的秘密共享方案，方案可驗證子秘密的有效性，有效的解決了參與者的欺騙的攻擊。而針對分發(fā)者的誠實問題，方案2提出了抗泄露的秘密共享方案，有效防止半誠實分發(fā)者存在的攻擊，但只可共享一個秘密。方案3基于離散對數(shù)問題提出一種無可信中心的可公開驗證秘密共享方案，但方案計算與通信開銷較大。

為解決上述文獻存在的問題，綜合已有方案的優(yōu)點，本文提出了一種無可信第三方的可驗證多秘密共享方案，方案利用單向哈希函數(shù)簡單易于實現(xiàn)的優(yōu)點，實現(xiàn)子秘密的驗證過程，有效的降低了計算開銷，方案采用由參與者共同創(chuàng)造多項式系數(shù)的方式，降低了分發(fā)者的權(quán)限，可以有效的抵抗半誠實參與者的攻擊。

一、預備知識

（一）單向哈希函數(shù)

單向哈希函數(shù)是指具有單向性和抗碰撞性的哈希函數(shù)H。

（1）單向性：已知H（x），計算滿足y = H（x）的x是困難的。

抗碰撞性：對于x的哈希值H（x），找到x滿足H（x） = H（x）是困難的。

（二）半誠實分發(fā)者

半誠實分發(fā)者不同于傳統(tǒng)的欺騙分發(fā)者直接發(fā)送假的秘密份額，半誠實分發(fā)者只是將秘密信息隱藏在有效的子秘密中，具有一定隱蔽性而且打破了秘密共享的門限限制。

（三）無可信第三方的可驗證多秘密共享

無可信第三方的可驗證多秘密共享方案是一種符合正確性、安全性、可驗證性的多秘密共享方案。

正確性：如果分發(fā)者是半誠實分發(fā)者，那么由任意不小于t個參與者提供的秘密份額能夠正確重構(gòu)秘密S。

安全性：如果分發(fā)者是半誠實分發(fā)者，那么通過任意小于t個參與者提供的秘密份額將無法得到任何關(guān)于秘密S的信息。

可驗證性： 如果分發(fā)者是半誠實分發(fā)者，那么參與者可以驗證分發(fā)者分發(fā)的秘密份額的有效性，分發(fā)者D也可以驗證參與重構(gòu)的參與者提供的秘密份額的有效性。

三、方案分析

（一）正確性分析

定理1 分發(fā)者是半誠實的，方案可保證任意大于等于t個參與者正確恢復k個秘密。

證明：根據(jù)半誠實分發(fā)者定義，當方案執(zhí)行時，分發(fā)者按照方案執(zhí)行。參與者Pi正確計算子秘密f （ i ） ，并且誠實提供子秘密。根據(jù)拉格朗日插值，已知大于等于t個多項式函數(shù)值可唯一確定一個t-1階多項式。因此，參與者可以正確恢復f （0）， 利用公布的gi，進而恢復k個秘密。

（二）安全性分析

定理2 分發(fā)者是半誠實的，方案可保證小于t個參與者無法獲得任何關(guān)于秘密的信息。

證明：根據(jù)半誠實分發(fā)者定義，分發(fā)者按照方案執(zhí)行。根據(jù)方案描述，公布的信息包括gi， vi， f （i） ，其中已知gi，未知f （0）敵手無法獲得任何秘密的信息。又因為vi =H（f （i） ），根據(jù)哈希函數(shù)單向性，已知vi，敵手無法獲得任何關(guān)于f （i） 的信息。由于公布的f （i） = ri + f （i） 中ri為每個參與者選擇的隨機數(shù)，因為即使公布 f （i）每個參與者也不能獲得多余的有效子秘密。假設有t-1個參與者{P1， P2， ...， Pt}試圖恢復秘密，根據(jù)拉格朗日插值定理，t -1個函數(shù)值只能唯一確定t -2階多項式，而f （x）為t-1階，因此t-1個參與者無法得到任何關(guān)于f （0）的信息，即無法重構(gòu)k個秘密。

（三）可驗證性分析

定理3 分發(fā)者是半誠實的，方案可使參與者驗證個人計算的子秘密是否正確；在重構(gòu)階段，每個參與者可驗證其他參與者發(fā)送的子秘密是否有效。

證明1：假設參與者不具可驗證性，即參與者可半誠實分發(fā)者發(fā)送的虛假秘密份額。假設分發(fā)者公布消息為，根據(jù)方案描述，參與者利用隨機數(shù)ri計算秘密份額，利用哈希函數(shù)計算并和vi比較：

根據(jù)方案，參與者要求分發(fā)者重新發(fā)送，因此，與假設矛盾，方案參與者具有可驗證性。

證明2：在秘密恢復階段，每個參與者接受其他參與者的秘密份額，根據(jù)方案描述，參與者在接受到所有子秘密后，計算秘密份額的哈希值，并判斷是否與vi相等，，當驗證通過后進行秘密恢復，因此方案秘密恢復階段，參與者具有驗證性。

四、方案比較

本文方案在共享秘密個數(shù)，安全假設以及是否依賴可信第三方上具有較大優(yōu)勢。多秘密共享表示共享秘密個數(shù)，安全假設描述方案計算負責度，是否依賴可信第三方是指方案分發(fā)者是否完全誠實。根據(jù)對已有文獻研究，對比結(jié)果如表1：

表1中Y表示具有該項性質(zhì)，N表示不具有該項性質(zhì)。在安全假設中hash、RSA、DLP分別表示單向哈希函數(shù)、RSA假設、離散對數(shù)問題。根據(jù)對比分析，本方案屬于多秘密共享發(fā)難，方案使用單向哈希函數(shù)作為安全假設，增強了實用性，方案不需要依賴可信第三方，降低方案的條件限制，提高了方案的安全性以及實用性。

五、總結(jié)與展望

本文提出了一種無可信第三方的可驗證多秘密共享方案，方案無需誠實的分發(fā)者進行秘密分發(fā)，降低了已有方案的限制條件，使得方案更具有實用性；方案基于單向哈希函數(shù)，方案無需花費較大的計算開銷。

參考文獻：

[1]Shamir A. How to share a secret [J]. Communications of the ACM， 1979， 22（11）： 612-613.

[2]Li H， Sui Y， Peng W. A viewable e-voting scheme for environments with conflict interest[C].//Proceeding of the 2013 IEEE conference on communcication and network security， 2013：251-259.

[3]Peng K. Secure e-commerce based on distributed processing[C].//Proceeding of the 12th international Conference on Parallel and Distributed Computing， PDCAT 2011：406-411.

[4]Huang X Y， Liu J K， Tang S H， et al. Cost-effective authentic and anonymous data sharing with forward security[J]. IEEE Transaction on computers，2015，64（4）：971- 983.

[5]Carpentieri M， Santies D， Vaccaro U. A perfect threshold secret sharing scheme to indentifiy cheaters Designs[J].Codes and Cryptography， 1994， 5（3）：183-187

[6]Chang T Y， Hwang M S， Yang W P. An improvement on the Lin-Wu （t， n） threshold verifiable multi-secret sharing scheme [J]. Applied Mathematics and Computation， 2005， 163（1）： 169-178.

[7]Young L， Yung M. Kleptography： Using Cryptography Against Cryptography [C] // Advances in Cryptology- EURO CRYPT97. Berlin， Heidelberg： Springer-Verlag， 1997： 62-74.

[8]Jun S. Efficient verifiable multi-secret sharing scheme based on hash function [J]. Information Sciences， 2014， 278（9）： 104 - 109.

[9]limid R F. Dealer-Leakage resilient verifiable secret sharing [EB/OL]. Cryptology ePrint Archive， 2014.

[10]Harn L， Fuyou M， CHange C C. Verifiable secret sharing based on the chinese remainder theorem[J].Security and Communication Networks， 2014， 7（6）： 950-957.

[11]于佳，陳養(yǎng)奎，郝蓉等. 無可信中心的可公開驗證多秘密共享[J]. 計算機學報， 2014， 37（5）： 1032.