張 劍,林昌露,丁 健,林修慧,李朝珍

1(福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院,福州 350117)

2(福建師范大學(xué) 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點實驗室,福州 350007)

秘密共享是網(wǎng)絡(luò)通信中保護信息隱私性和安全性的一種非常有效的密碼技術(shù),通過秘密共享技術(shù)可以實現(xiàn)將秘密信息共享給多個參與者.1979年,Shamir[1]和Blakley[2]最先分別提出了門限秘密共享的概念.Shamir 則是利用有限域上的多項式設(shè)計的秘密共享方案,而Blakey 利用超幾何問題構(gòu)造了秘密共享方案.Benaloh和Leichter[3],Ito 等[4]分別提出基于授權(quán)集和非授權(quán)集的秘密共享方案,實現(xiàn)了一般存取結(jié)構(gòu)上的秘密共享.為了防止秘密共享中參與者的欺騙行為,Chor等[5]提出了可驗證的秘密共享方案,之后Stadler[6]提出了公開可驗證秘密共享方案.通常的秘密共享方案中,秘密分發(fā)者將秘密分為多份子秘密,并按照一定的分發(fā)方式發(fā)送給參與者,使得授權(quán)集中的參與者聯(lián)合時可以恢復(fù)秘密,非授權(quán)集中的參與者聯(lián)合時不能恢復(fù)秘密.這些秘密共享方案均為單秘密的共享方案,執(zhí)行一次共享算法只能共享一個秘密,但實際中經(jīng)常需要共享多個秘密,若采用這些共享方案則需要多次執(zhí)行共享算法,從而使計算、存儲和通信等方面的效率降低.

由于單秘密共享方案的局限性,使得眾多學(xué)者提出并研究多秘密共享.1994年,He和Dawson[7]基于單向函數(shù)提出了一個多階段的(t,n)-門限多秘密共享方案,執(zhí)行一次共享算法可共享多個秘密,但該方案被Geng等[8]證明子秘密不是多次使用的,恢復(fù)全部的秘密后,參與者所保存的子秘密信息完全泄露,即子秘密是一次性的.Shao[9]基于多項式方法提出了共享k個秘密的(k,t,n)-門限多秘密共享方案,只需少量的公開值即可,但該方案實現(xiàn)的多秘密共享在秘密恢復(fù)階段所有秘密同時恢復(fù),若參與者在保護秘密方面有疏漏,則有可能會造成秘密信息的泄露.Wang 等[10]提出了一個可驗證的門限多秘密共享方案,該方案在實現(xiàn)Shao 方案[9]功能的基礎(chǔ)上增加了參與者對分發(fā)者的驗證以及參與者之間的驗證功能,并且子秘密可重復(fù)使用.很多學(xué)者對可驗證秘密共享方案進行研究,曹陽等[11]提出了一種基于大整數(shù)分解可公開驗證的秘密共享方案,彭詠等[12]研究了一類基于格的可驗證秘密共享方案.Harn和Hsu[13]提出了基于雙線性多項式的(t,n)-門限多秘密共享方案,Zhang 等[14]證明了該方案在恢復(fù)一個秘密之后,其余未恢復(fù)的秘密可由t-1個參與者進行重構(gòu)得到,同時對其進行改進,提出了新的秘密共享方案并解決了Harn和Hsu[13]方案中的安全隱患.這些方案實現(xiàn)的多秘密共享對應(yīng)的存取結(jié)構(gòu)為單一門限的門限存取結(jié)構(gòu),事實上在不同的存取結(jié)構(gòu)中共享多個秘密具有更強的實用性,因此有很多學(xué)者研究了關(guān)于多存取結(jié)構(gòu)的多秘密共享方案.

2007年,Geng 等[8]在He和Dawson 方案[7]的基礎(chǔ)上進行改進,提出了多存取結(jié)構(gòu)上參與者子秘密可多次使用的門限多秘密共享方案,使得參與者子秘密在恢復(fù)一輪多秘密之后,子秘密的信息仍是保密的,從而子秘密具有可多次使用的性質(zhì).為了防止參與者在秘密恢復(fù)時的不誠實行為,Chen 等[15]提出了一個可驗證的門限多秘密方案,該方案可對參與者發(fā)送的子秘密進行驗證,防止參與者的欺騙行為,但子秘密不具有多次使用的性質(zhì).Mashhadi[16]基于線性反饋移位寄存器提出了一個多步的秘密共享方案,該方案在秘密重構(gòu)階段可采用求解范德蒙方程和計算Lagrange 插值兩種方法進行秘密恢復(fù),但秘密恢復(fù)必須按照固定的順序進行.Zarepour-Ahmadabadi 等[17]提出一個具有可信第三方的漸進門限秘密共享方案,多個秘密按照預(yù)設(shè)的順序進行重構(gòu),并且每個秘密對應(yīng)不同的存取結(jié)構(gòu),若秘密恢復(fù)順序為S1,S2,···,Sk,對應(yīng)的門限值逐漸變大,即S1門限值最小,Sk門限值最大.該方案與前面幾個多秘密方案相比公開值最少,但該方案需要借助可信第三方實現(xiàn)多秘密共享,參與者存儲的子秘密包含兩部分,且子秘密不具有多次使用的性質(zhì).考慮多秘密方案在公開值個數(shù)、多秘密恢復(fù)的順序性、存取結(jié)構(gòu)的多樣性以及子秘密的多使用性等方面存在的問題,本文提出一個更加高效的多秘密共享方案,具有如下特點:

