可驗證的動態多秘密共享

趙麗萍，湯文亮

(華東交通大學軟件學院，江西南昌330013)

可驗證的動態多秘密共享

趙麗萍，湯文亮

(華東交通大學軟件學院，江西南昌330013)

提出了一種新的可驗證的動態門限多秘密共享方案。該方案的安全性基于Shamir的秘密共享體制和橢圓曲線加密算法的安全性以及橢圓曲線離散對數問題的求解困難性。共享秘密可以周期性的改變，秘密分發者周期性的改變公告欄上的信息以增強系統的健壯性。對于不同的共享秘密，秘密分發者可以動態調整該秘密的門限值。此外，方案能有效檢測和識別參與者的欺騙行為，參與者也可以驗證其接受到的信息，且無需改變私有信息在任何時候都可以重構秘密。由于公告欄上的信息是定期更新的，所以不會影響新秘密的共享。

門限;橢圓曲線;秘密共享;多秘密

秘密共享［1］是信息安全和數據保密的重要手段。1979年Shamir［2］和Blakey［3］分別獨立地提出了門限秘密共享體制，使授權的合格子集能容易地恢復共享秘密，而非合格子集得不到關于共享秘密的任何信息。由于有著廣泛的實際應用前景，許多學者投入了大量精力對其本身和相關問題進行深入的研究，并獲得了一批研究成果。在Shamir的秘密共享方案中存在兩個問題:莊家(秘密的分發者)的誠實性和成員的誠實性。對這兩個問題的研究，就形成了可驗證的秘密共享方案［4－5］。隨后的大多數方案在設計時都基于2個假設:(1)在秘密被重構之前所有的參與者和秘密都不改變。(2)秘密分發者和各參與者之間需要建立一條安全信道。但這2個假設會影響秘密共享方案的實際應用。文獻［6］提出了一種檢測方案，一次計算即可知道該授權子集中是否有不誠實的用戶。如果沒有欺詐者，即可得到正確秘密;如果存在欺詐者，則需要對各個用戶進行驗證。當參與者中沒有欺詐者存在時，驗證所需的計算量將大大減少。文獻［7］提出了一個動態的秘密共享方案，在該方案中使用了RSA密碼體制，這使得方案不需要建立安全信道并且共享秘密和參與者都可以動態地發生變化，但它只適用于單秘密共享，存在一定的局限性。

本文基于橢圓曲線加密體制和Shamir的秘密共享體制，提出了一種新的多秘密共享方案。該方案具有如下特點:(1)可進行多秘密的共享;(2)對于不同的共享秘密，秘密分發者可動態調整其門限值; (3)可防止秘密分發者與參與者的相互欺詐。

1 方案描述

方案由系統初始化、秘密的分發、秘密的重構、秘密的更新4個階段構成。

1.1 系統初始化

系統中包含一個秘密分發者和n個參與者。用U表示由n個參與者構成的集合，并且U由集合構成，即

設E(Fq)是一條橢圓曲線，G1是該曲線上的一個α階子群，其中α為質數。G為α階循環子群，G2=G－{0}。令e:G1×G1→G2上的雙線性映射，秘密分發者選擇G1的一個生成子g，同時選擇加密哈希函數h: G1→，將＜α，G1，G2，e，g，h＞發布在公告欄，同時公布參與者的數目。秘密分發者隨機秘密選取2k－ 1個隨機數a0，a1，…，a2k－2，構造多項式［8］:。秘密分發者計算，并將公開。

每個參與者Ui(i=0，1，2，…，n－1)下載公告欄上的信息，隨機選取秘密整數si∈，計算公鑰Ui=sig，并將Ui發回給秘密發送者，以保證不同的參與者使用不同的密鑰。秘密分發者將Ui(i=1，2，…，n－1)公布在公告欄。

1.2 秘密分發

計算

秘密分發者將Ii(i=1，2，…，n－1)公布在布告欄上。

1.3 秘密重構

為了將t份秘密重構，需要t個參與者提供他們的ssig(i=H1，H2，…，Ht)值。每個參與者Ui(i=1，2，…，t－1)首先從公告欄上下載sg，并計算ssig，然后利用哈希函數h生成矩陣M的第i行，最后參與者將該行信息發送給秘密合成者。這樣，授權子集內的各參與者合作，可列出方程M*X=I。

1.4 秘密更新

秘密分發者重新選擇共享秘密的門限和參數s，秘密更新如下:

1.5 成員的增加和刪除

在秘密沒有恢復前，如果有參與者因某些原因要被刪除。此時秘密分發者將其公開信息從公告欄上刪除，然后秘密分發者隨機選擇s∈，對所有的Ui(i=0，1，…，n－2)，使用哈希函數h，構造一個(n－1)*t的矩陣M，重復執行1.2步驟。

2 分析與討論

2.1 安全性分析

(1)參與者提供的秘密分量是可驗證的，并且驗證并不需要復雜的算法或更多的信息。秘密的重構者只需驗證e(ssig，g)≡e(sg，Ui)是否成立。如果成立，則參與者提供的信息是有效的，否則信息是無效的。同時也可以識別出無效的參與者。

