基于多项式插值的门限函数秘密分享方案①

罗景龙,林昌露,李朝珍,张 剑

(福建师范大学 数学与信息学院,福州 350117)

(福建师范大学 福建省网络安全与密码技术重点实验室,福州 350007)

1979年,Shamir[1]和Blakley[2]分别独立提出了秘密分享(Secret Sharing,SS)概念并基于不同数学工具构造了相应方案.秘密分享一般包含一个发送者和多个参与者,在秘密分发阶段发送者将秘密值分成多个子秘密,并将每个子秘密安全地发送给对应的参与者.在重构阶段满足条件的参与者集合中的参与者合作重构出秘密值,不满足条件的参与者集合中的参与者则不能得到关于秘密值的任何信息.作为重要的密码技术,秘密分享自提出以来一直受到研究者的持续关注.

函数秘密分享方案(Function Secret Sharing,FSS)与传统的秘密分享方案[1,2]最主要的不同在于它分享的秘密为函数而不是具体数值.一个n方的FSS 方案可以简单地描述如下,在分发阶段发送者将秘密函数f:Df→Rf,其中Df,Rf分别表示秘密函数的定义域和值域,可加地分为n个 子函数f1,···,fn,并将子函数安全地发送给相应的参与者.其正确性要求秘密函数可以通过计算被正确地重构,安全性要求子函数集合{f1,···,fn}的任何真子集完全掩盖了秘密函数的全部信息.在FSS 方案中,子函数的长度与该FSS 方案的通信复杂度直接相关,FSS 方案的通信复杂度为所有需要传输的子函数的长度之和.FSS 在提高多服务器环境下的私密信息存取的效率,如:私密信息恢复[3],私密信息存储[4]等方面有着重要的应用.

针对于点函数fa,b(x):{0,1}l→{0,1}m,其中{0,1}l,{0,1}m分别表示点函数的定义域和值域,任意的x0∈{0,1}n,若x0=a有fa,b(x0)=b,否则有fa,b(x0)=0.Gilboa等[5]基于伪随机生成器构造了子函数长度为O (λllog32)的两方FSS 方案,其中 λ为伪随机生成器的种子长度,并将构造的两方FSS 方案应用到了提高两服务器的私密信息检索协议的效率中,得到了通信复杂度为O(λllog32)的两方私密信息检索协议.之后Boyle 等[6]利用二叉树技术降低了文献[5]中两方FSS 方案的通信复杂度,构造了子函数长度为 O (λl)的两方FSS 方案.此外Boyle 等[6]构造了通信复杂度为 O(λ2l+n−1/2)的n(n≥3)方的FSS 方案.在此基础上Boyle 等[6]提出了函数秘密分享概念并对其进行了系统的介绍,指出FSS 与密码学中的其他概念,例如:同态秘密分享(Homomorphic Secret Sharing,HSS)[7],完全同态加密(Fully Homomorphic Encryption,FHE)[8]等其他密码学概念之间存在着密切的联系.在文献[9]中Boyle 等使用代数中的张量操作简化了文献[6]中的两方的FSS方案的构造并将其通信复杂度降低了4 倍.

文献[5,6,9]中的FSS 方案在重构阶段要求所有的参与者均参与重构.而在实际生活中往往存在参与者因为自身原因不能参与重构的场景,例如某个参与者在方案运行的过程中掉线,因此导致整个FSS 方案无法正常运行.除此之外他们的FSS 方案都是基于伪随机生成器构造的,因此其安全性基于密码学中单向函数存在性假设[10],这说明了他们的FSS 方案均为计算意义下安全的FSS 方案,即只可以抵抗计算能力有限的敌手.

为了使FSS 方案可以更加灵活地应用于现实场景,以及具有更高级别的安全性,本文采用多项式技术构造了信息论意义下安全的门限函数秘密分享(Threshold Function Secret Sharing,TFSS)方案,在重构过程中可以容忍部分参与者不参与重构,因此可以更加灵活地应用到实际场景中.对构造的方案按照FSS 方案所定义的t-安全性(即任意t个参与者联合不能得到秘密函数任何信息)进行严格的安全性证明,证明结果表明本文构造的TFSS 方案满足信息论意义下的t-安全性,即可以抵抗具有无限计算能力的敌手,因此相对于文献[5,6,9]中的FSS 方案本文构造的TFSS 方案具有更高级别的安全性.除此之外当分享的秘密函数为点函数fa,b(x):{0,1}l→{0,1}m时,本文构造的TFSS 方案的通信复杂度为 O (l).低于文献[5,6,9]中FSS 方案的通信复杂度.另外我们注意到Yuan 等[11]运用多项式插值技术构造了含有门限的FSS 方案,但是Yuan 等并没有对其方案按照FSS 方案所定义的t-安全性进行严格的安全性证明.经过分析发现,在他们的方案中任意一个参与者可以通过自己收到的子函数得到秘密函数的部分信息,进而任意两个参与者联合就可以得到整个秘密函数,因此其方案不能满足t-安全性.本文对他们构造不满足t-安全性的原因进行了具体分析和阐述.

