一種安全的多使用門限多秘密共享方案①

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

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

2(福建師范大學 福建省網絡安全與密碼技術重點實驗室,福州 350007)

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

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

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

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

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

(3)不同的秘密對應不同的存取結構;

(4)秘密重構時可按任意順序進行恢復;

(5)實現多秘密的公開值個數少.

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

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

1 預備知識

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

1.1 存取結構

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

存取結構Γ 具有單調性,即:

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

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

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

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

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

1.2 中國剩余定理

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

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

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

1.3 離散對數問題

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

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

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

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

秘密分發階段:

(1)分發者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)的子秘密,并通過安全信道分別發送給對應的參與者.

秘密重構階段:

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

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

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

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

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

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

2 方案構造與分析

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

2.1 具體構造

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

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

(1)秘密分發階段

分發者進行如下操作:

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

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

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

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

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

(2)秘密重構階段

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

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

② 恢復者:根據參與者發送的偽子秘密,恢復者計算:

(3)秘密驗證階段

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

2.2 方案分析

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

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

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

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

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

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

再根據公開信息中S j對應的轉換值Vj,恢復者可進行比特的異或運算Sj=Vj⊕gaj從 而恢復秘密Sj.

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

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

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

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

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

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

3 方案比較

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

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

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

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

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

4 結論

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