一种安全的多使用门限多秘密共享方案①

张 剑,林昌露,丁 健,林修慧,李朝珍

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 函数对恢复的秘密进行计算,通过与分发者的公开承诺值进行比较对所恢复的秘密进行验证.分析表明,与现有的部分多秘密共享方案相比,本文的方案在公开值个数以及子秘密的多使用性等方面有更好的性能.