雙群體門(mén)限秘密共享方案的一種幾何設(shè)計(jì)

李 濱

雙群體門(mén)限秘密共享方案的一種幾何設(shè)計(jì)

李 濱

(成都師范學(xué)院數(shù)學(xué)系 四川 成都 611130)

針對(duì)目前已公開(kāi)的門(mén)限秘密共享方案大多是單群體門(mén)限方案的問(wèn)題，引入雙群體秘密共享的概念，結(jié)合多維空間解析幾何和密碼學(xué)理論，提出一個(gè)雙群體門(mén)限秘密共享方案。其方法是引入雙變量函數(shù)和坐標(biāo)函數(shù)計(jì)算子密鑰的導(dǎo)出點(diǎn)，并通過(guò)兩個(gè)不平行的超平面的法線交點(diǎn)來(lái)重構(gòu)主密鑰。結(jié)果表明，該門(mén)限方案是理想的，既能實(shí)現(xiàn)參與者的動(dòng)態(tài)加入與退出以及門(mén)限值的改變，又能實(shí)現(xiàn)多個(gè)秘密共享，還能靈活地更新主密鑰。其中每個(gè)參與者始終只需掌握一個(gè)不變的子密鑰即可，管理和使用都比較方便。方案能有效地檢測(cè)和識(shí)別莊家D對(duì)參與者以及參與者之間的欺騙行為，以確保重構(gòu)的主密鑰是安全和可靠的。

門(mén)限秘密共享 雙群體 多維超平面 離散對(duì)數(shù) 參數(shù)曲面

0 引 言

秘密共享技術(shù)是保密通信中密鑰管理的重要手段。其思想方法是將主密鑰(即共享的秘密)分成n個(gè)子密鑰秘密地分發(fā)給n個(gè)參與者，使得任何參與者的授權(quán)子集中的所有參與者合作能夠恢復(fù)主密鑰，而參與者的非授權(quán)子集中的參與者合作卻不能得到主密鑰的任何信息。最早的秘密共享方案是由Shamir[1]和Blakley[2]在1979年分別獨(dú)立地提出的(t,n)門(mén)限秘密共享方案，隨后秘密共享成為密碼學(xué)的一個(gè)非常重要的內(nèi)容，并得到廣泛地研究和應(yīng)用。

但早期的秘密共享方案存在三大問(wèn)題：1) 在秘密共享過(guò)程中方案不能防止莊家(即秘密分發(fā)者)和參與者的欺騙行為，也就是在分發(fā)階段參與者不能驗(yàn)證其得到的子密鑰的真實(shí)性和在重構(gòu)階段參與者之間不能相互驗(yàn)證各自提供的子密鑰的真實(shí)性；2) 在秘密共享過(guò)程中參與者所得到的子密鑰只能使用一次，如果要共享多個(gè)主密鑰那就需要莊家多次重新分發(fā)子密鑰；3) 當(dāng)秘密共享的參與者集合中成員的增加或減少時(shí)，現(xiàn)有的共享出現(xiàn)不安全狀態(tài)，莊家需要重新分發(fā)子密鑰來(lái)更新老成員的子密鑰。這三個(gè)問(wèn)題影響了方案的安全性和實(shí)用性，甚至造成重構(gòu)秘密的成功率和系統(tǒng)效率的低下。針對(duì)第一個(gè)問(wèn)題，Chor等人[3]首先提出了可驗(yàn)證秘密共享的概念，只需在通常的秘密共享方案的基礎(chǔ)上附加一個(gè)驗(yàn)證算法就構(gòu)成了一個(gè)可驗(yàn)證秘密共享方案，如文獻(xiàn)[4-7]參與者可以通過(guò)驗(yàn)證算法檢驗(yàn)所收到的子密鑰的正確性。為了解決第二個(gè)問(wèn)題，He等人[8]把Shamir秘密共享思想與公開(kāi)移動(dòng)技術(shù)相結(jié)合，首次提出了多秘密共享方案。使得在秘密共享過(guò)程中，每個(gè)參與者只需持有一個(gè)子密鑰就可以共享多個(gè)主密鑰，后來(lái)許多學(xué)者在這方面做了大量的研究[9-12]。對(duì)于問(wèn)題三的解決辦法，Lain等人[13]提出了動(dòng)態(tài)秘密共享方案，支持參與者動(dòng)態(tài)地加入或者離開(kāi)而不用改變其它參與者的子密鑰。為了做到這一點(diǎn)，方案中往往采用在線秘密共享機(jī)制[14-16]，靈活地引入電子公告牌發(fā)布一些輔助消息。

