趙麗萍，湯文亮

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

可驗(yàn)證的動(dòng)態(tài)多秘密共享

趙麗萍，湯文亮

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

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

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

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

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

1 方案描述

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

1.1 系統(tǒng)初始化

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

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

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

1.2 秘密分發(fā)

計(jì)算

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

1.3 秘密重構(gòu)

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

1.4 秘密更新

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

1.5 成員的增加和刪除

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

2 分析與討論

2.1 安全性分析

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

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

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

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

2.2 性能分析

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

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

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

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

3 結(jié)論

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

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

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

［8］毛穎穎，毛明，李冬冬.安全的多等級(jí)門限秘密共享［J］.計(jì)算機(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)費(fèi)資助項(xiàng)目(洪財(cái)企［2008］68號(hào))

趙麗萍(1981－)，女，碩士研究生，助教，主要研究方向?yàn)檐浖こ獭⑿畔踩?/p>