《秘密共享方案》PPT课件.ppt

《《秘密共享方案》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《秘密共享方案》PPT课件.ppt（37页珍藏版）》请在金锄头文库上搜索。

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

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

3、少于K个人合作恢复秘密 又要防止对T个人的攻击而阻碍秘密的恢复当N 2T 1时K T N 1 2的取值最佳秘密分割应该由可信第三方执行 或者托管设备完成 4 13 1引言 13 1引言 秘密的分割假设是一个 K N 门限方案选取一个K 1次多项式F X A0 A1X AK 1XK 1该多项式有K个系数令A0 F 0 S 即把常数项指定为待分割的秘密其它K 1个系数可随机选取显然 对于该多项式 只要知道该多项式的K个互不相同的点的函数值F XI I 1 2 K 就可恢复F X 生成N个子秘密任取N个不同的点XI I 1 N 并计算函数值F XI I 1 N 则 XI F XI I 1 N 即为分

4、割的N个子秘密显然 这N个子秘密中的任意K个子秘密即可重构F X 从而可得秘密S 5 13 2SHAMIR门限方案 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个互不相同的点的函数值 XI I 1 2 K 可构造K 1次LAGRANGE插值多项式显然 如果将函数 X 就选定F X 则差值多项式刚好完全恢复了多项式 X F X 6 13 2

5、SHAMIR门限方案 根据上述的思想 在有限域GF Q 上实现上述方案 即可得到SHAMIR秘密分割门限方案 1 秘密的分割设GF Q 是一有限域 其中Q是一个大素数 满足Q N 1秘密S是在GF Q 0 上均匀选取的一个随机数 表示为S RGF Q 0 令S等于常系数A0其它K 1个系数A1 A2 AK 1的选取也满足AI RGF Q 0 I 1 K 1 在GF Q 上构造一个K 1次多项式F X A0 A1X AK 1XK 1N个参与者记为P1 P2 PN 其中PI分配到的子密钥为 I F I 7 13 2SHAMIR门限方案 2 秘密的恢复如果任意K个参与者PI1 PI2 PIK 1 I

6、1 I2 IK N 要想得到秘密S 可使用它们所拥有的K个子秘密 IL F IL L 1 K 构造如下的线性方程组A0 A1 I1 AK 1 I1 K 1 F I1 A0 A1 I2 AK 1 I2 K 1 F I2 A0 A1 IK AK 1 IK K 1 F IK 13 1 8 13 2SHAMIR门限方案 因为IL L 1 K 均不相同 所以可由LAGRANGE插值公式构造如下的多项式 F X 从而可得秘密S F 0 然而参与者仅需知道F X 的常数项F 0 而无需知道整个多项式F X 所以令X 0 仅需以下表达式就可以求出S S 可以预计算不需保密 9 方案的完善性分析如果K 1个参与

7、者想获得秘密S 他们可构造出由K 1个方程构成的线性方程组 其中有K个未知量对GF Q 中的任一值S0 可设F 0 S0 再加上上述的K 1个方程就可得到K个方程 并由LAGRANGE插值公式得出F X 因此对每一S0 GF Q 都有一个惟一的多项式满足13 1方程组所以已知K 1个子密钥得不到关于秘密S的任何信息 因此这个方案是完善的 10 13 2SHAMIR门限方案 例8 1 设门限K 3 份额数为N 5 模值Q 19 待分割的秘密S 11 随机选取A1 2 A2 7 可构造多项式F X 7X2 2X 11 MOD19将秘密分割成5份分别计算F 1 7 12 2 1 11 MOD19 1

8、F 2 7 22 2 2 11 MOD19 5F 3 7 32 2 3 11 MOD19 4F 4 7 42 2 4 11 MOD19 17F 5 7 52 2 5 11 MOD19 6得5个子密钥 11 13 2SHAMIR门限方案 13 2SHAMIR门限方案 秘密的恢复如果知道其中的3个子密钥 如F 2 5 F 3 4 F 5 6 就可重构F X 事实上我们可直接根据差值公式计算S F 0 12 13 2SHAMIR门限方案 简化的 T T 门限方案 D秘密的选取 独立随机选取 中的T 1个元素 记为 D计算 对于 D把共享的值发给 中国剩余定理 又称孙子定理设m1 m2 mk是k个两两

9、互素的正整数 m m1m2 mk Mi i 1 k 满足m miMi 则同余式组x b1 modm1 x b2 modm2 x bk modmk 有唯一解 x M 1M1b1 M 2M2b2 M kMkbk modm 其中M iMi 1modmi i 1 2 k 14 补充 基于中国剩余定理的门限方案 1 参数的选择设m1mnmn 1 mn k 2注意这里的条件m1mnmn 1 mn k 2表明最小的k个数的乘积也比最大的k 1个数的乘积大显然 m1 m2 mn中任意k个数的乘积都比m1m2 mk大 15 补充 基于中国剩余定理的门限方案 2 秘密的分割设s是待分割的秘密数据 令s满足mnmn

10、 1 mn k 2 s m1m2 mk即s比最大的k 1个数的成绩大 同时比最小的k个数的乘积小从而 对任意k个数的乘积T s smodT 模运算不起作用而任意k 1个数的乘积R有smodR在数值上不等于s 16 补充 基于中国剩余定理的门限方案 为了分发秘密 计算m m1m2 mn然后计算si s modmi i 1 2 n 以 si mi m 作为一个子秘密集合 si mi m i 1 n即构成了一个 k n 门限方案 17 补充 基于中国剩余定理的门限方案 秘密的恢复对任取的k个参与者 不失一般性 设这k个参与者为P1 Pk中 每个参与则Pi计算Mi m mi Ni Mi 1 modmi