以上提到的方案都只是基于具有同等的訪問(wèn)權(quán)限的參與者組成的一個(gè)群體的秘密共享方案。但在現(xiàn)實(shí)的應(yīng)用中，為了降低風(fēng)險(xiǎn)，對(duì)重要資源的管理往往需要管理層和職員層兩個(gè)群體的加入，如銀行金庫(kù)的開(kāi)啟需要一定數(shù)量的主管人員和一定數(shù)量的出納共同完成等。文獻(xiàn)[17,18]分別提出了(t+1,u+v)雙群體門(mén)限秘密共享方案的概念，即在有u個(gè)參與者的群體中至少t個(gè)成員和另一個(gè)有v個(gè)參與者的群體中至少一個(gè)成員合作在一起方可恢復(fù)共享的主密鑰。文獻(xiàn)[17]的方案通過(guò)齊次常系數(shù)線性差分方程的解結(jié)構(gòu)來(lái)構(gòu)建，文獻(xiàn)[18]的方案采用非循環(huán)多項(xiàng)式數(shù)列來(lái)設(shè)計(jì)。本文提出了更為一般的雙群體秘密共享的概念，利用兩個(gè)多維空間超平面法線相交的幾何方法設(shè)計(jì)出一個(gè)動(dòng)態(tài)的且能預(yù)防欺騙的門(mén)限多秘密共享方案。

1 方案設(shè)計(jì)

首先給出雙群體秘密共享方案的概念：

從這個(gè)定義不難看出，能夠恢復(fù)出主密鑰S的參與者子集集合Γ是Γ={E⊕F?P⊕Q| |P|≥n1,|Q|≥n2}在Γ中的任何集合都是P⊕Q上的授權(quán)集。

在本方案中，設(shè)P={P1，P2，…，Pm1}，Q={Q1，Q2，…，Qm2}，D為莊家，NB為電子公告牌，NB的作用是公布一些輔助信息，只有莊家可以提供、修改和更新NB上的內(nèi)容，其他參與者只能閱讀或下載。方案包括系統(tǒng)初始化階段、秘密分發(fā)階段以及秘密重構(gòu)階段三個(gè)部分。

1.1 系統(tǒng)初始化階段

在這個(gè)階段主要由莊家D完成系統(tǒng)參數(shù)的選定。

設(shè)n=max{ n1，n2}，在n+1維實(shí)歐氏空間Rn+1中引入一個(gè)易反解的t(1≤t≤n)元參數(shù)曲面σ：

其中(u1,u2,…,ut)∈Rt，σ實(shí)質(zhì)上是Rt到Rn+1的一個(gè)映射。

σ： (u1,u2,…,ut)→(x1,x2,…,xn+1)

設(shè)g是模p的一個(gè)原根，定義一個(gè)雙變?cè)瘮?shù)。

F(γ,v)=gγ+vmodp

和Zp上的一個(gè)坐標(biāo)函數(shù)：

1.2 秘密分發(fā)階段

設(shè)需要共享的主密鑰組為S1，S2，…，St，其中1≤t≤n，莊家D取t元參數(shù)值(u1，u2，…，ut)=(S1，S2，…，St)，利用Zp上t元參數(shù)曲面方程計(jì)算：

(1)

莊家D在雙變?cè)瘮?shù)中取值γ=γ1∈Zp,v=k0∈Zp，且k0≠ki(1≤i≤m1)，計(jì)算：

ξ01=F(γ1,k0)=gγ1+k0modp

利用坐標(biāo)函數(shù)計(jì)算出Rn+1中的另一點(diǎn)U0(ξ01,ξ02,…,ξ0,n+1)。