(1)參與者存儲的子秘密只有一份;

(2)參與者的子秘密可多次使用;

(3)不同的秘密對應(yīng)不同的存取結(jié)構(gòu);

(4)秘密重構(gòu)時可按任意順序進行恢復(fù);

(5)實現(xiàn)多秘密的公開值個數(shù)少.

本文應(yīng)用中國剩余定理,將其作為公開值聚合的工具來減少公開值的個數(shù),基于多項式的方法提出了一個子秘密可多次使用的門限多秘密共享方案,其中參與者只需存儲一個子秘密即可,同時公開值的個數(shù)與其他方案相比也是最少的,并且不同的秘密可對應(yīng)不同的門限值,在秘密恢復(fù)時可以按照任意的順序進行秘密的重構(gòu),不需要按照特定的順序,具有更好的靈活性.

文中剩余部分按照如下安排:第1 節(jié)介紹相關(guān)的預(yù)備知識;第2 節(jié)介紹方案的具體構(gòu)造以及方案的安全性分析;第3 節(jié)對幾個多秘密共享方案進行比較分析;第4 節(jié)是方案的總結(jié).

1 預(yù)備知識

這一部分將分別對存取結(jié)構(gòu),中國剩余定理,離散對數(shù)問題和Shamir (t,n)-門限秘密共享方案等內(nèi)容進行簡單的介紹.

1.1 存取結(jié)構(gòu)

設(shè)n個參與者的集合為P={P1,P2,···,Pn},存取結(jié)構(gòu) Γ (?2P)為P的一族可以恢復(fù)出秘密S的子集的集合,這些集合稱為授權(quán)集,2P為P的冪集.不能恢復(fù)出秘密的參與者集合為非授權(quán)集,所有非授權(quán)集的集合為非存取結(jié)構(gòu),記作=2P-Γ.

存取結(jié)構(gòu)Γ 具有單調(diào)性,即:

對于一個(t,n)-門限秘密共享方案而言,任意大于等于t個參與者可恢復(fù)秘密S,任意小于t個參與者不能恢復(fù)秘密S,即其存取結(jié)構(gòu)為Γ={A?P||A|≥t}.

若一個秘密共享方案滿足:

(1)正確性:對于?A∈Γ,A中參與者的子秘密聯(lián)合可正確恢復(fù)出秘密S;

(2)安全性:對于?B∈,B中的參與者聯(lián)合不能得到關(guān)于秘密S的任何信息.

則稱該方案為完備的秘密共享方案[18].

1.2 中國剩余定理

中國剩余定理(Chinese Reminder Theorem)[19]又稱孫子定理,簡記為CRT,是中國古代求解一次同余式的方法.中國剩余定理基本內(nèi)容表述如下:

隨機選擇兩兩互素的整數(shù)m1,m2,···,mn,對于任意的整數(shù)r1,r2,···,rn,滿足ri∈Zmi(i=1,2,···,n),Zmi為整數(shù)模mi的剩余類群.則下列同余方程組:

在模M下有唯一解(modM),其中,Mi=M/mi,bi=Mi-1(modmi),記為Y=CRT(r1,r2,···,rn).

1.3 離散對數(shù)問題

設(shè) Fq為有限域,q為一個素數(shù),g為乘法群F*q中的生成元,任取一個整數(shù)k,則計算a=gk(modq)可 知a∈Fq.反之,已知a∈Fq,要計算k=logga(modq),稱為離散對數(shù)問題[20].

由于對一般階數(shù)較大的有限域上離散對數(shù)問題至今沒有一個高效的求解算法,所以在密碼方案的構(gòu)造過程中,總是假設(shè)在有限域上求解離散對數(shù)問題是困難的.

1.4 Shamir (t,n)-門限秘密共享方案

