秘密共享方案-课件.ppt

1、第13章 秘密共享方案 报告人：孙宗臣1ppt课件 有些场合，秘密不能由一个人独自拥有，必须由两人或多人同时参与才能打开秘密，这时都需要将秘密分给多人掌管，而且必须有一定人数的掌管秘密的人同时到场才能恢复这一秘密，这种技术就称为秘密分割(SECRET SPLITTING)，也称为秘密共享(SECRET SHARING)。例如：导弹控制发射 开启核按钮 重要场所通行检验等 为了实现上述意义上的秘密共享，人们引入了门限方案(THRESHOLD SCHEME)的一般概念2/13.1引言2ppt课件 秘密分割门限方案的定义 定义1 设秘密 S 被分成N个部分信息，每一部分信息称为一个子密钥或影子(SH

2、ARE OR SHADOW)，由一个参与者持有，使得：由K个或多于K个参与者所持有的部分信息可重构S 由少于K个参与者所持有的部分信息则无法重构S 则称这种方案为(K,N)秘密分割门限方案，K称为方案的门限值。极端的情况下是(N,N)秘密分割门限方案，此时用户必须都到场才能恢复密钥3/13.1引言3ppt课件 如果一个参与者或一组未经授权的参与者在猜测秘密S时，并不比局外人猜秘密时有优势，即 由少于K个参与者所持有的部分秘密信息得不到秘密S的任何信息 则称这个方案是完善的，即(K,N)秘密分割门限方案是完善的 攻击者除了试图恢复秘密外，还可能从可靠性方面进行攻击，如果他能阻止多于N-K个人参与

3、秘密恢复，则用户的秘密就难于恢复 所以(K,N)门限的安全性在于既要防止少于K个人合作恢复秘密，又要防止对T个人的攻击而阻碍秘密的恢复 当N=2T+1时K=T=(N-1)/2的取值最佳 秘密分割应该由可信第三方执行，或者托管设备完成。4/13.1引言4ppt课件13.1 引言 秘密的秘密的分割分割 假设是一个(K,N)门限方案 选取一个K1次多项式F(X)A0+A1X+AK-1XK-1 该多项式有K个系数 令A0=F(0)=S，即把常数项指定为待分割的秘密 其它K1个系数可随机选取 显然，对于该多项式，只要知道该多项式的K个互不相同的点的函数值F(XI)(I=1,2,K)，就可恢复F(X)生成