1 相关概念

本节将给出本文所用到的一些概念和定义,包括点函数的定义,Shamir 门限秘密分享方案,函数秘密分享方案的定义及其安全模型.

定义1(点函数).设{ 0,1}l为定义域,{ 0,1}m为值域,其中l,m为正整数,则对任意的a∈{0,1}l,b∈{0,1}m,点函 数fa,b(x):{0,1}l→{0,1}m的定义 如 下:对任意 的x∈{0,1}l有,

定义2 (Shamir 门限秘密分享方案[1]).令GFq为q元有限域,D为发送者,P={P1,···,Pn}为n个参与者组成的集合且q>n,z1,···,zn为GFq上n个两两不同的非零公开值.若s∈GFq为秘密值,r为门限值,则(r,n)-Shamir 门限秘密分享方案包含以下两个阶段:

1)分发阶段:发送者D从有限域GFq中随机均匀地选取r−1个 值a1,···,ar−1,生成r−1次 多项式f(x)=s+a1x+···+ar−1xr−1,发送者D计算si=f(zi)(i=1,···,n),并将si安全地发送给每位参与者Pi.

2)重构阶段:对任意r个参与者{Pi1,···,Pir}⊆{P1,···,Pn},他们利用公开值z1,···,zn计算值插值系数cih=并通过多项式插值公式重构出秘密

定义3 (函数秘密分享[5]).设1λ为安全参数,Df为定义域,Rf为值域,秘密函数为f(x):Df→Rf,n为参与者个数,r为重构门限值,则t-安全 (t

(1)Gen(1λ,f)→(k1,···,kn):输入安全参数和秘密函数,输出n个子函数k1,···,kn.

(2)Eval(i,ki,x0)→yi:任意的x0∈Df,参与者Pi(i=1,···,n)输 入(i,ki,x0),输出值yi.

(3)Dec(yi1,···,yir)→f(x0):输入 (yi1,···,yir),输出秘密函数在点x0处 的函数值f(x0).

上述方案满足以下正确性和t-安全性:

正确性:若上述FSS 方案中的3 个算法(Gen,Eval,Dec)都能顺利且正确的执行,则任意r个参与者可以重构出秘密函数f(x):Df→Rf在x0处的函数值f(x0).

t-安全:若存在受贿参与者集合T⊆{P1,···,Pn}且|T|=t,则不可区分性实验可描述如下:

1)敌手 A输入安全参数1λ输出(f0,f1),满足Df0=Df1,并将产生的(f0,f1)发送给挑战者C.

2)挑战者 C收到(f0,f1)后,随机地选取挑战值c∈{0,1},执行子函数生成算法输入fc,输出(k1c,···,kcn),并将{kic}i∈T发送给A.

3)敌手 A 收到{kic}i∈T后根据自己所掌握的信息给出关于挑战值c的猜测.

对于任意概率多项式时间敌手A,若存在关于λ 的可忽略函数u(λ)[12]使得u(λ),则我们称(Gen,Eval,Dec)为计算意义下t-安全的FSS 方案.

对任意拥有无限计算能力的敌手 A,若Adv(1λ,A,T)=则我们称(Gen,Eval,Dec)为信息论意义下t-安全的FSS 方案.

2 门限FSS 方案TFSS(Gen,Eval,Dec)

本节采用了多项式技术构造了TFSS 方案,按照FSS 定义的t-安全的安全模型证明了本文构造的TFSS 方案具有信息论意义下的t-安全性,并对方案的通信复杂度进行了具体的分析.

2.1 TFSS(Gen,Eval,Dec)