Shamir (t,n)-門限秘密共享方案[1]根據(jù)門限值t構(gòu)造t-1次 多項式,將秘密p＞n(p為大素數(shù),p＞n)作為常數(shù)項,計算n個點處的函數(shù)值作為n個參與者的子秘密.將秘密拆分為n份并發(fā)送給n個參與者P1,P2,···,Pn,使得任意大于等于t個參與者可以重構(gòu)出秘密S,任意少于t個參與者不能得到秘密S的任何信息.具體秘密分發(fā)及重構(gòu)過程如下:

秘密分發(fā)階段:

(1)分發(fā)者D選擇一個t-1次多項式

f(x)=a0+a1x+a2x2+...+at-1xt-1(modp),其中,a0=S為秘密值,a1,a2,···,at-1為隨機選擇的Fp中的元素;

(2)D計算f(i)作為參與者Pi(i=1,2,···,n)的子秘密,并通過安全信道分別發(fā)送給對應(yīng)的參與者.

秘密重構(gòu)階段:

(3)不妨假設(shè)進行秘密重構(gòu)的參與者為P1,P2,···,Pt,分別將子秘密f(1),f(2),···,f(t)安全地發(fā)送給秘密重構(gòu)者C;

(4)秘密重構(gòu)者C根據(jù)Lagrange 插值公式計算得到秘密:

Shamir (t,n)-門限秘密共享方案滿足:

(1)任意大于等于t個參與者可以根據(jù)Lagrange插值公式重構(gòu)出多項式f(x),從而可正確恢復(fù)出秘密S,滿足正確性;

(2)任意少于t個參與者無法重構(gòu)出多項式f(x),因此無法重構(gòu)得到關(guān)于秘密S的任何信息,滿足安全性條件.

因此,Shamir (t,n)-門限方案是完備秘密共享方案.

2 方案構(gòu)造與分析

本節(jié)介紹方案的具體構(gòu)造,證明了方案的正確性和安全性、子秘密可多次使用性.設(shè)k個秘密為S1,S2,···,Sk∈Fp,每個秘密Sj(j=1,2,···,k)對應(yīng)的存取結(jié)構(gòu)為門限值為tj的門限存取結(jié)構(gòu),即Γj={A?P||A|≥tj}.本文選擇轉(zhuǎn)換值的方法進行秘密隱藏,同時根據(jù)Shamir(t,n)-門限方案的分發(fā)算法為參與者提供偽子秘密,引入中國剩余定理將多項式生成的n個函數(shù)值進行聚合作為公開值,從而達到最大程度減少公開值個數(shù)的目的.

2.1 具體構(gòu)造

分發(fā)者選取素數(shù)p和兩兩互素的正整數(shù)m1,m2,···,mn,使得mi≥p(i=1,2,···,n).選擇滿足p|(q-1)的素數(shù)q,取Fq的p階元g,以及公開的單向Hash 函數(shù)h(·).

隨機選擇x1,x2,···,xn∈F*p為參與者P1,P2,···,Pn的公開信息.對秘密Sj(j=1,2,···,k)的共享如下:

(1)秘密分發(fā)階段

分發(fā)者進行如下操作:

① 隨機選擇元素aj,aj,1,aj,2,···,aj,tj-1∈Fp,構(gòu)造多項式fj(:x)=aj+aj,1x+aj,2x2+···+aj,tj-1xtj-1(modp);

② 計算fj(x)在x1,x2,···,xn處的值fj(x1),fj(x2),···,fj(xn),并根據(jù)中國剩余定理計算公開值:

PS j=C RT(fj(x1),fj(x2),···,fj(xn));

③ 根據(jù)g與隨機值aj,計算gaj(modp),計算并公開轉(zhuǎn)換值Vj=S j⊕gaj,這里⊕為比特的異或運算;

④ 將mi作為子秘密通過安全信道發(fā)送給參與者Pi,i=1,2,···,n,計算并公開秘密Sj的Hash 值hj=h(S j).

(2)秘密重構(gòu)階段

任意tj個 參與者Pj1,Pj2,···,Pjtj要重構(gòu)秘密Sj,參與重構(gòu)的參與者Pj,i(i=1,2,···,tj)發(fā)送偽子秘密S Hj,i(i=1,2,···,tj)給恢復(fù)者,由恢復(fù)者進行秘密的計算.參與者和恢復(fù)者分別進行以下操作:

① 參與者:參與秘密重構(gòu)的參與者Pj,i(i=1,2,···,tj)根據(jù)公開值PS j計 算fj(xj,i)≡PS j之后計算偽子秘密S Hj,i≡gfj(xj,i)(modp)并發(fā)送給恢復(fù)者.

