可驗證的動態(tài)多秘密共享

趙麗萍，湯文亮

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

可驗證的動態(tài)多秘密共享

趙麗萍，湯文亮

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

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

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

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

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

1 方案描述

方案由系統(tǒng)初始化、秘密的分發(fā)、秘密的重構(gòu)、秘密的更新4個階段構(gòu)成。

1.1 系統(tǒng)初始化

系統(tǒng)中包含一個秘密分發(fā)者和n個參與者。用U表示由n個參與者構(gòu)成的集合，并且U由集合構(gòu)成，即

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

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

1.2 秘密分發(fā)

計算

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

1.3 秘密重構(gòu)

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

1.4 秘密更新

秘密分發(fā)者重新選擇共享秘密的門限和參數(shù)s，秘密更新如下:

1.5 成員的增加和刪除

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

2 分析與討論

2.1 安全性分析

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

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

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

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

2.2 性能分析

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

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

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

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

3 結(jié)論

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

［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］許春香，肖鴻，肖國鎮(zhèn).安全的門限秘密共享方案［C］//第八屆中國密碼學(xué)學(xué)術(shù)會議論文集.北京:科學(xué)出版社，2004: 120－124.

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

［8］毛穎穎，毛明，李冬冬.安全的多等級門限秘密共享［J］.計算機工程與應(yīng)用，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.

(責(zé)任編輯 劉棉玲)

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

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

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