李潔平，韋性佳

0 引 言

秘密共享是密碼學(xué)的一個(gè)重要工具。1979年，Shamir[1]和Blakley[2]兩人分別基于拉格朗日多項(xiàng)式和射影幾何理論，提出了兩種不同的秘密共享方案，對(duì)現(xiàn)代密碼學(xué)的研究具有非常重要的作用。之后，有關(guān)秘密共享方面的研究成為許多研究者的課題。1983年，Asmuth和Bloom[3]等人基于中國(guó)剩余定理提出了一種的新秘密共享方案。該方案結(jié)構(gòu)簡(jiǎn)明，理論知識(shí)容易理解，且較Shamir的秘密共享方案效率更高。

1985年，Chor等人[4]第一次提出可驗(yàn)證的理念,并且構(gòu)造了一種可驗(yàn)證的秘密共享方案。1992年，Pedersen[5]提出了一種更方便和實(shí)用的秘密共享方案。但是，早期的秘密共享方案存在計(jì)算量大、效率相對(duì)較低等問(wèn)題。直到Neal Koblitz[6]等人發(fā)現(xiàn)在有限域上橢圓曲線離散對(duì)數(shù)問(wèn)題（ECDLP）是難解問(wèn)題后，橢圓曲線（Elliptic Curve，簡(jiǎn)稱ECC）就以它計(jì)算量小、效率較高等優(yōu)勢(shì)快速成為密碼學(xué)研究的一個(gè)重要工具。2005年，Qing.L[7]等人提出了一個(gè)基于中國(guó)剩余定理的可驗(yàn)證秘密共享方案。該方案只有在秘密分發(fā)者誠(chéng)實(shí)的情況下，檢測(cè)出參與者之間的欺騙。

1997年，Anderson[8]首次提出前向安全性理論（Forward Security）；2001年，Itkis和 Reyzin[9]提出一種前向安全簽名方案，實(shí)現(xiàn)了有效的簽名驗(yàn)證和存儲(chǔ)，但效率相對(duì)較低。2002年，Kozlov[10]等人利用一種快速更新算法，提出了一種前向安全的簽名方案，不僅周期短，而且適合移動(dòng)計(jì)算。目前，國(guó)內(nèi)學(xué)者對(duì)前向安全性理論也做了大量研究，如王彩芬等人[11]提出的具有前向安全性的秘密共享方案,基于有限域上離散對(duì)數(shù)難解問(wèn)題（ECDLP）和強(qiáng)RSA假設(shè)，有效實(shí)現(xiàn)了秘密的前向安全性，且具有很強(qiáng)的實(shí)踐價(jià)值。本文方案在已有秘密共享方案[12-14]研究成果的基礎(chǔ)上，提出了一種基于中國(guó)剩余定理的可驗(yàn)證方案，利用橢圓曲線計(jì)算量小、效率高的優(yōu)勢(shì)，減少了方案的運(yùn)算成本，同時(shí)方案基于強(qiáng)RSA假設(shè)[15-16]，實(shí)現(xiàn)了方案的前向安全性。

1 預(yù)備知識(shí)

1.1 橢圓曲線離散對(duì)數(shù)問(wèn)題（ECDLP）

給定有限域GF(q)上的橢圓曲線E和生成元P∈E(GF(q))，且階為q，對(duì)?Q∈〈P〉，尋找a∈[0,q-1]，使得Q=aP，稱為橢圓曲線離散對(duì)數(shù)問(wèn)題。

1.2 雙線性變換

定義1：設(shè)(G1,+)和(G2,+)是2個(gè)階為素?cái)?shù)p的循環(huán)群，其中前者為加法群，后者為乘法群。令g為G的生成元，如果滿足以下性質(zhì)，則稱變換e∶G1×G1→ G2為雙線性變換：

（1）雙線性。對(duì)任意P1、P2和Q∈G1，有：

（2）非退化性。存在P∈G1即e(P,P)≠1，即e(P,P)是G2的生成元。

（3）可計(jì)算性。對(duì)任意P1、P2∈G1，存在有效的算法計(jì)算e(P1,P2)。

1.3 中國(guó)剩余定理（孫子定理）

給定一組兩兩互素的正整數(shù)m1,m2,…,mk和整數(shù)c1,c2,c3,…,ck，則同余方程組為：

對(duì)于模M具有唯一的解：

其中：

1.4 前向安全性理論

