韋性佳，張京花，蘆殿軍

(青海師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，青海 西寧 810008)

0 引 言

秘密共享作為一種基礎(chǔ)的密碼學(xué)手段，在信息安全方面扮演著非常重要的角色。自從1979年Shamir[1]提出基于拉格朗日插值多項(xiàng)式門限秘密共享方案之后，有關(guān)秘密共享方面的研究受到了廣大研究者的高度關(guān)注。

1985年Chor等[2]提出了可驗(yàn)證的秘密共享方案(VSS)的理念。1992年P(guān)edersen[3]在前人的基礎(chǔ)上提出了一種更為簡(jiǎn)潔、實(shí)用的VSS方案。起初的VSS方案存在計(jì)算量大、效率相對(duì)較低等缺陷，直到Neal Koblitz等[4]發(fā)現(xiàn)有限域上橢圓曲線離散對(duì)數(shù)問題是難解的以后，橢圓曲線(elliptic curve，ECC)以它計(jì)算量小、效率高等優(yōu)勢(shì)迅速成為密碼學(xué)研究的一個(gè)重要工具。

1989年，Brickell[5]提出了一種基于向量空間存取結(jié)構(gòu)的秘密共享方案。在這方面，張福泰等[6-8]基于雙線性變換提出的秘密共享方案對(duì)文中的研究具有重要的啟發(fā)作用。

1997年，Anderson[9]提出了前向安全性(forward security)理論,該理論可以有效地減少因?yàn)槊孛苄孤秾?duì)系統(tǒng)安全所帶來的隱患。在此基礎(chǔ)上，1999年Bellare[10]提出了一種前向安全的數(shù)字簽名方案。近年來，王彩芬等[11]提出了具有前向安全性的秘密共享方案，基于有限域上離散對(duì)數(shù)難解問題和強(qiáng)RSA假設(shè)[12-13]，有效地實(shí)現(xiàn)了秘密的前向安全性，并且該方案具有很強(qiáng)的實(shí)踐價(jià)值。

在已有秘密共享方案[14-16]研究成果的基礎(chǔ)上，文中提出了一種基于ECC的具有前向安全性質(zhì)的VSS方案。該方案利用橢圓曲線計(jì)算量小、效率高的優(yōu)點(diǎn)，同時(shí)充分發(fā)揮前向安全理論在秘密保護(hù)方面的優(yōu)勢(shì)，為秘密共享方案提供了雙重的安全保障。同時(shí)該方案是基于向量空間的存取結(jié)構(gòu)，在秘密的重構(gòu)中更加安全、有效。

1 基礎(chǔ)知識(shí)

1.1 橢圓曲線離散對(duì)數(shù)問題(ECDLP)

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

1.2 前向安全性理論

前向安全性理論(forward security theory)具體分析如下：

(1)Hi(i=1,2,…,n)將S的有效期分為T(1,2,…,T)個(gè)時(shí)間段；

(2)在整個(gè)有效期內(nèi)，公鑰PKU不變，但第j個(gè)時(shí)間段私鑰SKU隨著時(shí)間段j的改變而改變；

(3)在第j個(gè)時(shí)段，Hi計(jì)算Sj=f(Sj-1)，其中f是一個(gè)單向函數(shù)；

(4)算出Sj后，立即刪除Sj-1，這樣即使攻擊者A獲得了第j個(gè)時(shí)間段的Sj后也不能獲得關(guān)于S0,S1,…,Sj-1的任何信息。

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

H:參與者集合;

Hi：第i個(gè)參與者(Hi∈H,i=1,2,…,n)；

D:可信中心，且D?H;

S0:初始秘密；

Sj:第j個(gè)時(shí)間段的秘密;

T：時(shí)間周期；

1.4 向量空間存取結(jié)構(gòu)

2 提出的方案

2.1 系統(tǒng)初始化

然后，D廣播ψ(D),且將ψ(Hi)發(fā)送給Hi(i=1,2,…,n)。

初始子秘密Si0=(A+B)·ψ(Hi)=Ki0+Ri0(i=1,2,…,n)，其中Ki0=ψ(Hi)·A=ai1(P+x1Q)+…+ait(P+xtQ)=a1A1+…+atAtRi0=ψ(Hi)·B=ai1(P+x1R)+…+ait(P+xtR)=ai1B1+…+aitBt。

E0=gK0+hR0，Ej=gAj+hBj后，D廣播g,h,E0,Ej(j=1,2,…,t)，且通過秘密信道將(Ri0,Ki0)，Si0發(fā)送Hi(i=1,2,…,n)。

(3)第j個(gè)時(shí)間段的共享秘密Sj=2j(A+B)·ψ(D)(j=0,1,…,T)

2.2 子秘密更新