11、 yi siMiNi结合起来根据中国剩余定理可求得s 由于任意k个或k个以上的模数相乘都比s大 它们恢复出来的s必然相同 而少于k个参与者则不行 18 补充 基于中国剩余定理的门限方案 13 3访问结构和一般的秘密共享 定义 在W个参与者 记为集合P 中共享密钥K的方法称为是实现访问结构的一个完善的秘密共享方案 如果满足以下两个条件 1 对于一个授权的参与者子集 如果把他们的共享集中到一起 那么就可以确定密钥K的值 2 对于一个未授权的参与者子集 如果把他们的共享集中到一起 那么他们也不能确定关于K值的任何信息 如果且 则 我们称访问结构满足单调性 本章假设均为单调 13 3访问结构和一般的秘

12、密共享 设是一个访问结构 称是一个最小授权子集 如果对于任何满足和的集合A都有 的最小授权集合记为 称为的基 在 T W 门限访问结构的情况中 基恰好是由所有T个参与者的所有子集组成 定义 子集是最大的非授权子集 如果对于所有的 都有 13 3 1单调电路构造 设我们得到布尔公式算法 单调电路构造 C 当存在线使得未定义时 循环以下操作 找到C的一个门G使得已经被定义 其中是G的输出线 但是对于G的任意出入线来说 都没定义过 1 如果G是一个 或 门 那么对于G的每一个输入线W 2 否则 令G的输入线是 独立的选择中的个元素 记为FORDO 例题A 非授权子集 13 3 1单调电路构造 变成合

13、取范式 例题B定理 设C是任意的单调布尔电路 则单调电路的构造可产生一个能够实现访问结构的完善秘密共享方案 略 13 3 1单调电路构造 非授权子集 假设是一个访问结构并且是分发规则的集合 我们称是一个实现访问结构的完善秘密共享方案 如果下面两个性质 对于任何的授权子集 不存在两个分发准则和 其中使得 即对于授权子集B中的参与者 共享的任何分发都可以确定密钥K的值 对于任何非授权子集和任何共享的分发 有下式成立对于任意 即对于非授权的子集B 给定共享的分发 K上的条件概率分布和K上的先验概率分布是相同的 换句话说 B的共享的分发没有提供关于K值的任何信息 13 3 2单调电路构造 正式定义 定

14、义 假设我们有一个实现访问结构的完善秘密共享方案 的信息率定义为比率 注意 表示所有可能收到的共享集合 当然 方案的信息率记为并定义为例题 因此例题 所以 我们更倾向于方案一 其信息率高些 13 4信息率和高效方案的构造 定理13 2 设C是任意的单调布尔电路 则存在一个实现访问结构的完善秘密共享方案 其信息率是其中是C中带有输入线的根数 可以看出 shamir门限方案的信息率是1 下面会证明这是一个最优值 相比之下 使用析取范式的布尔电路实现的 t w 门限方案的信息率是 当这是一个非常低的值 因此是不佳的 定理13 3 对于实现一个访问结构的任何完善的秘密共享方案 都有 13 4信息率和高

15、效方案的构造 设是一个访问结构 是上所有d元组组成的向量空间 假设存在函数满足性质话句话说 向量可以表示为中向量的线性组合当且仅当B是一个授权子集 对于给定的访问结构 只要我们找到满足该性质的向量的集合 那么就可以建立相应的秘密共享方案 这个方案被称为Brickell秘密共享方案 13 4 1向量空间构造 密码体制13 3Brickel秘密共享方案输入 满足上述性质的向量初始化阶段对于 D把向量给D 这些向量公开 共享分发假设D想要共享密钥K D定义 并且他秘密的选择中的d 1个元素对于 D计算 其中对于 D把的值作为共享分发给 13 4 1向量空间构造 定理13 4假设满足性质 则分法规则

16、的集合组成了一个实现访问结构的理想秘密共享方案 证明 首先 我们证明如果B是一个授权子集 那么B中参与者能够计算K 因为所以我们将其写成其中每个 的共享是 其中是由D选定的未知向量 并且 由内积运算的线性性 可得 13 4 1向量空间构造 如果B不是授权子集 假设对于某个 B假设 我们证明这样的猜测和她们所拥有的信息是一致的 我们用表示子空间的维数考虑方程组 这是一个含有个未知量的线性方程组 因为则这个方程组是相容的 系数矩阵的秩是 解空间的维数为 对任意的值这样在每个恰好有个分发规则 这和B共享的可能分发是一致的 有 13 4 1向量空间构造 详解参考例题13 8 定理13 5假设是一个完整的多划分图 则存在一个理想秘密共享方案实现了参与者V上的基为E上的访问结构 13 4 1向量空间构造 定义13 5设是一个访问结构 是分布规则的集合 则称是实现访问结构的一个完善的秘密共享方案 如果满足以下两个条件 对于任何参与者的授权子集 对于任何参与者的非授权子集 引理13 7假设设是一个访问结构 是实现的分发规则的集合 设 其中则引理13 8假设是一个访问结构 是实现的分发规则的集合 设其中