無可信中心可驗證可更新的向量空間秘密共享

谷婷

（懷化學院 電氣與信息工程學院，湖南 懷化 418000）

1 概述

秘密共享技術被廣泛應用于現實生活中，它主要用于防止重要數據、秘密信息的丟失和竊取，最早由Blakley和Shamir于1979年提出[1-2]。矢量空間秘密共享方案最初由Brickell于1989年提出[3]，完善了接入結構的豐富性。無可信中心的秘密共享方案最初是由Ingemarsson等人于1991年提出的[4]，避免了可信中心的權威欺詐。可更新的秘密共享方案最初由Herzberg等人于1995年提出[5]，在不改變共享秘密的前提下，定期更新參與者的秘密份額，防止攻擊者在整個秘密生存周期內竊取共享秘密。可公開驗證的秘密共享方案最初由Stadler于1996年提出[6]，任何人均可驗證公開信息的有效性，并且不會泄露任何與秘密相關的信息。

最初的向量空間秘密共享方案是一個理想的方案，其中某一個參與者或者是幾個參與者聯合很容易就能成功地欺騙其他參與者。1999年，Padr·等人提出了一個安全的矢量空間秘密共享方案[7]，欺詐成功的概率為1/q。2002年，許春香等人在文獻[7]的基礎上也提出了一種安全的矢量空間秘密共享方案[8]，欺詐成功的概率為1/q2。同年，許春香等人還提出了一種預防欺詐的矢量空間秘密共享方案[9]，利用離散對數的難解性檢測欺詐行為，但始終需要分發者的參與，同時，更新操作需由分發者完成。2006年，Pang等人提出了一種基于ECC的向量空間秘密共享方案[10]，該方案實現了可公開驗證的屬性，但需要可信中心的參與，未能實現對秘密份額的更新。2011年，Zhang等人提出一種無可信中心的、可驗證的向量空間秘密共享方案[11]。該方案的份額只能由參與者自己驗證，同時未實現對秘密份額的更新。同年，張倩倩等人提出了一種無分發者的向量空間秘密共享方案[12]，該方案無需分發者分發秘密份額，但未實現對秘密份額的驗證和更新，且在所舉的例子中沒有完全設計好函數φ，以至于在接入結構中不是所有的合法授權子集都能恢復出密鑰。2015年，李濱提出了一種基于向量空間不同訪問群體的門限方案[13]。該方案通過選取向量空間的一些子空間中線性無關向量作為子密鑰來實現對主密鑰的共享，但需要可信中心的存在。

本文構造了一種無可信中心的可公開驗證、可更新的向量空間秘密共享方案。它不需要可信中心的參與，無需安全信道，所有參與者共同產生各個參與者的秘密份額。同時，更新時選取一個第一分量為零的非零向量，即可實現定期更新各個參與者所持有的秘密份額。另外，這種方案基于簽密與消息恢復算法，實現了方案的可公開驗證屬性。

2 準備知識

2.1 離散對數

設p是素數，a是p的本原元，即1到p-1的任何值都可以用a，a2，…，ap-1（modp）中的一個值表示，b?∈｛1，2，…，p-1｝，有唯一的i∈｛1，2，…，p-1｝，使得b≡ai（modp），稱i為modp下以a為底b的離散對數，記 i≡logab（modp）。

已知a，p，i時，容易求出b；而當a，p，b已知時，求i非常困難。目前，最快求解離散對數的時間復雜度為：當p很大時，求解離散對數是困難的。

2.2 簽密與消息恢復算法

設q和p是2個大素數，且q︱（p-1），GF（p）為有限域，g為GF（p）上的q階生成元。成員A選取私鑰dA∈[1，q-1]，對應公鑰為yA＝ gdA（modp），成員B選取私鑰dB∈[1，q-1]，對應公鑰為成員A對成員B發送消息m。

簽密算法：A選擇k∈[1，q-1]，計算α＝gk，u＝m·β（modq），v＝k-dAu（modq）。A 將（α，u，v）通過公開信道發送給B。

3 方案構成

p和q均為大素數，GF（p）為有限域，g為GF（p）上的q階生成元。U＝｛P1，P2，…，Pn｝是n個參與者的集合。K是GF（p）上的r維向量空間，Γ為U上的接入結構，存在函數φ：U→K滿足特性：r維向量（1，0，0，…，0）∈φ（Pi）＝（ai1，ai2，…，air）：Pi∈M＞ΓM∈?，即r維向量（1，0，0，…，0）能表示為Г的合法授權子集中各參與者的φ函數的線性組合，公開函數φ（Pi）＝（ai1，ai2，…，隨機選擇私鑰2，…，n），計算對應的公鑰n）。共享的隨機秘密為S。

3.1 份額分發

Pi（i＝1，2，…，n）任選r維向量空間K上非零向量計算并公開記秘密0），其中（1，0，0，…，0）為r維向量。

Pi（i＝1，2，…，n）計算Pi保留將通過簽密算法加密公開發送給Pj（j＝1，2，…，n；j≠i）。具體操作是：Pi選取整數計算公開其中 j＝1，2，…，n；j≠i.

式（1）驗證通過后，Pj（j＝1，2，…，n）計算n），從而計算各自的秘密份額

3.2 份額更新

設在τ（τ＝1，2，…）時刻對秘密份額進行更新。

Pi（i＝1，2，…，n）任選K上非零向量其中，計算并公開

依據Pi（i＝1，2，…，n）計算Pi保留將通過簽密算法加密公開發送給Pj（j＝1，2，…，n；j≠i）。具體操作是：Pi選取整數計算公開其中，j＝1，2，…，n；j≠i.