否則，重新選取γ和γ′的值直至上面不等式成立。

令:

u=(u1,u2,…,un+1)=(a1-ξ01,a2-ξ02,…,an+1-ξ0,n+1)

莊家D分別以u(píng)、u′為法向量過(guò)U0、V0點(diǎn)在Zp上作Rn+1中的超平面π和π′。

莊家D根據(jù)參與者Pi(1≤i≤m1)的子密鑰ki和數(shù)值γ1作如下計(jì)算：

ξi1=F(γ1,ki)=gγ1+kimodp 1≤i≤m1

對(duì)于門(mén)限值n1和n2，不妨設(shè)n1≥n2，此時(shí)n=n1，莊家需要將超平面π′上的n-n2個(gè)點(diǎn)的坐標(biāo)在NB上公布。

為了方案能預(yù)防欺騙行為的發(fā)生，莊家D需要作如下計(jì)算：

δ=2[n(n-1)]-1modq

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

當(dāng)P中的任意n(n=n1)個(gè)成員和Q中的任意n2個(gè)成員合作在一起時(shí)，他們可以通過(guò)自己手中的子密鑰恢復(fù)出超平面π和π′。

對(duì)于P中的任意n1個(gè)成員，不失一般性，不妨設(shè)為P1，P2，…，Pn。他們?cè)贜B上下載相關(guān)的公開(kāi)信息，各自利用自己擁有的子密鑰ki計(jì)算：

ξi1=F(γ1,ki)=gγ1+kimodp 1≤i≤n

(2)

由式(2)計(jì)算出待定系數(shù)u1, u2, …, un和N。再通過(guò)下式計(jì)算出un+1:

從而得到超平面π的方程:

其中u=(u1,u2,…,un, un+1)為π的法向量，(ξ1,ξ2,…,ξn+1)為π上動(dòng)點(diǎn)坐標(biāo)。

由U0點(diǎn)和法向量u得到π上過(guò)U0點(diǎn)的法線L的方程：

(3)

其中(η1,η2,…,ηn+1)為L(zhǎng)上動(dòng)點(diǎn)坐標(biāo)。

(4)

其中(η1,η2,…,ηn+1)為L(zhǎng)′上動(dòng)點(diǎn)坐標(biāo)。

然后由式(3)和式(4)求出L與L′的交點(diǎn)A(a1,a2,…,an+1)，再通過(guò)式(1)計(jì)算出主密鑰組S1，S2，…，St。

在這個(gè)秘密的重構(gòu)過(guò)程中，P中的每位參與者Pi(1≤i≤m1)都可以對(duì)莊家分發(fā)給自己的子密鑰進(jìn)行驗(yàn)證，只需在NB上下載αj(1≤j≤n) 和βi，驗(yàn)證以下等式是否成立:

如果等式成立，那么莊家D發(fā)送了有效的子密鑰，如果等式不成立，則說(shuō)明莊家D發(fā)送的子密鑰無(wú)效，要求其重發(fā)。

在對(duì)超平面π的恢復(fù)過(guò)程中，每位成員提供的不是自己的子密鑰，而是根據(jù)子密鑰ki(0≤i≤n)和NB上的公開(kāi)信息導(dǎo)出的影子信息ξij(0≤i, j≤n)，秘密重構(gòu)者可以計(jì)算下式來(lái)分別驗(yàn)證n個(gè)參與成員是否有欺騙行為：

如果等式都成立，表示收集到的子密鑰都是有效的，則可按照以上重構(gòu)法恢復(fù)出正確的超平面π。

2 分析與討論

本方案能夠?qū)崿F(xiàn)多重秘密共享，通過(guò)多維空間參數(shù)曲面靈活地更換主密鑰組，動(dòng)態(tài)地增減參與者人數(shù)，在方案的實(shí)現(xiàn)過(guò)程中能有效地驗(yàn)證子密鑰的真實(shí)性，提高重構(gòu)主密鑰的成功率。方案的安全性基于多維超平面的確定性條件和離散對(duì)數(shù)問(wèn)題的難解性。由于參與者集合P和Q，超平面π和π′情況類似，因此下面我們主要針對(duì)P和π進(jìn)行分析討論。

