安全公平理性秘密共享方案

周全興 吳冬妮 李秋賢

摘要：傳統秘密共享方案因未考慮參與者的自利行為而導致方案的效率較低。為了提高秘密共享的通信效率和安全性，結合博弈論與雙線性映射技術，設計公平的理性秘密共享方案。首先，在博弈論框架下引入理性參與者并設計理性秘密共享博弈模型;其次，利用雙線性映射技術保證方案和理性參與者的可驗證性和公平性;最后，通過對方案進行性能分析，表明了該方案不僅保證了安全性，并且有較高的秘密共享通信效率。

關鍵詞： 理性秘密共享; 博弈論; 雙線性映射; 公平性; 通信效率

Abstract：Traditional secret sharing schemes do not take into account the self-interested behavior of participants， which leads to low efficiency of the scheme. In order to improve the communication efficiency of secret sharing， game theory and bilinear mapping technology are combined to design a fair and rational secret sharing scheme. Firstly， introduce rational participants and design a rational secret sharing game model under the framework of game theory. Secondly， this paper uses bilinear mapping technology to ensure the verifiability and fairness of the solution and rational participants. Finally， the performance analysis of the scheme shows that the scheme not only guarantees safety， but also has higher communication efficiency.

Key words： rational secret sharing; game theory; bilinear pairings; fairness; communication efficiency

1 引言

近年來，秘密共享[1]已成為現代密碼學的重要研究領域，在研究各類密碼協議中起著越來越重要的作用。秘密共享的基本思想是存在秘密擁有者將秘密進行分割，隨后發送給不同的參與者，這些參與者的某些子集可以將子秘密進行重構，而其他參與者無法重構秘密也不能獲取有關秘密的任何信息。

秘密共享是由著名密碼學家Shamir[2]和Blakley[3]基于拉格朗日插值多項式和射影幾何理論首次提出的。基于傳統的秘密共享方案，眾多研究學者結合博弈理論提出了理性秘密共享方案[4-6]。2010年，Ishai等[7]利用博弈論設計了服務器與客戶機模式下的安全秘密共享方案，并證明了方案的安全性。2011年，Tian等[8]在提出第三方概念的基礎上，設計了理性秘密共享重構機制，并保證方案的高通信率。2016年，Gordon等[9]在實現方案公平性基礎上，利用全同態加密技術減少了秘密共享的輪復雜度。2019年，Zhang等[10]利用門限秘密共享技術設計區塊鏈分片存儲模型，保證了秘密共享數據的安全性與隱私性。

本文針對秘密共享中存在較高通信率，以及參與者存在自利行為的問題，提出公平的理性秘密共享方案。根據參與者的自利行為，基于博弈論分析理性參與者的行動策略，并設計理性博弈模型。再利用雙線性映射技術保證秘密共享方案的安全性和公平性，從而提高秘密共享的通信效率。

2 預備知識

2.1 博弈論

博弈論[11]表達式由參與者[P]、策略集合[S]和效用函數[u]三個要素組成，即[G=P，S，u]。

2.2 雙線性映射

設[G1]和[G2]分別為[q]階的加法循環群和乘法循環群，[g，Q]為群[G1]的生成元，且[G1=G2=p]具雙線性性質：對于任意[P1，P2∈G1]和[a1，a2∈Z?q]，滿足等式[ePa11，Pa22=eP1，P2a1a2]。

3 理性秘密共享模型

本文設計的公平理性秘密共享博弈模型由理性參與者、參與者不同的策略集合和參與者通過采取不同策略取得的效用函數組成。其中理性參與者包括理性秘密分發者[D]和秘密重構者[P=P1，...，Pn]。參與者的策略集合分為秘密分發者[D]的策略，即是否誠實的將秘密進行分發，策略集合可形式化為[D+，D-]，[D+]表示誠實分發真實秘密，[D-]表示虛假分發假的秘密;秘密重構者[P=P1，...，Pn]的策略集合為[P+，P-]，[P+]表示秘密恢復者選擇誠實的恢復正確秘密，[P-]表示參與者偏離協議選擇惡意行為不發送或不恢復正確秘密。根據參與選擇不同的行為策略，秘密分發者的效用函數為[u+D，u-D]，秘密恢復者的效用函數為[u+P，u-P]。理性參與者的效用函數如表1所示。

4 公平理性秘密共享方案

4.1 初始化階段