② 恢復(fù)者:根據(jù)參與者發(fā)送的偽子秘密,恢復(fù)者計算:

(3)秘密驗證階段

參與者收到恢復(fù)者發(fā)送的秘密S j時,可通過驗證等式h(S j)=?hj是否成立來判斷所恢復(fù)秘密的正確性.

2.2 方案分析

本文方案的安全性與Shamir (t,n)-門限方案的安全性一致,同時方案的構(gòu)造是基于中國剩余定理的性質(zhì)和有限域上離散對數(shù)求解的困難性.定理2.1 證明了方案的正確性、安全性,定理2.2 分析了子秘密的可多次使用性.

定理2.1.在共享秘密S j時,本文構(gòu)造的方案是安全的(tj,n)-門限秘密共享方案.

證明:分別從門限方案的正確性和安全性證明本文的方案是一個完備的秘密共享方案:

(1)正確性:任意大于等于tj個參與者可以正確恢復(fù)出秘密Sj;

(2)安全性:任意少于tj個參與者無法得到關(guān)于秘密S j的任何信息.

方案正確性:在進行秘密重構(gòu)時,任意至少tj個參與者參與,根據(jù)公開值PS j與子秘密分別進行計算fj(xj,i)≡PS j(modmj,i),i=1,2,···,tj,再計算偽子秘密S Hj,i≡gfj(xj,i)(modp)發(fā)送給恢復(fù)者.恢復(fù)者根據(jù)參與者發(fā)送的信息計算:

再根據(jù)公開信息中S j對應(yīng)的轉(zhuǎn)換值Vj,恢復(fù)者可進行比特的異或運算Sj=Vj⊕gaj從 而恢復(fù)秘密Sj.

方案安全性:對于不同的秘密Su,Sv(u≠v),分別對應(yīng)不同的公開轉(zhuǎn)換值Vu=Su⊕gau,Vv=Sv⊕gav,這里au,av均為分發(fā)者構(gòu)造多項式選取的隨機值.因此,不同的秘密重構(gòu)時是相互獨立的,當(dāng)參與者恢復(fù)秘密Su時,不能得到關(guān)于秘密Sv的任何信息.

假設(shè)P1,P2,···,Ptj-1想重構(gòu)秘密S j,包含秘密S j部分信息的只有參與者提供的偽子秘密gfj(1),gfj(2),···,gfj(t j-1).由于fj(x)為tj-1次 多項式,故只有tj-1個參與者時,只能構(gòu)造tj-1個 方程,無法計算多項式fj(x),從而不能計算得到gaj.又因為Sj=Vj⊕gaj,所以任意tj-1 個 參與者不能得到秘密Sj的任何信息.

設(shè)參與者Pi1的子秘密為mi1,參與者Pi2的子秘密為mi2,根據(jù)中國剩余定理的性質(zhì),由于參與者Pi1無法得到參與者Pi2的子秘密mi2,因此不能由秘密S j的公開值PS j得到fj(xi2),即不能得到對應(yīng)的偽子秘密S Hji2.從而只有當(dāng)參與者個數(shù)達到門限值tj才 能得到至少tj個偽子秘密進行秘密重構(gòu),從而恢復(fù)秘密Sj.

定理2.2.本文構(gòu)造的方案中,參與者的子秘密具有安全性;在秘密重構(gòu)階段不會泄露參與者保存的子秘密信息,子秘密具有重復(fù)使用性.

證明:在重構(gòu)秘密S j時,參與者Pi根據(jù)公開值計算fj(xi)≡PS j(modmi),若攻擊者能夠得到參與者Pi的多個信息fj1(xi),···,fjl(xi),即有同余方程組:

可以得到關(guān)于參與者Pi的子秘密mi的部分信息,甚至得到子秘密mi.但本方案中參與者發(fā)送給秘密恢復(fù)者的偽子秘密為S Hj,i≡gfj(xi)(modp),由于求解有限域上離散對數(shù)問題是困難問題,根據(jù)偽子秘密S Hj,i無法求解fj(xi),因此攻擊者無法得到與參與者Pi在秘密重構(gòu)階段產(chǎn)生的fj(xi)任何信息,進而無法獲取上述同余方程組,保證了參與者的子秘密mi在秘密重構(gòu)階段的私密性.因此參與者的子秘密具有可重復(fù)使用性,若再次執(zhí)行秘密共享方案,可不改變參與者的子秘密,仍能進行安全的多秘密共享.從而減少子秘密分發(fā)時產(chǎn)生的通信量,并且參與者無需增加信息的存儲量.

3 方案比較