前向安全性理論（Forward Security Theory）具體如下：（1）Pi(i=1,2…n)將S的有效期分為T個(gè)時(shí)間段，1,2…T；（2）在整個(gè)有效期內(nèi)，公鑰PKU不變，但第j個(gè)時(shí)間段私鑰SKU隨著時(shí)間段j的改變而變換；（3）第j個(gè)時(shí)段時(shí)，Pi計(jì)算Sj=f (Sj-1)，其中f是一個(gè)單向函數(shù)；（4）算出Sj后，立即刪除Sj-1，這樣即使攻擊者A獲得了第j個(gè)時(shí)間段的Sj，也不能獲得關(guān)于S0,S1,…,Sj-1的任何信息，如圖1所示。

圖1 密鑰更新流程

1.5 系統(tǒng)中的記號(hào)與參數(shù)

P：參與者符號(hào)，而Pi為第i個(gè)參與者，有Pi∈ P,i=1,2,…,n；

D：秘鑰分配者，且D?P；

K：要分享的秘密（初始者）。

2 提出方案

2.1 系統(tǒng)初始化

（1）D選擇mi∈i=1,2,…,n 且 (mi,mj)=1,mi為素?cái)?shù)；選擇初始共享秘密x0∈

（2）計(jì)算如下參量：

①秘密份額：

（3）公開(kāi)系統(tǒng)公鑰：

將(ci,0,mi,0)作為私鑰份額通過(guò)秘密通道發(fā)送給用戶Pi。

2.2 子秘密的更新

當(dāng)Pi收到初始私密份額(ci,0,mi,0)后，計(jì)算ci,j=作為第j個(gè)時(shí)間段的子份額，然后立即刪除, j=1,2…T。

2.3 秘密的驗(yàn)證

2.3.1 初始階段秘密的驗(yàn)證

Pi選擇ki,0∈RZ*q，計(jì)算初始公鑰：

然后，進(jìn)行D驗(yàn)證：

若等式成立，則Pi誠(chéng)實(shí)的；同樣，Pi通過(guò)等式可驗(yàn)證D的份額(ci,0,mi,0)是有效的。

2.3.2 驗(yàn)證更新子秘密

這個(gè)階段，用戶Pi通過(guò)下面過(guò)程研究第j個(gè)時(shí)間段秘密份額的有效性：

然后，驗(yàn)證 e ( P , Qi,j) =?e( Mi, Ki) e( Ci, Ki)。若等式成立，D可以驗(yàn)證Pi更新子秘密的正確性，而Pi也可以驗(yàn)證D的誠(chéng)實(shí)性。

3 秘密恢復(fù)

第j個(gè)時(shí)間段，所有用戶{P1,P2,…,Pn}利用自己的秘密份額(ci,j,mi)，合作完成如下過(guò)程：

（1）計(jì)算 M=m1m2…mn；

（3）利用中國(guó)剩余定理，計(jì)算第j個(gè)時(shí)間段的共享秘密：

當(dāng)秘密恢復(fù)成員計(jì)算出共享秘密后，計(jì)算：

（1）得到第j個(gè)時(shí)間段的共享秘密xj；

（2）利用式（9）中的共享秘密xj和系統(tǒng)公鑰X，驗(yàn)證等式：

若等式成立，則說(shuō)明恢復(fù)的共享秘密是有效的。

4 正確性及安全性分析

4.1 方案的正確性

定理1：方案在初始階段秘密驗(yàn)證了Pi和D是誠(chéng)實(shí)的，即等式（8）正確。

證明：根據(jù)已知條件，有：

等式成立。

證明：根據(jù)已知條件，有：

等式成立。

定理3：方案中秘密恢復(fù)的驗(yàn)證是正確的，即等式（10）正確。

等式成立，所以恢復(fù)的秘密是正確的。

4.2 方案的安全性

定理4：公鑰{Ci,0,Mi,Xj,Ci,Ki,Qi,j}不會(huì)泄露私鑰{ki,j,ci,j,mi,xj}的任何信息。

證明：若敵手已知 Ci,0、Mi、Ci、Ki、Qi,j想獲取私鑰ki,j、ci,j、mi，由于Ki,j=ki,jP，Ci,j=ci,jP，Qi,j=ki,j(mi+ci,j)P，Mi=miP，則必須解決橢圓曲線離散對(duì)數(shù)問(wèn)題。但是，ECDLP是難解決的。所以，敵手無(wú)法通過(guò)公鑰獲取得到私鑰的任何信息。

定理5：方案具有前向安全性

假設(shè)敵手已經(jīng)掌握第j個(gè)時(shí)間段的共享密鑰xj,想要獲取前j個(gè)時(shí)間段的共享秘密xl,l=0,1,…, j-1，有兩種方式：

（1）若想通過(guò)Xl=xlP解出xl，必須解決橢圓曲線離散對(duì)數(shù)問(wèn)題。但是，ECDLP是難解決的。所以，敵手無(wú)法獲得前j個(gè)時(shí)間段xl；

5 結(jié) 語(yǔ)

