《现代密码学》课件第8章.ppt

1、第8章 多方密码协议 8.1 秘密共享与门限密码体制 8.2 零知识证明 8.3 安全多方计算 第第8章章 多方密码协议多方密码协议 第8章 多方密码协议 8.1 秘密共享与门限密码体制秘密共享与门限密码体制8.1.1 秘密共享秘密共享1.秘密共享概述秘密共享概述秘密共享(secret sharing)是指在多个参与方之间共享秘密s的策略，每个参与方p得到的信息S(p)是秘密的一部分，称为一个份额或影子份额或影子(share/shadow)，设P为参与方集合，则只有P的某些特定的子集集合2P能利用其掌握的份额集合重构秘密，这些子集的集合被称为访问结构访问结构或存取结构存取结构(access s

2、tructure)。如果非授权集中的参与方无法得到秘密s的任何信息，则称这样的秘密共享方案为完善的完善的(perfect)。对A，如果ABP时必有B，则称访问结构是单调的。此时如果令m表示中最小元素之集，则由m可以确定出的全部元素，称m为访问结构的基(basis)。第8章 多方密码协议 现有的秘密共享体制主要有以下几种分类方法：(1)按照分发份额及重构秘密时有无可信任的仲裁者参与，分为有仲裁的秘密共享和无仲裁的秘密共享；(2)按照参与方的非授权子集是否能得到秘密的部分信息，分为完善秘密共享和非完善秘密共享，或理论安全和计算安全的秘密共享；(3)按照秘密的数量，可分为单个秘密共享和多重秘密共享；

3、(4)按照有无验证机制，可分为可验证的秘密共享和不可验证的秘密共享。第8章 多方密码协议 除此之外，人们还根据不同的应用需求而有针对性地设计了许多其它秘密共享方法，这里不再一一列举。秘密共享技术实现了“不把鸡蛋放在同一个篮子里”的目的，从而当某个参与者实施欺骗或者其手中的份额丢失时，仍可恢复秘密，这实际上是通过引入冗余来提高数据服务的可靠性。同时，大多数秘密共享还可以实现无条件的安全性，即其安全性不是建立在某个计算上困难的问题之上，而是可以从Shannon信息论的角度证明无信息泄露，即使攻击者有无限的计算资源和时间，也无法得到秘密的任何信息。第8章 多方密码协议 秘密共享因为上述优点而在国内外

4、得到了非常广泛的研究和关注，主要有以下几方面的研究工作。1)对一般形式的访问结构构造秘密共享方案在秘密共享方面最早的研究是(k,n)门限方案的构造，后来人们开始关注更为通用的方案，Saito和Nishizeki证明了对任意的访问结构，均存在可以实现它的秘密共享方案3。Benaloh和Leichterr提出了更为简单和有效的秘密共享方案，可以在任何单调访问结构中实现4。第8章 多方密码协议 2)秘密共享的效率算法的效率主要用计算量和占用的存储空间来衡量。在现有的线性门限方案中，份额计算和秘密重构算法均为多项式时间复杂度，因而份额长度成为影响效率的关键因素。秘密共享实际上是一种冗余机制，在实际应用

5、中，为了提高安全性，同时降低存储量，秘密份额的长度应尽量小，人们提出了许多方法使份额的长度保持在适当范围内。第8章 多方密码协议 秘密共享方案的一个重要参数是其信息率(information rate)。信息率(,S)定义为共享秘密的长度与份额的最大长度之比：这里,S为所有可能的秘密集合。如果()=1，则称为理想的(ideal)秘密共享方案，通常()1。设为访问结构，如果存在一个理想的秘密共享方案能实现，则称是理想的访问结构。在(k,n)门限方案中，份额与秘密具有相同规模，然而在对一般访问结构构造的方案中，份额长度通常大于秘密长度。以下例子给出了一个简单的理想秘密共享方案5。22log,max