2.1 正確性分析

在保證莊家D可信的前提下，本方案的子密鑰分發(fā)以及主密鑰組的恢復(fù)是可行的。

定理1 方案中兩法線L和 L′有唯一交點(diǎn)A(a1,a2,…,an+1)。

證明 由于在Zp上L1與L2的方向向量分別為：

u=(a1-ξ01,a2-ξ02,…,an+1-ξ0,n+1)

因此A(a1,a2,…,an+1)顯然在L1與L2上。

由于:

所以不存在任何h∈Zp，使得u = hu′，即交于同一點(diǎn)A的L與L′不會(huì)重合。故L與L′有唯一交點(diǎn)A。證畢。

定理2 由子密鑰ki(1≤i≤m1)導(dǎo)出的點(diǎn)中任意n個(gè)不同的點(diǎn)連同公開(kāi)的U0點(diǎn)確定唯一的超平面π。

證明 n個(gè)不同點(diǎn)和U0點(diǎn)決定的式(2)可變形為下面方程組：

以N，u1, u2, …, un為未知數(shù)的這個(gè)方程組的系數(shù)行列式：

由于：

ξi1=F(γ1+ki)=gγ1+kimodp

ξj1=F(γ1+kj)=gγ1+kjmodp

且g是模p的原根,所以在Zp上當(dāng)ki≠kj時(shí)ξi1≠ξj1,故D≠0。

由Gramer法則可知式(2)有唯一解N，u1,u2,…,un。因而確定出唯一的超平面：

其中(ξ1,ξ2,…,ξn+1)為π上動(dòng)點(diǎn)坐標(biāo)。證畢。

從定理1和定理2可知方案中參與者集合P中至少n1個(gè)成員和參與者集合Q中至少n2個(gè)成員在一起合作能夠恢復(fù)出主密鑰組。關(guān)于驗(yàn)證算法的正確性，給出以下結(jié)論：

定理3 子密鑰ki(1≤i≤m1)是真實(shí)有效的當(dāng)且僅當(dāng)：

證明 點(diǎn)Ui(ξi1,ξi2,…,ξin,ξi,n+1)在超平面π上：

gγ1zimodp=gγ1·gkimodp=gγ1+kimodp

驗(yàn)證條件(Ⅰ)保證了莊家D發(fā)送的子密鑰的導(dǎo)出點(diǎn)在超平面π上，驗(yàn)證條件(Ⅱ)保證了參與者提交的子密鑰與莊家D發(fā)送的子密鑰是一致的。

2.2 安全性分析

方案的安全性基于Zp上離散對(duì)數(shù)問(wèn)題的難解性和超平面的確定性條件，在秘密的分發(fā)和重構(gòu)過(guò)程中能夠?qū)崿F(xiàn)參與者對(duì)莊家以及參與者之間的驗(yàn)證。

1) 參與者集合P中不足n1個(gè)成員或者參與者集合Q中不足n2個(gè)成員合作不能恢復(fù)主密鑰組Si(1≤i≤t)，這是因?yàn)镻中少于n1個(gè)成員提交的子密鑰最多能產(chǎn)生包括公開(kāi)的U0點(diǎn)在內(nèi)的n1個(gè)點(diǎn)，這n1個(gè)點(diǎn)不能夠唯一確定超平面π的。這是因?yàn)椋偃暨@n1個(gè)點(diǎn)(不妨設(shè)為U0，U1，…，Un1-1)能夠確定唯一的超平面為π1，在多維空間中選取不在π1上的一個(gè)點(diǎn)W，使得U0，U1，…，Un1-1，W的坐標(biāo)向量線性無(wú)關(guān)(即生成的行列式不為0)。由定理2可知，U0，U1，…，Un1-1，W能唯一確定一個(gè)超平面π2，由于W不在π1上，所以π1≠π2，但U0，U1，…，Un1-1既在π1上又在π2上，這與U0，U1，…，Un1-1唯一確定一個(gè)超平面的假設(shè)矛盾。因此p中少于n1個(gè)成員合作不能唯一確定超平面π。同理Q中少于n2個(gè)成員合作也不能唯一確定超平面π′，從而得不到相應(yīng)的法線L和L′及其交點(diǎn)A，故無(wú)法恢復(fù)出主密鑰。