若秘密函数为点函数fa,b(x):{0,1}l→Fq,n为参与者个数,r=2lt+1(r

(1)Gen(1λ,fa,b)→(k1,···,kn)

① 将a∈{0,1}l转换为二进制进行表示,则a=(a1,···,al),其中aj∈{0,1}(j=1,···,l).

③ 发送者D从GFq中随机均匀的选取lt个值rj,1,···,rj,t(j=1,···,l),并产生2l个关于z的2t次多项式

④D使用公开值z1,···,zn计 算并生成

⑤ 输出(k1,···,kn).

(2)Eval(i,ki,x0)→yi

① 对于任意的x0∈{0,1}l,将x0用二进制表示为x0=(x10,···,x0l).

②Pi计 算

③ 输出yi.

(3)Dec(yi1,···,yir)→y

① 参与者Pih(h=1,···,r)通 过公开值z1,···,zn计算

正确性:在TFSS 方案中子函数ki=(g1,i,···,gl,i;,···,)(i=1,···,n),其中,为关于z的2t次多项式,且在子函数计算算法中每个参与者Pi(i=1,···,n)计 算yi=Eval(i,ki,x0)=因为(zi,yi)为关于z的2lt次多项式上的一点,所以任意r=2lt+1个 参与者Pih(h=1,···,r)可通过子函数kih和公开值z1,···,zn计算得到的(zi1,yi1),···,(zir,yir)为 多项式f(z)上 的2lt+1个点.此时参与者{Pi1,···,Pir}可以通过多项式插值公式计算:

2.2 TFSS 方案的安全性分析

定理1.若GFq为q元有限域,1λ为安全参数,则TFSS (Gen,Eval,Dec)是 关于 秘密 函数fa,b(x):{0,1}l→{0,1}m的信息论意义下t-安全的FSS 方案.

证明:假设 A为任意具有无限计算能力的敌手则关于敌手 A存在受贿参与者集合T⊆{P1,···,Pn},且|T|=t(为了简便起见我们不妨取T={P1,···,Pt})的不可区分性实验,描述如下:

(1)敌手 A输入安全参数1λ输出(fa0,b0,fa1,b1),满足a0,a1∈{0,1}l,b0,b1∈{0,1}m,并将(fa0,b0,fa1,b1)发送给挑战者 C.

(2)挑战者 C 收到(fa0,b0,fa1,b1)后,随机地产生挑战值c∈{0,1},执行子函数生成算法输入fac,bc,输出(kc1,···,knc),并将 {kic}i∈T发送给敌手 A.

(3)敌手 A 收到{kic}i∈T后,根据自己所掌握的信息给出一个关于挑战值c的猜测.

此时敌手A 可以通过子函数kuc计 算wj,u=gcj,u+=bcj+rj,1·zu+···+rj,t·ztu,j=1,···,l,u=1,···,t,满足以下等式关系:

因为Z为非退化矩阵,R为一个随机矩阵,所以对于敌手 A 来说矩阵W为一个随机矩阵,则敌手 A不能得到bcj(j=1,···,l)的任何信息.又因为:

则敌手 A不能得到acj,bcj,(c∈{0,1})的任何信息,进而敌手 A不能得到关于挑战值c的任何信息.所以Adv(1λ,A,T)=则定理1 得证.

2.3 TFSS 方案的通信复杂度分析

在方案TFSS 中ki=(g1,i,···,gl,i;,···,)(i=1,···,n), 其gj,i=gj(zi),=(zi)∈Fq,因此|ki|=2l·logq2.因为yi∈Fq,则|yi|=logq2.因此=(2nl+h)·logq2.因为 (n,r,logq2)为常数,则 Ψ=O(l).

3 文献[11]的方案及其分析

本节对文献[11]构造的方案进行了具体的描述,并对其方案的不满足方案所定义的t-安全性的原因进行了具体的分析.

3.1 文献[11]的方案

为了解决现有FSS 方案不具有门限的问题,文献[11]给出了秘密函数为fa,b(x):{0,1}l→GFq,n为参与者的个数,t(t=l+1,t

正确性:在文献[11]方案中存在关于z的l次多项式f(z)=其常数项f(0)=对于任意的x0∈{0,1}l,若x0≠a,则存在x0j≠aj,因此有f(0)=0.若x0=a,则对任意的 (j=1,···,l)都有x0j=aj,因此有所以f(0)=因此关于z的l次 多项式f(z)的常数项f(0)=fa,b(x0).而每个参与者Pi通过ki(i=1,···,n)计算的值yi=因此任意t(t=l+1,t

通过分析发现文献[11]的方案在保证方案正确重构的前提下,其方案可以容忍n−t个参与者不参与重,因此其方案可以更加灵活地应用到现实场景.

3.2 安全性分析

本小节对文献[11]方案的安全性进行分析.详细分析了每个参与者如何通过自己的子函数来计算得到秘密函数fa,b中b的值,以及任意两个参与者联合如何计算得到整个秘密函数fa,b,具体过程如下:

1)参与者Pi(i=1,···,n),通过ki计算秘密函数fa,b中b的值.

2)任意两个参与者(不妨设为P1,P2)联合通过k1,k2计算出秘密函数fa,b.

参与者P1收 到子函数k1=参与者P2收 到子函数k2=由1)中的分析可知,参与者P1,P2分 别通过子函数k1,k2计算出bj(j=1,···,l).此时参与者P1利 用计算得到的bj,子函数k1,k2和 公开值z1,z2计算同样参与者P2利用计算得到的bj,子函数k1,k2和公开值z1,z2计算随后P1计算P2计算此时参与者P1,P2可以分别独自计算出a=(a1,···,al).