令Sij=2Si(j-1)(i表示第i個(gè)參與者,j表示第j個(gè)時(shí)間段)。

注:(1)每個(gè)成員Hi通過非交互式的方式來更新自己在第j個(gè)時(shí)間段的子秘密；

(2)當(dāng)更新Sij后，立即刪除Si(j-1)。

2.3 秘密的驗(yàn)證

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

(1)驗(yàn)證可信中心D的正確性(初始階段)。

對(duì)于任意一個(gè)參與者Hi，通過式(1)來驗(yàn)證可信中心D的正確性：

(1)

(2)參與者Hi通過式(2)驗(yàn)證可信中心D發(fā)送給自己的信息的正確性：

(2)

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

D計(jì)算S=h1(2T+1S0),SPi=h1(2T+1Si0)(i=1,2,…，n),并廣播S,SPi。

(1)用戶Hi驗(yàn)證自己在第j個(gè)時(shí)間段的子秘密進(jìn)化是否有效。

每個(gè)成員Hi檢驗(yàn)：

h1(2T+1-jSij)=SPi

(3)

若式(3)成立，則Hi證明自己在第j個(gè)時(shí)間段的子秘密進(jìn)化是有效的。

(2)合格子集驗(yàn)證第j個(gè)時(shí)間段所恢復(fù)的秘密Sj是否正確。

h1(2T+1-jSj)=S

(4)

若式(4)成立，則合格子集可以確定在第j個(gè)時(shí)間段恢復(fù)的共享秘密Sj是正確的。

2.4 秘密的恢復(fù)

任意一個(gè)授權(quán)子集(成員個(gè)數(shù)必須≥t)聯(lián)合起來，利用每個(gè)成員的秘密份額可以恢復(fù)秘密，其過程為：

(1)為不失一般性，取重構(gòu)成員H={H1,H2,…,Ht}，這t個(gè)成員利用ψ(Hi)，根據(jù)向量空間存取結(jié)構(gòu)，有如下等式：

ψ(D)=ψ(H)·CT

(5)

其中，C=(c1,c2,…,ct)；ψ(H)={ψ(H1),ψ(H2),…,ψ(Ht)}。

然后利用式(5)解出向量C。

3 安全性及正確性分析

3.1 方案的正確性

定理1：在初始階段，式(1)可驗(yàn)證可信中心D的正確性，式(2)可驗(yàn)證D發(fā)給參與者Hi的信息的正確性。

證明：根據(jù)已知條件Ej=gAj+hBj，代入等式右側(cè)，則有：

g(a1A1+…+atAt)+

h(a1B1+…+atBt)=

gK0+hR0=E0

由此可得E0,Ej(j=1,2,…,t)是正確的。

同理可證式(2)成立，如下：

(gA1+hB1)ai1+(gA2+hB2)ai2+…+

(gAt+hBt)ait=g(ai1A1+…+aitAt)+

h(ai1B1+…+aitBt)=

gKi0+hRi0

因此D發(fā)給參與者Hi的信息是正確的。

定理2：方案中子秘密更新階段的驗(yàn)證過程是正確的，即：式(3)、式(4)是正確的。

證明：Sij=2jSi0

h1(2T+1-jSij)=h1(2T+1-j·2jSi0)=h(2TSi0)=SPi

即式(3)成立，則說明子秘密的更新是正確的。

同理

Sj=2j(A+B)·ψ(D)=2jS0

h1(2T+1-jSj)=h1(2T+1-j·2jS0)=S

即等式(4)成立，說明合格子集恢復(fù)的共享秘密是正確的。

3.2 方案的安全性

定理3：系統(tǒng)中的公開信息不會(huì)揭示關(guān)于共享秘密Sj與子秘密Sij的任何信息。

定理4:只有有效的合格子集(成員個(gè)數(shù)必須≥t)方能構(gòu)造出秘密Sj。

證明：根據(jù)向量空間存取結(jié)構(gòu)的定義，不失一般性地取重構(gòu)成員為H1,H2,…,Ht，于是有：ψ(D)=c1ψ(H1)+…+ctψ(Ht)。

如果秘密重構(gòu)成員的個(gè)數(shù)小于t，根據(jù)線性方程組的性質(zhì)，方程組(6)的解不唯一，即存在無窮多個(gè)解，則要解出系數(shù)c1,c2,…,ct是不可行的，所以至少需要t個(gè)合格成員聯(lián)合起來，方能解下列方程組：

(6)

計(jì)算出系數(shù)c1,c2,…,ct后，利用式(7)計(jì)算并恢復(fù)出在第j個(gè)時(shí)間段的秘密。

Sj=2j(A+B)ψ(D)=

2j(A+B)(c1ψ(H1)+…+ctψ(Ht))=

c12jS10+c22jS20+…+ct2jSt0=