2.3 動(dòng)態(tài)性能分析

在很多實(shí)際應(yīng)用中，經(jīng)常會(huì)遇到參與者數(shù)目、門(mén)限值和共享主密鑰組的改變等問(wèn)題，莊家D往往重新分發(fā)參與者的子密鑰，這樣就增加了D的計(jì)算和通信負(fù)擔(dān)。為了解決以上問(wèn)題，本方案中的每一位參與者只需始終維護(hù)一個(gè)子密鑰，該子密鑰可以在多次秘密共享過(guò)程中重復(fù)使用，從而提高了方案的靈活性和效率。

1) 從參數(shù)曲面的方程可以看出，本方案可一次性共享從1個(gè)到n個(gè)主密鑰，即對(duì)于共享的主密鑰Si(1≤i≤t，1≤t≤n)取參數(shù)值ui=Si即可。

2) 當(dāng)共享的主密鑰組需要改變時(shí)，各參與者的子密鑰不需要改變，莊家只需改變雙變?cè)瘮?shù)中γ和γ′的值，更新電子公告牌NB上相應(yīng)的公開(kāi)信息即可。

6) 該方案是一個(gè)理想的秘密共享方案。一個(gè)秘密共享方案的信息率與其數(shù)據(jù)擴(kuò)散程度成反比[19]，定義為：

ρ=min{ρi|ρi=lg|S|/lg|Ki|,1≤i≤n}

式中S是主密鑰空間，Ki是ρi的子密鑰空間，由于在本方案中，每一位參與者只需保存一個(gè)屬于Zp的子密鑰，因此S = Ki= Zp,故ρ=1。

3 結(jié) 語(yǔ)

本文主要采用多維空間解析幾何的方法研究雙群體門(mén)限秘密共享問(wèn)題，提出了一個(gè)新的可驗(yàn)證的動(dòng)態(tài)多秘密共享的門(mén)限方案。方案中參與者需要保存的子密鑰僅是有限域Zp上的一個(gè)數(shù)值而非一個(gè)多維空間點(diǎn)，從而子密鑰的長(zhǎng)度與共享主密鑰的長(zhǎng)度相同，即信息率為1；方案可以一次性共享多個(gè)秘密和多輪次被反復(fù)使用，并且在門(mén)限要素動(dòng)態(tài)改變的情況下參與者只需掌握同一個(gè)子密鑰，從而提高了秘密分發(fā)率和方便了密鑰管理。方案的安全性基于有限域Zp上求解離散對(duì)數(shù)的困難性和多維超平面的確定性條件，參與者重構(gòu)一個(gè)超平面并不影響另一個(gè)超平面的安全性；方案能有效地檢測(cè)和阻止莊家D對(duì)參與者以及參與者之間的欺騙，欺騙者只能通過(guò)猜測(cè)的手段來(lái)進(jìn)行欺詐且成功的概率僅為1/pt，從而提高了秘密重構(gòu)的成功率和方案的效率。

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

[2] Blakley G R.Safeguarding cryptographic keys[C]//Proceeding of National Computer Conference.Montvale,NJ:AFIPS Press,1979,48:313-317.

[3] Chor B,Goldwasser S,Micali S,et al.Verifiable secret sharing and achieving simultaneity in the presence of faults[C]//Proceeding of the 26thIEEE Symposium on Foundations of Computer Science.Washington D C:IEEE Computer Society,1985:383-395.

[4] Gan Yuanju,Wang Lihua,Wang Licheng,et al.Publicly verifiable secret sharing scheme with provable security against chosen secret attacks[J/OL].International Journal of Distributed Sensor Networks,2013,Article ID 902462[2013-07-08].http://dx.doi.org/10.1155/2013/902462.

[5] Zhao Dawei,Peng Haipeng,Wang Cong,et al.A secret sharing scheme with a short share realizing the (t,n) threshold and the adversary structure[J].Computers and Mathematics with Applications,2012,64(11):611-615.