本文利用中國(guó)剩余定理，提出了一種具有前向安全的可驗(yàn)證秘密共享方案。該方案的創(chuàng)新之處在于：在秘密更新階段，將強(qiáng)RSA問(wèn)題融入子秘密的更新即，每個(gè)用戶利用自己的私鑰通過(guò)非交互式的方式更新自己的份額，極大地節(jié)省了可信中心的運(yùn)算量；方案實(shí)現(xiàn)了參與者的可驗(yàn)證性，利用基于橢圓曲線的雙線性對(duì)每個(gè)時(shí)間段的參與者實(shí)現(xiàn)互相驗(yàn)證，這樣可以及時(shí)檢測(cè)出系統(tǒng)中的欺詐行為，保障系統(tǒng)的安全性。

[1] Shamir A.How to Share a Secret[J].Communication of the ACM 1979,22(11):612-613.

[2] Blakley G R.Safeguarding Cryptographic Keys[C].Proceedings of AFIPS 1979 National Computer Conference,1979:313-317.

[3] Asmuth C,Bloom J.A Modular Approach to Key Safeguarding[J].IEEE Transactions on Information Theory,1983,29(02):208-210.

[4] Chor B,Doldwasser S,Micali S,et al.Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults[C].Proceedings of the 26th IEEE Symposium on Foundations of Computer Sciences,1985:383-395.

[5] Pedersen T P.Non-interactive and Informationtheoretic Secure Verifiable Secret Sharing[C].Cryptology CRYPTO’91,1992:129-140.

[6] Koblitz N.Elliptic Curve Cryptosystems [J].Mathematics of Computation,1987,48(48):203-209.

[7] Qiong L,Zhifang W,Xiamu N.et al.A Non-interactive Modular Verifiable Secret Sharing Scheme[C].In ICCCAS 2005:International Conferenc on Communications,Circuits and Systems,2005:84-87.

[8] Anderson R.Two Remarks on Public-key Cryptology[C].Fourth ACM Conference on Computer and Communications Security,1997.

[9] Itkis G,Reyzin L.Forward-secure Signatures with Optimal Signing and Verifying[C].Intenational Cryptology Conference on Advances in Cryptology,2001:332-354.

[10] Kozlov A,Reyzin L.Forward-secure Signature with Fast Key Update[C].International Conference on Security in Communication Networks,2002:241-256

[11] 王彩芬,劉國(guó)軍,賈愛(ài)庫(kù)等.具有前向安全性質(zhì)的秘密共享方案[J].電子與信息學(xué)報(bào),2006,9(28):1974-1976.WANG Cai-fen,LIU Guo-jun,JIA Ai-ku,et al.A Secret Sharing Scheme with Forward Security[J].Journal of Electronics & Information Technolo gy,2006,9(28):1974-1976.

[12] 蘆殿軍,張秉儒,趙海興.基于多項(xiàng)式秘密共享的前向安全門限簽名方案[J].通信學(xué)報(bào),2009,30(01):45-49. LU Dian-jun,ZHANG Bing-ru,ZHAO Hai-xing.Forward-secure Threshold Signature Scheme Based on Polynomial Secret Sharing[J].Journal on Communicatio ns,2009,30(01):45-49..

[13] 田有亮,馬建峰,彭長(zhǎng)根等.橢圓曲線上的信息論安全的可驗(yàn)證秘密共享方案[J].通信學(xué)報(bào),2008,29(10):45-50.TIAN You-liang,MA Jian-feng,PENG Chang-gen,et al.Information-theoretic Secure Verifiable Secret Sharing Scheme on Elliptic Curve Group[J].Journal on Communic ations,2008,29(10):45-50.

[14] 李慧賢,蔡皖東,裴慶祺.可驗(yàn)證秘密共享方案的設(shè)計(jì)與分析[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,2008,35(01):148-151.LI Hui-xian,CAI Wan-dong,PEI Qing-qi.Design and Analysis of a Verifiable Secret Sharing Scheme[J].Journal of Xidian University(Natural Science Edition),2008,35(01):148-151.

[15] 汪保友,胡運(yùn)發(fā).基于強(qiáng)RSA假設(shè)的簽名方案[J].軟件學(xué)報(bào),2002,13(08):1729-1734.LI Hui-xian,HU Yun-Fa.Signature Scheme Based on Strong RSA Hypothesis[J].Journal of Software,2002,13(08):1729-1734.

[16] 徐文華,賀前華,李韜.基于強(qiáng)RSA假設(shè)的數(shù)字簽名方案[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2008,36(12):24-26.XU Wen-hua,HE Qian-hua,LI Tao.Signature Scheme Based Strong RSA Assumption[J].J. Huazhong Univ. of Sci.& Tech.(Natural Science Edition),2008,36(12):24-26.