本文構(gòu)造的方案中應(yīng)用中國剩余定理作為聚合生成公開值的工具,將根據(jù)Shamir(t,n)-門限方案生成的n個偽子秘密進行聚合產(chǎn)生一個公開值.因此k個秘密對應(yīng)產(chǎn)生k個聚合的公開值以及k個轉(zhuǎn)換值,只需要2k個公開值即可共享多個秘密,在分發(fā)多秘密時,每個參與者只需存儲一個子秘密即可,并且參與者所存儲的子秘密可多次使用.同時每個秘密可對應(yīng)不同的存取結(jié)構(gòu),實現(xiàn)了多存取結(jié)構(gòu)的秘密共享.在秘密恢復(fù)階段,本文的方案不需要按照固定順序進行秘密重構(gòu),在需要恢復(fù)哪個秘密時,根據(jù)對應(yīng)的公開值進行重構(gòu)即可.因此可以減少一次性重構(gòu)全部秘密和固定順序重構(gòu)秘密帶來的安全隱患.

表1中對比的3 個方案均為子秘密可多使用的多秘密共享方案.其中Geng 等的方案[8]應(yīng)用單向函數(shù)以及離散對數(shù)問題,保護子秘密的安全性,但所產(chǎn)生的公開值個數(shù)為n2,同時該方案中的秘密值是根據(jù)構(gòu)造的多項式常數(shù)項求模指數(shù)運算得到的,不具有一般性.Wang 等的方案[10]利用RAS 算法實現(xiàn),參與者參與重構(gòu)秘密時,根據(jù)子秘密計算一個偽子秘密發(fā)送給重構(gòu)者,通過偽子秘密無法計算子秘密信息,實現(xiàn)了子秘密的保護,但在秘密重構(gòu)階段該方案一次恢復(fù)全部秘密.Mashhadi 方案[16]在秘密恢復(fù)時限制了秘密的重構(gòu)順序,恢復(fù)某個秘密必須先恢復(fù)前面所有的秘密.本方案共享的秘密可以為任意信息,每個秘密可選擇不同的存取結(jié)構(gòu)進行共享,可靈活地根據(jù)需要在秘密分發(fā)階段選擇合適的門限存取結(jié)構(gòu).在共享秘密時,根據(jù)不同的門限值構(gòu)造隨機多項式生成秘密的掩蓋值,對秘密進行隱藏生成的公開值個數(shù)為2k,遠(yuǎn)小于其他幾個方案產(chǎn)生的公開值個數(shù),并且不同秘密在共享時為相互獨立的,因此在秘密重構(gòu)時可根據(jù)需要恢復(fù)對應(yīng)的秘密值.

表1 子秘密可多使用秘密共享方案對比

Shao的方案[9]構(gòu)造兩個不同的多項式,產(chǎn)生的公開值為2 (k-t)個,但Shao的方案子秘密不具有多使用性,并且所有秘密為一次性全部恢復(fù)的;Chen 等的方案[15]雖然在秘密恢復(fù)時可以按任意順序恢復(fù),但其公開值個數(shù)為大于本方案的2k;Zarepour-Ahmadabadi 等的方案[17]公開值個數(shù)為k個,但需要可信第三方參加秘密重構(gòu),并且參與者的子秘密不具有多使用性.表2中通過3 個方案的比較,說明了本方案與其他幾種公開值個數(shù)較少的多秘密共享方案在秘密恢復(fù)、存取結(jié)構(gòu)、參與者保存的子秘密個數(shù)以及子秘密的安全性等方面進行對比具有更好的性質(zhì).

表2 多秘密共享方案性能對比

4 結(jié)論

本文基于Shamir (t,n)-門限秘密共享方案,應(yīng)用中國剩余定理作為聚合的工具生成公開值,提出了一個子秘密可多次使用的多秘密共享方案.該方案一次分發(fā)多個秘密,每個秘密可以對應(yīng)不同的門限結(jié)構(gòu),同時參與者只存儲一個子秘密.在秘密重構(gòu)階段可根據(jù)需要恢復(fù)對應(yīng)的秘密,參與者根據(jù)不同秘密的公開值信息進行計算,生成偽子秘密參與秘密重構(gòu),最后根據(jù)對應(yīng)的轉(zhuǎn)換值計算得到秘密.同時參與者可以根據(jù)公開的Hash 函數(shù)對恢復(fù)的秘密進行計算,通過與分發(fā)者的公開承諾值進行比較對所恢復(fù)的秘密進行驗證.分析表明,與現(xiàn)有的部分多秘密共享方案相比,本文的方案在公開值個數(shù)以及子秘密的多使用性等方面有更好的性能.