基于上述分析可知,在文献[11]方案中任意两个参与者联合可以通过子函数和公开值计算出a,b的值,从而得到秘密函数fa,b且任意参与者可以通过子函数计算得到秘密函数fa,b中b的值.所以其方案不能抵抗t个参与者的联合,因此不满足FSS 方案中所定义的t-安全性.

3.3 通信复杂度分析

在文献[11]的方案中ki=(i=1,···,n),其gj,i=因 此|ki|=2l·logq2.因 为yi∈Fq,则|yi|=logq2.因 此Ψ=因为(n,t,logq2)为常数,则Ψ=O(l).

4 TFSS 方案与现有FSS 方案的比较

本节我们将本文构造的基于多项式插值的门限函数秘密分享TFSS 方案与现存的文献[5,6,9,11]中的FSS 方案在方案所基于的工具,有无门限值特性,方案的安全性的级别以及方案的通信复杂度4 个方面进行全面的比较.为了比较的方便,假设所有FSS 方案分享的秘密函数均为点函数fa,b(x):{0,1}l→GFq,λ 表示伪随机生成器种子的长度,t表示重构门限值,n表示参与者的个数.具体比较结果见表1.

表1 TFSS 方案与现有FSS 方案的比较

经过比较发现本文构造的TFSS 方案相对于文献[5,6,9]中构造的FSS 方案具有额外的门限特性,即在重构的过程中可以容忍参(n−r)个参与者不参与,因此可以更加灵活地应用于现实场景,且在安全性级别上由2.2 节中对TFSS 方案的安全性证明可得其为信息论意义下t-安全的,而文献[5,6,9]中构造的FSS 方案构造均基于伪随机生成器,所以其方案的安全性基于密码学中单向函数的存在性假设,进而为计算意义下t-安全的.因此TFSS 方案相对于文献[5,6,9]中构造的FSS 方案具有更高级别的安全性.此外在分享的秘密函数均为fa,b(x):{0,1}l→GFq的前提下,由2.3 节对TFSS 方案的通信复杂的分析可得,TFSS 方案的通信复杂度为O (l),低于文献[5,6,9]中构造的FSS 方案的通信复杂度.在与文献[11]中构造的FSS 方案对比中可以发现,虽然TFSS 方案与文献[11]中构造的FSS 方案均具有门限的特性,且具有相同级别的通信复杂度.但在安全性上经过3.3 节对文献[11]中构造的FSS 方案的安全性分析可得,其方案不具有FSS 方案定义的t-安全性,而本文构造的TFSS 方案具有信息论意义下t-安全性.

5 结语

本文针对现有的函数秘密分享方在重构阶段需要所有参与者参与不能灵活的适用于现实场景的问题,采用多项式技术构造了门限函数秘密分享方案.并按照函数秘密分享方案定义的安全模型证明了新构造的门限函数秘密分享方案为信息论意义下安全的.并对文献[11]构造了门限函数秘密分享方案进行的分析,指出了其方案存在安全性漏洞.最后本文将新构造的门限函数秘密分享方案与现有的函数秘密分享方案进行了比较,发现其具有更高级别的安全性和更高的效率.但事实上,本文构造的门限函数秘密分享方案的门限值r是受限的,要求r=2lt+1.因此在未来是否能构造出门限值自由的函数秘密分享方案是一个值得继续思考的问题.