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

韋性佳，張京花，蘆殿軍

(青海師范大學 數學與統計學院，青海 西寧 810008)

0 引 言

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

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

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

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

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

1 基礎知識

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

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

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是一個單向函數；

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

1.3 系統中的記號與參數

H:參與者集合;

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

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

S0:初始秘密；

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

T：時間周期；

1.4 向量空間存取結構

2 提出的方案

2.1 系統初始化

然后，D廣播ψ(D),且將ψ(Hi)發送給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發送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發送給自己的信息的正確性：

(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 秘密的恢復

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

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

ψ(D)=ψ(H)·CT

(5)

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

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

3 安全性及正確性分析

3.1 方案的正確性

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

證明：根據已知條件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發給參與者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：系統中的公開信息不會揭示關于共享秘密Sj與子秘密Sij的任何信息。

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

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

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

(6)

計算出系數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：方案具有前向安全性。

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

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

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

4 方案的計算成本

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

表1 方案的計算量分析

5 結束語

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

參考文獻:

[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] 汪保友,胡運發.基于強RSA假設的簽名方案[J].軟件學報,2002,13(8):1729-1734.

[13] 徐文華,賀前華,李 韜.基于強RSA假設的數字簽名方案[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.