4、N个子秘密 任取N个不同的点XI(I=1,N)并计算函数值F(XI)(I=1,N)则(XI,F(XI),I=1,N,即为分割的N个子秘密 显然，这N个子秘密中的任意K个子秘密即可重构F(X)，从而可得秘密S5/5ppt课件13.2 SHAMIR门限方案 SHAMIR门限方案基于多项式的LAGRANGE插值公式 插值：数学分析中的一个基本问题 已知一个函数(X)在K个互不相同的点的函数值(XI)(I=1,2,K)，寻求一个满足F(XI)(XI)(I=1,2,K)的函数F(X)来逼近(X)，F(X)称为(X)的插值函数，也称插值多项式 LAGRANGE插值：已知(X)在K个互不相同的点的函数值(X

5、I)(I=1,2,K)，可构造K-1次LAGRANGE插值多项式 显然，如果将函数(X)就选定F(X)，则差值多项式刚好完全恢复了多项式(X)F(X)6/kjllljlkjjxxxxxxf11)()(6ppt课件13.2 SHAMIR门限方案 根据上述的思想，在有限域GF(Q)上实现上述方案，即可得到SHAMIR秘密分割门限方案（1）秘密的分割 设GF(Q)是一有限域，其中Q是一个大素数，满足QN1 秘密S是在GF(Q)0上均匀选取的一个随机数，表示为SRGF(Q)0 令S等于常系数A0 其它K-1个系数A1,A2,AK-1的选取也满足AIRGF(Q)0(I=1,K-1)在GF(Q)上构造一个

6、K-1次多项式F(X)A0+A1X+AK-1XK-1 N个参与者记为P1,P2,PN，其中PI分配到的子密钥为（I,F(I)）7/7ppt课件13.2 SHAMIR门限方案(2)秘密的恢复 如果任意K个参与者PI1,PI2,PIK(1I1I2IKN)要想得到秘密S，可使用它们所拥有的K个子秘密(IL,F(IL)|L=1,K构造如下的线性方程组 A0A1(I1)AK-1(I1)K-1=F(I1)A0A1(I2)AK-1(I2)K-1=F(I2)A0A1(IK)AK-1(IK)K-1=F(IK)（13-1）8/8ppt课件13.2 SHAMIR门限方案 因为IL(L=1,K)均不相同，所以可由LA

7、GRANGE插值公式构造如下的多项式：F(X)从而可得秘密SF(0)然而参与者仅需知道F(X)的常数项F(0)而无需知道整个多项式F(X)，所以令X0，仅需以下表达式就可以求出S：S=，（可以预计算不需保密 ）)(mod)(mod)(111qybqiiiifkjijkjlljllkjjj9/kjllljlkjjqiiixif11)(mod)(jb9/方案的完善性分析 如果K-1个参与者想获得秘密S，他们可构造出由K-1个方程构成的线性方程组，其中有K个未知量 对GF(Q)中的任一值S0，可设F(0)S0，再加上上述的K-1个方程就可得到K个方程，并由LAGRANGE插值公式得出F(X)。因此对

8、每一S0GF(Q)都有一个惟一的多项式满足13-1方程组 所以已知K-1个子密钥得不到关于秘密S的任何信息，因此这个方案是完善的。10/13.2 SHAMIR门限方案10ppt课件【例81】设门限K=3，份额数为N=5，模值Q=19，待分割的秘密S=11，随机选取A1=2，A2=7，可构造多项式 F(X)=(7X2+2X+11)MOD 19 将秘密分割成5份 分别计算 F(1)=(712+21+11)MOD 191 F(2)=(722+22+11)MOD 195 F(3)=(732+23+11)MOD 194 F(4)=(742+24+11)MOD 1917 F(5)=(752+25+11)M

9、OD 196 得5个子密钥。11/13.2 SHAMIR门限方案11ppt课件13.2 SHAMIR门限方案 秘密的恢复 如果知道其中的3个子密钥,如F(2)=5，F(3)4，F(5)6，就可重构F(X)，事实上我们可直接根据差值公式 计算S=F(0)kjllljlkjjkqiiiif111)(mod)()1(19mod)353252)5()535232)3()525323)2()1(13fff12/1112/89ppt课件13.2 SHAMIR门限方案 简化的（T,T）门限方案：1.D 秘密的选取（独立随机选取）中的 T-1 个元素，记为 ，2.D计算 ，3.对于 ，D 把共享 的值发给 。

10、13ppt课件中国剩余定理，又称孙子定理l设m1,m2,mk是k个两两互素的正整数，m=m1m2mk,Mi(i=1,k)满足m=miMi，则同余式组lx=b1(mod m1)lx=b2(mod m2)l lx=bk(mod mk)l有唯一解：有唯一解：x=M 1M1b1+M 2M2b2+M kMkbk(mod m)l其中其中M iMi=1 mod mi(i=1,2,k)14/(补充)基于中国剩余定理的门限方案14ppt课件l设m1m2mnmn-1mn-k+2l注意这里的条件m1m2mnmn-1mn-k+2表明最小的k个数的乘积也比最大的k-1个数的乘积大l显然，m1,m2,mn中任意k个数的乘

11、积都比m1m2mk大15/(补充)基于中国剩余定理的门限方案15ppt课件l设s是待分割的秘密数据，令s满足lmnmn-1mn-k+2sm1m2mkl即s比最大的k-1个数的成绩大，同时比最小的k个数的乘积小l从而：l对任意k个数的乘积T，ss mod T，模运算不起作用l而任意k-1个数的乘积R有s mod R在数值上不等于s16/(补充)基于中国剩余定理的门限方案16/l 为了分发秘密，计算m=m1m2mnl 然后计算 si=s(mod mi)(i=1,2,n)l 以(si,mi,m)作为一个子秘密l 集合(si,mi,m)i=1n即构成了一个(k,n)门限方案17/(补充)基于中国剩余定

12、理的门限方案17/l对任取的k个参与者，不失一般性，设这k个参与者为P1Pk中，每个参与则Pi计算lMim/mi，NiMi-1(mod mi)，yi=siMiNil结合起来根据中国剩余定理可求得lsl由于任意k个或k个以上的模数相乘都比s大，它们恢复出来的s必然相同，而少于k个参与者则不行18/(补充)基于中国剩余定理的门限方案18/13.3 访问结构和一般的秘密共享 定义：在W 个参与者（记为集合P）中共享密钥K的方法称为是实现访问结构 的一个完善的秘密共享方案，如果满足以下两个条件：（1）对于一个授权的参与者子集 ，如果把他们的共享集中到一起，那么就可以确定密钥K的值。（2）对于一个未授权

13、的参与者子集 ，如果把他们的共享集中到一起，那么他们也不能确定关于K值的任何信息。如果 且 ，则 ，我们称访问结构满足单调性（本章假设均为单调）19ppt课件13.3 访问结构和一般的秘密共享 设 是一个访问结构，称 是一个最小授权子集最小授权子集，如果对于任何满足 和 的集合A 都有 。的最小授权集合记为 ，称为 的基。在（T,W）门限访问结构的情况中，基恰好是由所有T 个参与者的所有子集组成。定义：子集 是最大的非授权子集，如果对于所有的 ，都有 。ABABA00:,CP BC B 11,BB BB1B 20ppt课件13.3.1 单调电路构造 设 我们得到布尔公式 算法：单调电路构造（C

14、）当存在线 使得 未定义时，循环以下操作：找到C的一个门G使得 已经被定义，其中 是G的输出线，但是对于G的任意出入线来说，都没定义过。（1）如果G是一个“或”门，那么对于G的每一个输入线W，（2）否则，令G的输入线是 ，独立的选择 中的 个元素，记为 FOR DO 012413423,P P PP P PP P 12413423()()()PPPPPPPP()outf WK()f W()Gf WGW()f W()()Gf Wf W1,.tWW1t,1,1,.,GG tyy1,1()modtG tGG iiyf Wym1,.,it,()iG if Wy21ppt课件 例题A 12413423(

15、)()()PPPPPPPP12Kaa1Kc12Kbb121111(,)(,)yya b122221(,)(,)yya c123321(,)(,)yyb Kc12441212(,)(,)yyKaaKbb012413423,P P PP P PP P 1213142434,P PP PP PP PP P非授权子集13.3.1 单调电路构造22ppt课件12413423()()()PPPPPPPP 变成合取范式：例题B定理：设C是任意的单调布尔电路，则单调电路的构造可产生一个能够实现访问结构的完善秘密共享方案。（略）1213142434()()()()()PPPPPPPPPP1234Kaaaa()C

16、13.3.1 单调电路构造1213142434,P PP PP PP PP P非授权子集23ppt课件 假设 是一个访问结构并且 是分发规则的集合。我们称 是一个实现访问结构 的完善秘密共享方案，如果下面两个性质：l对于任何的授权子集 ，不存在两个分发准则 和 ，其中使得 （即对于授权子集B中的参与者，共享的任何分发都可以确定密钥K的值）l对于任何非授权子集 和任何共享的分发 ，有下式成立 对于任意 （即对于非授权的子集B，给定共享的分发 ,K 上的条件概率分布和K 上的先验概率分布是相同的。换句话说，B 的共享的分发没有提供关于K 值的任何信息 ）13.3.2 单调电路构造(正式定义)kk

17、KFFFBPkf Fkf Fkk|BBffBPBBgSPr|()PrBKk S BgKkkK24ppt课件 定义：假设我们有一个实现访问结构 的完善秘密共享方案。的信息率定义为比率（注意，表示 所有可能收到的共享集合：当然，）。方案的信息率记为并定义为 例题：，（）因此例题：所以 。我们更倾向于方案一，其信息率高些。13.4 信息率和高效方案的构造|()|iilb Klb S P()iS P()iS PSmin:1iiw 212ilbmlbm1,.,4i 12142311,231325ppt课件 定理定理13.2：设C是任意的单调布尔电路，则存在一个实现访问结构 的完善秘密共享方案，其信息率是

18、 其中 是C中带有输入线的根数。可以看出，shamir门限方案的信息率是 1，下面会证明这是一个最优值。相比之下，使用析取范式的布尔电路实现的（t,w）门限方案的信息率是 ，当这是一个非常低的值（因此是不佳的）定理定理13.3：对于实现一个访问结构的任何完善的秘密共享方案，都有 。13.4 信息率和高效方案的构造(C)1/r:1miiwni ri111wt1tw 126ppt课件 设 是一个访问结构，是 上所有d元组组成的向量空间，假设存在函数 满足性质 话句话说，向量 可以表示为 中向量的线性组合当且仅当B是一个授权子集。对于给定的访问结构，只要我们找到满足该性质的向量的集合，那么就可以建立

19、相应的秘密共享方案，这个方案被称为Brickell 秘密共享方案。13.4.1向量空间构造()dpp:()dpP(1,0,.,0)(P):PiiBB(1,0,.,0)(P):PiiB27ppt课件密码体制13.3 Brickel 秘密共享方案输入：满足上述性质的向量 初始化阶段 对于 ，D把向量 给 D，这些向量公开。共享分发1.假设D 想要共享密钥K。D定义 ，并且他秘密的选择 中的d-1个元素2.对于 ，D 计算 ，其中 3.对于 ，D 把 的值作为共享分发给 。13.4.1向量空间构造1(P),.,(P)w1iw(P)()dip 1aKp()iiyaP1(,.)daaaiy28ppt课件

20、 定理13.4 假设 满足性质 ，则分法规则 ，的集合组成了一个实现访问结构 的理想秘密共享方案。证明：首先，我们证明 如果B 是一个授权子集，那么B中参与者能够计算K。因为 所以我们将其写成 其中每个 。的共享是 ，其中 是由D选定的未知向量，并且 .由内积运算的线性性，可得 13.4.1向量空间构造kK(1,0,.,0)():iiPPB :(1,0,.,0)()iiii PBcPipc()iiyaP:(1,0,.,0)()()iiiiii PBiiiii PBi PBkaacPc aPc y29ppt课件 如果B不是授权子集，假设对于某个 ，B 假设 。我们证明这样的猜测和她们所拥有的信息

21、是一致的。我们用 表示子空间的维数考虑方程组：这是一个含有 个未知量的线性方程组，因为则这个方程组是相容的，系数矩阵的秩是 ，解空间的维数为 （对任意的值这样在每个 恰好有 个分发规则，这和B共享的可能分发是一致的。有 13.4.1向量空间构造(),iiiPasPB0(1,0,.,0)ay(1,0,.,0)():iiPPB1e1de 0yF00Pr|PrBKygKy（详解参考例题13.8）30ppt课件定理 13.5 假设 是一个完整的多划分图，则存在一个理想秘密共享方案实现了参与者V上的基为 E 上的访问结构。13.4.1向量空间构造(,)GV E31ppt课件32ppt课件33ppt课件

22、定义 13.5 设 是一个访问结构，是分布规则的集合，则称 是实现访问结构的一个完善的秘密共享方案，如果满足以下两个条件：1.对于任何参与者的授权子集 ，。2.对于任何参与者的非授权子集 ，。引理13.7 假设设 是一个访问结构，是实现 的分发规则的集合，设 ，其中 则 引理13.8 假设 是一个访问结构，是实现 的分发规则的集合，设其中 ，则 。13.4.2 信息率上界FFBP(|)0H K B BP(|)()H K BH KFAB,A BP(|)()(|,)H A BH KH A B KFAB,A BP(|)(|,)H A BH A B K34ppt课件定理 13.9 假定 是一个访问结构

23、使得 和令 是任意实现 的完善秘密共享方案，则 。推论13.10假定 是满足定理13.9中假设的访问结构，并设密钥值是等概率选取的，则 。定理13.11 假设G 是一个非完全多划分的连通图，令 是具有基 的访问结构，其中是的边集，那么。由于对完全多划分图，定理告诉我们，对于一个访问结构，如果它的基是一个连通图的边集，那么永远不会出现的情况。,W XX YW Y Z,W YXW Z F()3()H XYH K2/3()G*()2/3G*1*2/3135ppt课件13.4.分解构造 定义假设是具有基的访问结构，令是一个指定的密钥集合。（对于密钥集的）的一个理想分解是由子集组成的集合，并满足下面的性质：1.对于，对于，对于具有基的访问结构来说，存在参与者集合是上的具有密钥集的理想方案。1,.,n1kn0k 01ukk kkBPB36ppt课件 定理（分解构造）假定是具有基的访问结构，是一个整数。令是一个指定的密钥集，对于，设是对于密钥集的理想分解。令是一个访问结构的参与者集合。对于每个参与者，定义则存在一个实现的完善的秘密共享方案，其信息率是其中。13.4.分解构造11h,1,.,hhhh nD ,1|:|iih jhRj PP/R max:1iRRiw 37ppt课件