c1S1j+c2S2j+…+ctStj

(7)

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

證明：該方案所具有的前向安全性具體體現(xiàn)在參與者所持子秘密的前向安全性及秘密信息的前向安全性。

在子秘密的更新階段，假設(shè)敵手通過某種方式獲得參與者Hi在第j個(gè)時(shí)間段的子秘密Sij，若要計(jì)算Sik(k=1,2,…j-1)，由于子秘密是參與成員通過非交互的方式更新產(chǎn)生的，并且參與者在更新子秘密后，立即刪除了前一時(shí)間段的秘密。所以即使敵手掌握了第j個(gè)時(shí)間段的子秘密Sij，要想破解前j個(gè)時(shí)間段內(nèi)的子秘密就必須面對(duì)橢圓曲線離散對(duì)數(shù)的難解問題，這樣就保障了子秘密的前向安全性。

同理即便攻擊者得到了第j個(gè)時(shí)間段的秘密Sj=2j(A+B)·ψ(D),若要通過Sj計(jì)算Sk(k=1,2,…,j-1)，他將面臨同樣的問題。

4 方案的計(jì)算成本

設(shè)ρ代表G1中的標(biāo)量乘法運(yùn)算，結(jié)果如表1所示。該方案的運(yùn)行時(shí)間復(fù)雜度為O(n)，即在多項(xiàng)式時(shí)間范圍內(nèi)。說明方案的計(jì)算成本較低。

表1 方案的計(jì)算量分析

5 結(jié)束語

在文獻(xiàn)[6，11]的基礎(chǔ)上，基于向量空間存取結(jié)構(gòu)提出了一種具有前向安全性的秘密共享方案，無論是在系統(tǒng)的安全性方面，還是在計(jì)算效率方面都有一定的提升。如果秘密在被動(dòng)泄露的情況下，該方案可以避免秘密持有者的抵賴行為，檢查出欺詐行為，同時(shí)該方案利用前向安全性理論保障了系統(tǒng)的前向安全性。

參考文獻(xiàn):

[1] SHAMIR A.How to share a secret[J].Communication of the ACM,1979,22(11):612-613.

[2] 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.Washington,DC,USA:IEEE Computer Society,1985:383-395.

[3] PEDERSON T P.Non-interactive and information-theoretic secure verifiable secret sharing[C]//Proceedings of the 11th annual international cryptology conference on advances in cryptology.London,UK:Springer-Verlag,1992:129-140.

[4] NEAL K.Elliptic curve cryptosystems[J].Mathematics of Computation,1987,48(177):203-209.

[5] BRICKELL E F. Some ideal secret sharing schemes[J].Journal of Combinatorial Mathematics & Combinatorial Computing,1989,434:468-475.

[6] ZHANG F,ZHANG J.Efficient and information-theoretical secure verifiable secret sharing over bilinear groups[J].Chinese Journal of Electronics,2014,23(1):13-17.

[7] 張福泰.基于向量空間接入結(jié)構(gòu)的分布式密鑰生成[J].電子學(xué)報(bào),2005,33(5):816-819.

[8] 張福泰,王育民.適用于任意接入結(jié)構(gòu)的可驗(yàn)證多秘密分享方案[J].通信學(xué)報(bào),2007,28(11):59-64.

[9] ANDERSON R. Two remarks on public-key cryptology[C]//Fourth ACM conference on computer and communications security.[s.l.]:[s.n.],1997.

[10] BELLARE M,MINER S.A forward-secure digital signature scheme[C]//Proceedings of CRYPTO’99.Berlin:Springer-Verlag,1999:431-448.

[11] 王彩芬，劉軍龍，賈愛庫(kù)，等.具有前向安全性質(zhì)的秘密共享方案[J].電子與信息學(xué)報(bào),2006,28(9):1714-1716.

[12] 汪保友,胡運(yùn)發(fā).基于強(qiáng)RSA假設(shè)的簽名方案[J].軟件學(xué)報(bào),2002,13(8):1729-1734.

[13] 徐文華,賀前華,李 韜.基于強(qiáng)RSA假設(shè)的數(shù)字簽名方案[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2008,36(12):24-26.

[14] 蘆殿軍，張秉儒，趙海興.基于多項(xiàng)式秘密共享的前向安全門限簽名方案[J].通信學(xué)報(bào),2009,30(1):45-49.

[15] 田有亮，馬建峰，彭長(zhǎng)根，等.橢圓曲線上的信息論安全的可驗(yàn)證秘密共享方案[J].通信學(xué)報(bào),2011,32(12):96-102.

[16] 李慧賢,蔡皖東,裴慶祺.可驗(yàn)證秘密共享方案的設(shè)計(jì)與分析[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,2008,35(1):148-151.