李 滨

双群体门限秘密共享方案的一种几何设计

李 滨

(成都师范学院数学系 四川 成都 611130)

针对目前已公开的门限秘密共享方案大多是单群体门限方案的问题，引入双群体秘密共享的概念，结合多维空间解析几何和密码学理论，提出一个双群体门限秘密共享方案。其方法是引入双变量函数和坐标函数计算子密钥的导出点，并通过两个不平行的超平面的法线交点来重构主密钥。结果表明，该门限方案是理想的，既能实现参与者的动态加入与退出以及门限值的改变，又能实现多个秘密共享，还能灵活地更新主密钥。其中每个参与者始终只需掌握一个不变的子密钥即可，管理和使用都比较方便。方案能有效地检测和识别庄家D对参与者以及参与者之间的欺骗行为，以确保重构的主密钥是安全和可靠的。

门限秘密共享 双群体 多维超平面 离散对数 参数曲面

0 引 言

秘密共享技术是保密通信中密钥管理的重要手段。其思想方法是将主密钥(即共享的秘密)分成n个子密钥秘密地分发给n个参与者，使得任何参与者的授权子集中的所有参与者合作能够恢复主密钥，而参与者的非授权子集中的参与者合作却不能得到主密钥的任何信息。最早的秘密共享方案是由Shamir[1]和Blakley[2]在1979年分别独立地提出的(t,n)门限秘密共享方案，随后秘密共享成为密码学的一个非常重要的内容，并得到广泛地研究和应用。

但早期的秘密共享方案存在三大问题：1) 在秘密共享过程中方案不能防止庄家(即秘密分发者)和参与者的欺骗行为，也就是在分发阶段参与者不能验证其得到的子密钥的真实性和在重构阶段参与者之间不能相互验证各自提供的子密钥的真实性；2) 在秘密共享过程中参与者所得到的子密钥只能使用一次，如果要共享多个主密钥那就需要庄家多次重新分发子密钥；3) 当秘密共享的参与者集合中成员的增加或减少时，现有的共享出现不安全状态，庄家需要重新分发子密钥来更新老成员的子密钥。这三个问题影响了方案的安全性和实用性，甚至造成重构秘密的成功率和系统效率的低下。针对第一个问题，Chor等人[3]首先提出了可验证秘密共享的概念，只需在通常的秘密共享方案的基础上附加一个验证算法就构成了一个可验证秘密共享方案，如文献[4-7]参与者可以通过验证算法检验所收到的子密钥的正确性。为了解决第二个问题，He等人[8]把Shamir秘密共享思想与公开移动技术相结合，首次提出了多秘密共享方案。使得在秘密共享过程中，每个参与者只需持有一个子密钥就可以共享多个主密钥，后来许多学者在这方面做了大量的研究[9-12]。对于问题三的解决办法，Lain等人[13]提出了动态秘密共享方案，支持参与者动态地加入或者离开而不用改变其它参与者的子密钥。为了做到这一点，方案中往往采用在线秘密共享机制[14-16]，灵活地引入电子公告牌发布一些辅助消息。

以上提到的方案都只是基于具有同等的访问权限的参与者组成的一个群体的秘密共享方案。但在现实的应用中，为了降低风险，对重要资源的管理往往需要管理层和职员层两个群体的加入，如银行金库的开启需要一定数量的主管人员和一定数量的出纳共同完成等。文献[17,18]分别提出了(t+1,u+v)双群体门限秘密共享方案的概念，即在有u个参与者的群体中至少t个成员和另一个有v个参与者的群体中至少一个成员合作在一起方可恢复共享的主密钥。文献[17]的方案通过齐次常系数线性差分方程的解结构来构建，文献[18]的方案采用非循环多项式数列来设计。本文提出了更为一般的双群体秘密共享的概念，利用两个多维空间超平面法线相交的几何方法设计出一个动态的且能预防欺骗的门限多秘密共享方案。

1 方案设计

首先给出双群体秘密共享方案的概念：

从这个定义不难看出，能够恢复出主密钥S的参与者子集集合Γ是Γ={E⊕F⊂P⊕Q| |P|≥n1,|Q|≥n2}在Γ中的任何集合都是P⊕Q上的授权集。

在本方案中，设P={P1，P2，…，Pm1}，Q={Q1，Q2，…，Qm2}，D为庄家，NB为电子公告牌，NB的作用是公布一些辅助信息，只有庄家可以提供、修改和更新NB上的内容，其他参与者只能阅读或下载。方案包括系统初始化阶段、秘密分发阶段以及秘密重构阶段三个部分。

1.1 系统初始化阶段

在这个阶段主要由庄家D完成系统参数的选定。

设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 秘密分发阶段

设需要共享的主密钥组为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上公布。

为了方案能预防欺骗行为的发生，庄家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)都可以对庄家分发给自己的子密钥进行验证，只需在NB上下载αj(1≤j≤n) 和βi，验证以下等式是否成立:

如果等式成立，那么庄家D发送了有效的子密钥，如果等式不成立，则说明庄家D发送的子密钥无效，要求其重发。

在对超平面π的恢复过程中，每位成员提供的不是自己的子密钥，而是根据子密钥ki(0≤i≤n)和NB上的公开信息导出的影子信息ξij(0≤i, j≤n)，秘密重构者可以计算下式来分别验证n个参与成员是否有欺骗行为：

如果等式都成立，表示收集到的子密钥都是有效的，则可按照以上重构法恢复出正确的超平面π。

2 分析与讨论

本方案能够实现多重秘密共享，通过多维空间参数曲面灵活地更换主密钥组，动态地增减参与者人数，在方案的实现过程中能有效地验证子密钥的真实性，提高重构主密钥的成功率。方案的安全性基于多维超平面的确定性条件和离散对数问题的难解性。由于参与者集合P和Q，超平面π和π′情况类似，因此下面我们主要针对P和π进行分析讨论。

2.1 正确性分析

在保证庄家D可信的前提下，本方案的子密钥分发以及主密钥组的恢复是可行的。

定理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发送的子密钥的导出点在超平面π上，验证条件(Ⅱ)保证了参与者提交的子密钥与庄家D发送的子密钥是一致的。

2.2 安全性分析

方案的安全性基于Zp上离散对数问题的难解性和超平面的确定性条件，在秘密的分发和重构过程中能够实现参与者对庄家以及参与者之间的验证。

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 动态性能分析

在很多实际应用中，经常会遇到参与者数目、门限值和共享主密钥组的改变等问题，庄家D往往重新分发参与者的子密钥，这样就增加了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 结 语

本文主要采用多维空间解析几何的方法研究双群体门限秘密共享问题，提出了一个新的可验证的动态多秘密共享的门限方案。方案中参与者需要保存的子密钥仅是有限域Zp上的一个数值而非一个多维空间点，从而子密钥的长度与共享主密钥的长度相同，即信息率为1；方案可以一次性共享多个秘密和多轮次被反复使用，并且在门限要素动态改变的情况下参与者只需掌握同一个子密钥，从而提高了秘密分发率和方便了密钥管理。方案的安全性基于有限域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] 李滨.基于非循环多项式数列的秘密共享方案[J].四川大学学报:自然科学版,2014,51(3):423-427.

[19] 刘木兰,张志芳.密钥共享体制和安全多方计算[M].北京:电子工业出版社,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