本文構造的公平理性秘密共享方案存在理性秘密分發者[D]，理性秘密恢復者[P=P1，...，Pn]，當且僅當[t0

4.2 秘密分發

根據設計的理性秘密共享博弈模型，結合雙線性映射技術構造公平的理性秘密共享方案。秘密分發者[D]將秘密[S]進行分割為子秘密[S1，...，Sm]，其中[S∈G1]，分發者將秘密[S]承諾并對外公布承諾值[CS]，其中[CS=eg，QS]，隨之將子秘密發送至秘密恢復者[P=P1，...，Pn]。

4.3 秘密恢復

理性參與者接收到子秘密[S1，...，Sm]后，通過分發者公布的承諾值[CS]對子秘密進行驗證。若驗證通過，各理性參與者[Pii=1，...，n]利用拉格朗日插值多項式對秘密[S]進行恢復。此時若有參與者偏離協議不恢復或不發送正確的子秘密，根據設計的博弈模型將得到效用[u-D，u-P]，且參與者將受到大于參加本協議消耗的處罰。只有當參與者都誠實的分發和恢復子秘密，他們才會得到效用[u+D，u+P]，且根據博弈論可知此時所有理性參與者效用最大。

5 方案分析

5.1 公平性分析

定理1：在博弈論框架下，當所有理性參與者都不偏離協議執行方案時，方案中參與者的效益最大且能恢復出正確秘密并滿足其公平性。

證明：在方案執行階段，當理性秘密分發者選擇誠實分發秘密且秘密恢復者發送正確子秘密，則獲得效用為[u+D，u+P]，如若其中一方選擇偏離協議則得到效用[u+D，u-P]或[u-D，u+P]，當兩方都存在偏離協議的行為則得到效用[u-D，u-P]。因為博弈論中的囚徒困境可知效用[u+D，u+P]的效益最大，所以只有理性參與者都選擇誠實的執行協議才能取得最大收益，且對所有理性參與者都是公平的并能恢復正確秘密。

5.2 安全性分析

定理2：本方案的安全性基于雙線性映射技術，在理性秘密共享方案中，群[G1]上的秘密[S]的承諾值[CS]滿足其安全性的要求。

證明：假設存在秘密[S∈Z?q]且[S≠S]，使得承諾值[CS=CS]，則根據雙線性映射的雙線性性質可得[eg，QS=eg，QS]，又因為[g，Q]為群[G1]的生成元，[q]為群[G1]的階，所以存在[qg=0]且[qQ=0]，即可得到[Sg=Sg]，這與[S≠S]相矛盾，且雙線性映射的計算性Diffie-Hellman問題是難解的，所以本方案滿足其安全性要求。

6 總結

本文是結合博弈論設計的安全公平的理性秘密共享方案，為了實現方案的公平性與安全性，先構造了理性秘密共享博弈模型，利用效用函數制約理性參與者的策略行為，使其不選擇偏離協議的惡意行為。其次利用雙線性映射技術保證了方案的安全性。方案滿足了其公平性與安全性，實現了高效的秘密共享。

參考文獻：

[1] Cheraghchi M. Nearly optimal robust secret sharing[J]. Designs， Codes and Cryptography， 2019.

[2] Communications of the ACM， 1979， 22（11）： 612–613.

[3] BLAKLEY G R. Safeguarding cryptographic keys[A]. Proceedings of the National Computer Conference[C]. Germany： Springer-Verlag，1979， 48： 313-317.

[4] Gen P C， Liang T Y， Hai L， et al. A Survey on the Intersection of Cryptography and Game Theory[J]. Journal of Cryptologic Research， 2017.

[5] 許春香.安全秘密共享及其應用研究[D].西安電子科技大學，2003.

[6] 張恩，蔡永泉.一種新的理性秘密共享方案[J].中國通信（英文版）， 2010（4）：26-30.

[7] ISHAI Y， KUSHILEVITZ E， PASKIN A. Secure multiparty computation with minimal interaction[C]. In： Advances in Cryptology—CRYPTO 2010. Springer Berlin Heidelberg， 2010： 577–594.

[8] 田有亮，王雪梅，劉琳芳.基于馬爾可夫決策的理性秘密共享方案[J].通信學報，2015，36（9）： 222–229.

[9] GORDON S D， LIU F H， SHI E. Constant-round MPC with fairness and guarantee of output delivery[C]. In：Annual Cryptology Conference. SPringer Berlin Heidelberg， 2015： 63–82.

[10] 張國潮，王瑞錦.基于門限秘密共享的區塊鏈分片存儲模型[J].計算機應用，2019，39（9）：2617-2622.

[11] 周全興，李秋賢，樊玫玫.基于智能合約的三方博弈防共謀委托計算協議[J].計算機工程，2020，46（8）：124-131，138.

【通聯編輯：代影】