基于ECC的具有前向安全性的VSS方案

韋性佳，張京花，蘆殿軍

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

0 引 言

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

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

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

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

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

1 基礎知識

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

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

1.2 前向安全性理論

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

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

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

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

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

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

H:參與者集合;

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

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

S0:初始秘密；

Sj:第j個時間段的秘密;

T：時間周期；

1.4 向量空間存取結構

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個時間段的共享秘密Sj=2j(A+B)·ψ(D)(j=0,1,…,T)

2.2 子秘密更新

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

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

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

2.3 秘密的驗證

2.3.1 初始階段秘密的驗證

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

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

(1)

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

(2)

2.3.2 驗證更新秘密

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

(1)用戶Hi驗證自己在第j個時間段的子秘密進化是否有效。

每個成員Hi檢驗：

h1(2T+1-jSij)=SPi

(3)

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

(2)合格子集驗證第j個時間段所恢復的秘密Sj是否正確。

h1(2T+1-jSj)=S

(4)

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

2.4 秘密的恢復

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

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

ψ(D)=ψ(H)·CT

(5)

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

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

3 安全性及正確性分析

3.1 方案的正確性

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

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

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：方案中子秘密更新階段的驗證過程是正確的，即：式(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)成立，說明合格子集恢復的共享秘密是正確的。

3.2 方案的安全性

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

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

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

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

(6)

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

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

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

c12jS10+c22jS20+…+ct2jSt0=

c1S1j+c2S2j+…+ctStj

(7)

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

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

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

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

4 方案的計算成本

設ρ代表G1中的標量乘法運算，結果如表1所示。該方案的運行時間復雜度為O(n)，即在多項式時間范圍內。說明方案的計算成本較低。

表1 方案的計算量分析

5 結束語

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

參考文獻:

[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] 張福泰.基于向量空間接入結構的分布式密鑰生成[J].電子學報,2005,33(5):816-819.

[8] 張福泰,王育民.適用于任意接入結構的可驗證多秘密分享方案[J].通信學報,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] 王彩芬，劉軍龍，賈愛庫，等.具有前向安全性質的秘密共享方案[J].電子與信息學報,2006,28(9):1714-1716.

[12] 汪保友,胡運發(fā).基于強RSA假設的簽名方案[J].軟件學報,2002,13(8):1729-1734.

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

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

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

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