6、 logpSSS p 第8章 多方密码协议 例例8-1 设秘密空间与份额空间均为GF(3)，参与者集合为a,b,c，访问结构=a,b,b,c,a,b,c。构造秘密共享方案如表8-1所示。第8章 多方密码协议 第8章 多方密码协议 表中，D为原始秘密；Sa,Sb,Sc分别为a,b,c的份额。注意到在每行中，D=SaSb=SbSc，然而由于每行的Sa与Sc均相等，因此a与c组合将得不到D的任何信息。第8章 多方密码协议 构造理想的秘密共享方案是秘密共享方面的重要研究课题，后面介绍的Balkley方案和Shamir门限方案均为理想的秘密共享体制。除此之外，这方面还有许多文献6-7。参考文献6中利用向

7、量空间构造证明了判定理想访问结构的充分条件；参考文献7中则利用拟阵的方法给出了必要条件。对于任意给定的访问结构，寻找理想的秘密共享方案是不太现实的，因而人们只能试图找到使信息率尽可能大的方案。访问结构的最佳信息率(optimal information rate)定义为*()sup(,S)第8章 多方密码协议 这里,sup()是指对所有可能的秘密集合|S|2和所有能实现的秘密共享方案求极大值。显然，理想的访问结构的最佳信息率为1。寻找任意访问结构的最佳信息率，并求出其上、下界也是一个尚未解决的重要研究内容。为了减少秘密份额的长度，人们将秘密共享与其它技术相结合，构造了一些新的方案，如Rabin

8、的IDA(Information Dispersal Algorithm)8和Krawczyk的“短”秘密共享方案9(将在8.1.2节介绍)。第8章 多方密码协议 3)安全性秘密共享中的不安全因素包括：某个合法参与者拒绝提供份额而无法恢复秘密；非授权成员伪装为合法成员骗取秘密份额以及仲裁者分发给参与者错误份额，等等。针对不同安全问题，人们提出了不同的解决方法。比如构造完善的秘密共享方案，使得非授权的参与方集合无法得到秘密的任何信息；对现有的门限方案进行改进，使其具有预防欺骗的功能；在分发秘密份额时加入仲裁者的签名信息，等等。8.1.2节将详细讨论如何在门限方案中防止欺骗。第8章 多方密码协议

9、4)应用在应用方面，一个典型的例子是门限数字签名。门限签名是群签名的一种，在群签名中，通过设计适当的协议，可以使群中的某个成员代表整个群体进行签名，而门限签名则要求群中参与签名的人数必须大于某个门限值，从而防止个别不诚实的参与方进行欺骗。门限签名可以用秘密共享技术实现。除此之外，秘密共享还在信息系统可生存性研究及数据的分布式存储中有着重要应用。第8章 多方密码协议 2.(k,n)门限方案门限方案(k,n)门限方案是一类特殊的秘密共享方案，Shamir和Blakley于1979年各自独立地提出了门限方案的思想，并采用不同方法将之实现10-11。在(k,n)门限方案中，n表示参与方个数，k表示要重

10、构秘密需要的最少份额数，其访问结构是所有k元素子集构成的集合。门限方案是理想的秘密共享方案。第8章 多方密码协议 定义定义8-1 设D为取自有限集S的某一秘密数据，又设n个参与者各自拥有份额Di，DiS，i=1,2,n。集合称为一个(k,n)门限方案，如果以下两个条件成立：(1)利用任意k个不同的份额均可容易地求得D，从Shannon信息论的角度，即1niiD0,21kiiiDDDDH第8章 多方密码协议 (2)利用任意小于k个不同的份额都无法有效地求得D，即门限方案可以写成更一般的形式，即(t,k,n)门限方案，其中任意k个不同的份额可以容易地重构秘密，而当份额数量不大于t时，将得不到关于秘

11、密D的任何信息。现有的方案中，一般令k=t+1。121,kiiiDDDDHDH第8章 多方密码协议(k,n)门限方案可以利用不同领域的数学知识来构造，其中比较著名的有Shamir的基于有限域上的拉格朗日插值多项式方案10、McEliece的基于Reed-Solomon码的门限方案12、基于中国剩余定理的Asmuth-Bloom方案13、利用超平面构造的Blakley方案11以及Karnin-Greene-Hellman方案14，等等。Kothari证明了上述五种方案均可看做一般线性门限体制的某种特例15，他还使用线性几何的概念，给出了一般线性门限体制的定义。下面我们一一介绍这些方案。第8章 多