式（2）驗證通過后，根據Pj（j＝1，2，…，n）計算（i＝1，2，…，n），計算更新份額2，…，n），則更新后的秘密份額為＝1，2，…，n）.

3.3 秘密恢復

如果Г中的授權子集M準備恢復秘密，不妨設M＝｛P1，P2，…，PL｝，M中的成員Pj（j＝1，2，…，l）提交它們的秘密份額。先驗證秘密份額的正確性，當τ＝0（初始時刻）時，M中的成員對提交的秘密份額用式（3）驗證其正確性：

當τ＝1，2，3，…（更新時刻）時，M中的成員對提交的秘密份額用式（4）驗證其正確性：

最后，恢復出共享的秘密：當τ＝0時，M中的成員恢復出共享的秘密為當τ＝1，2，3，…時，M中的成員恢復出共享的秘密為0）＝V（0）·（1，0，0，…，0）.

4 方案分析

4.1 正確性分析

驗證式（1）：

驗證式（2）：

驗證式（3）：

驗證式（4）：

4.2 安全性分析

定理：在份額分發階段，假設簽密與消息恢復算法是安全的，則攻擊者不能以不可忽略的優勢攻破本方案（當τ＝1，2，…時，有類似的結論。）

證明：反證法。假設簽密與消息恢復算法是安全的，但存在一個模擬算法能以不可忽略的優勢攻破本方案，并用此模擬算法對簽密和消息恢復算法進行攻擊。

模擬算法隨機設置U＝｛P1，P2，…，Pn｝的私鑰di（i＝1，2，…，n），且從公開信息中獲取各成員的公鑰yi（i＝1，2，…，n）、大素數q和p、GF（p）上q階生成元g。

設A是敵手，B是挑戰者，A開始詢問私鑰，并公開其結果，B將結果所對應的私鑰送給A，系統屏蔽A擲硬幣μ∈｛0，1｝.如果μ＝0，則A獲得成員的正確私鑰；反之，如果μ＝1，則A獲得其他信息。

系統屏蔽B擲硬幣δ∈｛0，1｝.如果δ＝0，則模擬算法設置非零向量如果δ＝1，則模擬算法設置非零向量。設置完成后，B將和傳送給A。

猜測過程：A猜測μ和δ，并輸出猜測值μ′和δ′。

當δ′＝1，μ′＝1時，顯然是無效的攻擊。

同理可證，當τ＝1，2，…時，有相似的結論。

4.3 性能分析

表1比較本方案與方案[8]、方案[9]、方案[12]的性能。由表1可知，本方案不需要可信中心的參與，而且具有秘密份額的可公開驗證屬性以及秘密份額的可定期更新屬性。

表1 性能比較

5 結束語

本文基于簽密與消息恢復算法，構造了一種無可信中心的可公開驗證、可更新的向量空間秘密共享方案。該方案不需要維護安全信道，參與者可以將要分發的信息在公開的信道上傳輸；利用簽密與消息恢復算法，任何人均可公開驗證秘密份額和更新份額；通過更新秘密份額，有效地防止攻擊者在整個秘密生存周期內竊取秘密信息。安全性分析證明了該體制是安全的，具有一定的實用價值。而如何在計算量上取得更大的優勢，則是筆者下一步的研究方向。

［1］Blakley G R.Safeguarding Cryptographic Keys：Proceedings of National Computer Conference，1979［C］//New York：[s.n.]，1979：313-317.

［2］Shamir A.How to share a secret［J］.Communications of the ACM，1979，22（11）：612-613.

［3］Brickell E F.Some ideal secret sharing schemes［J］.Journal of Combinatorial Mathematics and Combinatorial Computing，1989（6）：105-113.

［4］Ingemarsson I，Simmons G J.A protocol to set up shared secret schemes without the assistance of a mutually trusted party ［ C ］ //Advances in Cryptology-Eurocrypt’90 Proceedings，1991：266-282.

［5］HerzbergA，Jarecki S，Krawczyk H，et al.Proactive secret sharing or：how to cope with perpetual leakage［C］//Coppersmith Ded Advances in Cryptology CRYPTO’95.Berlin：Springer-Verlag，1995：339-353.

［6］Stadler M.Publicly verifiable secret sharing［C］//LNCS 1070 Advances in Cryptology-EUROCRYPT’96.Berlin：Springer-Verlag，1996：190-199.

［7］Padr·C，S·ez G.Detection of Cheaters in Vector Space Secret Sharing Schemes［J］.Desings，Codes and Cryptography，1999，16（1）：75-85.

［8］許春香，陳愷，肖國鎮.安全的矢量空間秘密共享方案［J］.電子學報，2002，30（5）：715-718.

［9］許春香，傅小彤，肖國鎮.預防欺詐的矢量空間秘密共享方案［J］.西安電子科技大學學報，2002，29（4）：527-555.

［10］Shichun Pang，Shufen Liu.An ECC based vector space key sharing scheme［C］//2006 1st International Symposium on Pervasive Computing and Applications，2006：524-527.

［11］Benhui Zhang，Yuansheng Tang.Verifiable Vector Space Secret Sharing Scheme Without a Dealer［C］//Computer Science and Service System，2011：931-934.

［12］張倩倩，李志慧，雷娟.基于向量空間上的無分發者的秘密共享方案［J］.計算機應用研究，2011，28（6）：2230-2232.

［13］李濱.基于向量空間不同訪問群體的門限方案［J］.通信學報，2015，36（11）：67-72.