[6] Shao Jun.Efficient verifiable multi-secret sharing scheme based on hash function[J].Information Sciences,2014,288(2):104-109.

[7] Tang Chunming,Gao Shuhong.Leakproof secret sharing protocols with applications to group identification scheme[J].Science CHINA:Information Sciences,2012,55(5):1172-1185.

[8] He J,Dawson E.Multi-stage secret sharing scheme based on one-way function[J].Electronic Letters,1994,30(19):1591-1594.

[9] He Chunqiang,Liao Xiaofeng,Cheng Xiuzhen.Verifiable multi-secret sharing based on LFSR sequences[J].Theoretical Computer Science,2012,445(1):52-62.

[10] Lin Kaisiang,Lin Chihhung,Chen Tzungher.Distortionless visual multi-secret sharing based on random grid[J].Information Sciences,2014,288(6):330-346.

[11] Dehkordi M H,Mashhadi S.New efficient and practical verifiable multi-secret sharing schemes[J].Information Sciences,2008,178(9):2262-2274.

[12] Eslami Z,Zarepour A J.A verifiable multi-secret sharing scheme based on cellular automata[J].Information Science,2010,180(15):2889-2894.

[13] Lain C,Harn L,Lee J,et al.Dynamic threshold scheme based on the definition of cross-product on N-dimensional linear space[C]//Proceeding of Advances in Cryptology.Berlin:Springer-Verlag,1989:20-24.

[14] Sasouli A,Shamsi M.Online secret sharing using infinite convergent sequences[C]//Proceeding of International Conference on Computer and Software Modeling.Singapore:IACSIT Press,2011:128-133.

[15] Boloorchi A T,Samadzadeh M H,Chen T.Symmetric Threshold Multipath (STM):An online symmetric key management scheme[J].Information Sciences,2014,288(8):489-504.

[16] Nojoumian M,Stinson D R.On dealer-free dynamic threshold schemes[J].Advances in Mathematics of Communications,2013,7(1):39-56.

[17] 李濱.基于特殊訪問(wèn)權(quán)限的差分秘密共享方案[J].四川大學(xué)學(xué)報(bào):自然科學(xué)版,2006,43(1):78-83.

[18] 李濱.基于非循環(huán)多項(xiàng)式數(shù)列的秘密共享方案[J].四川大學(xué)學(xué)報(bào):自然科學(xué)版,2014,51(3):423-427.

[19] 劉木蘭,張志芳.密鑰共享體制和安全多方計(jì)算[M].北京:電子工業(yè)出版社,2008:18-21.

A GEOMETRIC DESIGN OF THRESHOLD SECRET SHARING SCHEME ON DUAL COLONIES

Li Bin

(DepartmentofMathematics,ChengduNormalUniversity,Chengdu611130,Sichuan,China)

Most of current disclosed threshold secret sharing schemes are regarding the single colony. In light of this issue, we introduced the concept of secret sharing for dual colonies. In combination with hyperspace analytic geometry and cryptography, we proposed a threshold secret sharing scheme on dual colonies. The approach is that to introduce the bivariate function and coordinate function to calculate the derived points of sub-key and then to reconstruct the master key through the normal intersection point of two unparallel hyperplanes. Result showed that this threshold scheme is ideal, it can realise not only the dynamic join or exit of the participants and the change of threshold, but also the sharing of multiple secrets, as well as the flexible update of master key. In the scheme, every participant only has the need to hold an unvaried sub-key always, thus it is convenient in management and use. This scheme can effectively detect and identify the frauds the maker D imposed on participants and among the participants so as to guarantee that the reconstructed master key is secure and trustworthy.

Threshold secret sharing Dual colonies Multidimensional hyperplane Discrete logarithm Parameter surface

2014-12-15。四川省科研基金項(xiàng)目(12ZB276)。李濱，副教授，主研領(lǐng)域：密碼學(xué)及計(jì)算機(jī)安全技術(shù)。

TP309

A

10.3969/j.issn.1000-386x.2016.04.073