12、方密码协议 1)Shamir的插值多项式构造方案设q为素数的幂，是有限域GF(q)中的本原元，设要共享的秘密为DGF(q)，随机选取GF(q)上的k1次多项式f(x),使得f(x)=D+a1x+a2x2+ak1xk1其中,aiGF(q)，i=1,2,k1，且ak10。对n个互不相同的i，i=1,2,n，计算di=f(i)，则集合即构成一个(k,n)门限方案。1 nijd第8章 多方密码协议 证明：证明：假设k个参与者提供了k个份额di，i=1,2,k，则根据拉格朗日插值公式，有进而得到f(x)的常数项，即秘密D=f(0)，并且每个参与者i均可利用自己掌握的份额di来验证所求得的f(x)是否正确

13、，从而可以发现其它参与方的欺骗行为。kikijjjijixdxf11第8章 多方密码协议 另一方面，当份额数量rQ；(2)m1m2pmnk+2mnk+3mn。对于i=1,n，令Mi=M/mi，且设是Mi mod mi的逆，则。由于(Mi,mi)=1，因此这个逆存在而且可以用Euclid算法求出。由中国剩余定理可知，同余方程组xai mod mi，i=1,n，有解，并且在模M的意义上，该解是唯一的，这里0aimi，i=1,n。NpiM1modiiiM Mm1niiiixa M M第8章 多方密码协议 随机选取正整数，定义秘密数据为D=Q+rp，且DN。令ai=(D mod mi)，i=1,n，则

14、有定理8-2。定理定理8-2 集合(mi,ai)ni=1构成关于秘密D的一个(k,n)门限方案。证明：证明：假设k个参与者提供的份额为(mi1,ai1),(mik,aik),令M=mi1mik，Mj=M/mij，i=1,k，而且设是Mj mod mij的逆。定义 ，由中国剩余定理求得yD mod M，因为DN，故D=y mod M。这说明利用(mi1,ai1),(mik,aik)可以重构D。10pNrjM1kijjjjya M M第8章 多方密码协议 另一方面，若只有k1个参与者，则只能求得DD mod N，其中N为k1个模数mi的乘积，由条件(4)得。因为(N,p)=1，而根据以上讨论得，故

15、方程y mod N=D的解不唯一。事实上，y的取值将在mod p的所有同余类中均匀分布，因此无法确定D。NNpNpN第8章 多方密码协议 4)Blakley方案设参与者为Ai，i=1,2,n，仲裁者为D，V为GF(q)上的k维向量，其中q为素数幂。Blakley构造的(k,n)门限方案包含以下步骤：(1)D固定V中的一条线l，将其对所有参与者公开，而l上的所有q个点即为q个可能的秘密值；(2)设秘密为p，D首先随机地构造k1维子空间H，H与l相交于某个点，然后D构造超平面Hp=H+p，注意Hpl=p；第8章 多方密码协议(3)D在Hp中随机选择n个点si，i=1,2,n，使得集合psi：i=1

16、,2,n 中的任意j(jk)个不会位于同一个j2维超平面中；(4)D将si作为秘密份额分发给Ai，i=1,2,n。假设有k个参与者提供了份额，则可以唯一地确定超平面Hp，再通过计算Hpl就能得到原始秘密p。然而任意k(k1。随机选取n维行矢量u=(u1,u2,un)，求出n+1个nm阶矩阵A0,A1,An，要求其中任意k个拼成的nn阶矩阵B满足:为满秩矩阵。nniiikAAAB21第8章 多方密码协议 将秘密数据表示为m维矢量d=uA0，每个用户的秘密份额为di=uAi，i=1,2,n，A0为公用信息，于是构成一个(k,n)门限方案。当k个参与者提供了秘密份额时，构造未知量为u的方程组如下：(8-1)kkiiiiiidAdAdA,2211niiidA1,1,2,jjiiduAjk第8章 多方密码协议 由于n=km，因此可将式(8-1)改写为 (8-2)112212kkTTiiTTiiTTniiAduAduuAd第8章 多方密码协议 这个方程组有n个未知量u1,u2,，un，其系数矩阵为满秩矩阵，存在唯一的解，即u=(u1,u2,un)。于是可以得到秘密信息d=uA0。当份额数量小于k时