秘密共享方案概要.ppt

13.2 SHAMIR门限方案 简化的（T , T）门限方案： D 秘密的选取（独立随机选取） 中的 T-1 个元素，记为 ， D计算 ， 对于 ，D 把共享 的值发给 。 中国剩余定理，又称孙子定理 设m1,m2, … , mk是k个两两互素的正整数，m=m1m2…mk, Mi(i=1,…,k)满足m=miMi，则同余式组 x=b1 (mod m1) x=b2 (mod m2) … x=bk (mod mk) 有唯一解：x=M?1M1b1+M?2M2b2+…+ M?kMkbk (mod m) 其中M?iMi=1 mod mi (i=1,2,…,k) */ (补充) 基于中国剩余定理的门限方案 1. 参数的选择 设m1m2…mn是n个大于1的整数，满足 (mi,mj)＝1(对任意的i，j，i≠j)，及两两互素，和 m1m2…mkmnmn-1…mn-k+2 注意这里的条件m1m2…mn是必须的，在此条件下，m1m2…mkmnmn-1…mn-k+2表明最小的k个数的乘积也比最大的k-1个数的乘积大 显然，m1, m2, …, mn中任意k个数的乘积都比m1m2…mk大 */ (补充) 基于中国剩余定理的门限方案 2. 秘密的分割 设s是待分割的秘密数据，令s满足 mnmn-1…mn-k+2sm1m2…mk 即s比最大的k-1个数的成绩大，同时比最小的k个数的乘积小 从而： 对任意k个数的乘积T，s＝s mod T，模运算不起作用 而任意k-1个数的乘积R有s mod R在数值上不等于s */ (补充) 基于中国剩余定理的门限方案 为了分发秘密，计算m=m1m2…mn 然后计算 si=s(mod mi) (i=1,2,…,n) 以(si,mi,m)作为一个子秘密 集合{(si,mi,m)}i=1?n即构成了一个(k,n)门限方案 */ (补充) 基于中国剩余定理的门限方案 秘密的恢复 对任取的k个参与者，不失一般性，设这k个参与者为P1…Pk中，每个参与则Pi计算 Mi＝m/mi，Ni＝Mi-1(mod mi)，yi=siMiNi 结合起来根据中国剩余定理可求得 s＝ 由于任意k个或k个以上的模数相乘都比s大，它们恢复出来的s必然相同，而少于k个参与者则不行 */ (补充) 基于中国剩余定理的门限方案 13.3 访问结构和一般的秘密共享 定义：在W 个参与者（记为集合P）中共享密钥K的方法称为是实现访问结构 的一个完善的秘密共享方案，如果满足以下两个条件： （1）对于一个授权的参与者子集 ，如果把他们的共享集中到一起，那么就可以确定密钥K的值。 （2）对于一个未授权的参与者子集 ，如果把他们的共享集中到一起，那么他们也不能确定关于K值的任何信息。 如果 且 ，则 ，我们称访问结构满足单调性（本章假设均为单调） 13.3 访问结构和一般的秘密共享 设 是一个访问结构，称 是一个最小授权子集，如果对于任何满足 和 的集合A 都有 。 的最小授权集合记为 ，称为 的基。 在（T,W）门限访问结构的情况中，基恰好是由所有T 个参与者的所有子集组成。 定义：子集 是最大的非授权子集， 如果对于所有的 ，都有 。 13.3.1 单调电路构造 设 我们得到布尔公式 算法：单调电路构造（C） 当存在线 使得 未定义时，循环以下操作： 找到C的一个门G使得 已经被定义，其中 是G的输出线，但是对于G的任意出入线来说， 都没定义过。 （1）如果G是一个“或”门，那么对于G的每一个输入线W， （2）否则，令G的输入线是 ，独立的选择 中的 个元素，记为 FOR DO