李 濱

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

李 濱

(成都師范學院數學系 四川 成都 611130)

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

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

0 引 言

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

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

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

1 方案設計

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

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

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

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

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

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

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

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

設g是模p的一個原根，定義一個雙變元函數。

F(γ,v)=gγ+vmodp

和Zp上的一個坐標函數：

1.2 秘密分發(fā)階段

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

(1)

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

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

利用坐標函數計算出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根據參與者Pi(1≤i≤m1)的子密鑰ki和數值γ1作如下計算：

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

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

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

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

1.3 秘密重構階段

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

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

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

(2)

由式(2)計算出待定系數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。

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

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

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

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

2 分析與討論

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

2.1 正確性分析

在保證莊家D可信的前提下，本方案的子密鑰分發(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)導出的點中任意n個不同的點連同公開的U0點確定唯一的超平面π。

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

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

由于：

ξ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個成員在一起合作能夠恢復出主密鑰組。關于驗證算法的正確性，給出以下結論：

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

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

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

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

2.2 安全性分析

方案的安全性基于Zp上離散對數問題的難解性和超平面的確定性條件，在秘密的分發(fā)和重構過程中能夠實現參與者對莊家以及參與者之間的驗證。

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

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

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

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

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

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

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

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

3 結 語

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

[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] 李濱.基于特殊訪問權限的差分秘密共享方案[J].四川大學學報:自然科學版,2006,43(1):78-83.

[18] 李濱.基于非循環(huán)多項式數列的秘密共享方案[J].四川大學學報:自然科學版,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)。李濱，副教授，主研領域：密碼學及計算機安全技術。

TP309

A

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