李 濱

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

李 濱

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

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

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

0 引 言

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

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

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

1 方案設(shè)計

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

從這個定義不難看出，能夠恢復(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)階段三個部分。

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

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

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

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

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

設(shè)g是模p的一個原根，定義一個雙變元函數(shù)。

F(γ,v)=gγ+vmodp

和Zp上的一個坐標函數(shù)：

1.2 秘密分發(fā)階段

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

(1)

莊家D在雙變元函數(shù)中取值γ=γ1∈Zp,v=k0∈Zp，且k0≠ki(1≤i≤m1)，計算：

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

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

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

令:

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

莊家D分別以u、u′為法向量過U0、V0點在Zp上作Rn+1中的超平面π和π′。

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

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

對于門限值n1和n2，不妨設(shè)n1≥n2，此時n=n1，莊家需要將超平面π′上的n-n2個點的坐標在NB上公布。

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

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

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

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

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

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

(2)

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

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

其中u=(u1,u2,…,un, un+1)為π的法向量，(ξ1,ξ2,…,ξn+1)為π上動點坐標。

由U0點和法向量u得到π上過U0點的法線L的方程：

(3)

其中(η1,η2,…,ηn+1)為L上動點坐標。

(4)

其中(η1,η2,…,ηn+1)為L′上動點坐標。

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

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

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

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

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

2 分析與討論

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

2.1 正確性分析

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

定理1 方案中兩法線L和 L′有唯一交點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′，即交于同一點A的L與L′不會重合。故L與L′有唯一交點A。證畢。

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

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

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

由于：

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

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

且g是模p的原根,所以在Zp上當ki≠kj時ξi1≠ξj1,故D≠0。

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

其中(ξ1,ξ2,…,ξn+1)為π上動點坐標。證畢。

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

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

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

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

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

2.2 安全性分析

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

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

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

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

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

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

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

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

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

3 結(jié) 語

本文主要采用多維空間解析幾何的方法研究雙群體門限秘密共享問題，提出了一個新的可驗證的動態(tài)多秘密共享的門限方案。方案中參與者需要保存的子密鑰僅是有限域Zp上的一個數(shù)值而非一個多維空間點，從而子密鑰的長度與共享主密鑰的長度相同，即信息率為1；方案可以一次性共享多個秘密和多輪次被反復(fù)使用，并且在門限要素動態(tài)改變的情況下參與者只需掌握同一個子密鑰，從而提高了秘密分發(fā)率和方便了密鑰管理。方案的安全性基于有限域Zp上求解離散對數(shù)的困難性和多維超平面的確定性條件，參與者重構(gòu)一個超平面并不影響另一個超平面的安全性；方案能有效地檢測和阻止莊家D對參與者以及參與者之間的欺騙，欺騙者只能通過猜測的手段來進行欺詐且成功的概率僅為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] 李濱.基于特殊訪問權(quán)限的差分秘密共享方案[J].四川大學(xué)學(xué)報:自然科學(xué)版,2006,43(1):78-83.

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

[19] 劉木蘭,張志芳.密鑰共享體制和安全多方計算[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。四川省科研基金項目(12ZB276)。李濱，副教授，主研領(lǐng)域：密碼學(xué)及計算機安全技術(shù)。

TP309

A

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