(2)當多于t個參與者提供其秘密信息時，秘密是可重構的。首先通過等式e(ssig，g)≡e(sg，Ui)來驗證參與者提供的信息是否有效，然后將參與者提供的信息進行重構，將秘密恢復。

(3)參與者提交給秘密分發者的信息Ui(=sig)是安全的。由于算法是基于橢圓曲線離散對數問題，所以參與者的個人信息si是不會泄密的。

(4)可檢驗秘密分發者是否誠實。各參與者在收到自己的子秘密之后，可根據公開的信息，驗證式是否成立。如果成立，說明秘密分發者分發的是正確子秘密。這是因為，第j等級的用戶的多項式進行kj－1次f函數運算后，多項式中原本次數低于kj－1的項降為0，其后各項分別為kj－1≤t≤k－1。所以有:

2.2 性能分析

(1)與Chen et al.'s秘密共享機制相比，Chen et al.'s秘密共享機制中的共享秘密需通過哈希函數h(rp)生成。在本文的共享機制中，共享秘密的門限值t存儲在矩陣M，故大小由矩陣M的大小決定，秘密s在任何時候均存儲在矩陣X中，與哈希函數h無關。所以計算時間會縮短。

(2)與Chen et al.'s秘密共享機制相比，Chen et al.'s秘密共享機制中，矩陣M會以(n－t+1)×(n+t)增大，而X矩陣會以(n+t)×1增大，此外，其門限值隨著秘密的重構會改變為2t－1;在本文的共享機制中，矩陣M和X的大小不會改變，且秘密更新也非常方便，秘密分發者只需選擇新的門限值t′，s′，進而構造新的矩陣M′，X′，V′，I′，故多秘密共享在本方案中所需的空間不會發生改變。

(3)秘密重構的門限是可變的。秘密分發者只需改變矩陣M和X的大小，秘密重構的門限就可以改變。

表1 本文協議與Chen et al.'s協議的比較

3 結論

本文提出了一種的新的多秘密共享方案，該方案允許每個參與者只需保存一個秘密信息就能共享多個秘密。降低了秘密分發者的算法難度。秘密重構時，參與者只需提供公共信息和個人的秘密信息，就可實現秘密的重構。當門限發生改變時，秘密分發者只需調整一個矩陣的大小。此外，該方案對參與者的驗證加強了該方案的健壯性。由于方案是基于橢圓曲線，故其安全性較高，算法的效率也較高。

［1］CHIEN H Y，JAN J K，TSENG Y M.A practical(t，n)multi－secret sharing scheme［J］.IEICE Transaction on Fundamentals，2000，83(12):2 762－2 765.

［2］SHAMIR A.How to share a secret［J］.Communications of the ACM，1979，22(11):612－613.

［3］BLAKLEY G.Safeguarding Cryptographic Keys［C］//New York:Proceedings of the AFIPS 1979 National Computer Conference，1979:313－317.

［4］CHOR B，GOLDWASSER S，MICALI S，et al.Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults［C］//Proc of the 26th IEEE Symposium on Foundations of Computer Sciences.Los Angeles，USA:IEEE Computer Society，1985.

［5］TASSA T.Hierarchical threshold secret sharing［J］.Journal of Cryptolo－gy，2007，20(2):237－264.

［6］許春香，肖鴻，肖國鎮.安全的門限秘密共享方案［C］//第八屆中國密碼學學術會議論文集.北京:科學出版社，2004: 120－124.

［7］龐遼軍，李慧賢.動態門限多重秘密共享方案［J］.計算機工程，2008，34(15):164－165.

［8］毛穎穎，毛明，李冬冬.安全的多等級門限秘密共享［J］.計算機工程與應用，2009，45(32):90－92.

［9］CHEN W，LONG X，BAI Y B，GAO X P.A New Dynamic Threshold Secret Sharing Scheme from Bilinear Maps［R］.In International Conference on Parallel Processing Workshops，2007:19.

(責任編輯 劉棉玲)

Verifiable Dynamic Multi－secret Sharing Scheme

Zhao Liping，Tang Wenliang

(School of Software Engineering，East China Jiaotong University，Nanchang 330013，China)

The paper proposes a new verifiable multi－secret sharing scheme of dynamic threshold.The security of the proposed scheme is based on Shamir＇s secret sharing scheme and the ECIES cryptosystem，and the difficulty in solving the elliptic curve discrete logarithm.In the scheme，the secret will change periodically and the dealer will periodically publish some of the information to increase the robustness of system.The dealer could adjust the threshold value depending on the secure level of different secret.In addition，the efficient solutions against multiform cheating of any participant are proposed，and the participants can verify the information which they have received.Each participant uses his own private secret during different time periods to reconstruct the corresponding shared secrets without revealing their own private information.Public information is renewed periodically in the scheme，which will not influence new secret sharing.

threshold;elliptic curve;secret sharing;multi－secret

TP393.08

A

1005－0523(2010)04－0063－05

2010－03－16

江西省南昌市科技課題經費資助項目(洪財企［2008］68號)

趙麗萍(1981－)，女，碩士研究生，助教，主要研究方向為軟件工程、信息安全。