，如果把他们的共享集中到一起，那么他们也
如果
且
，则
，我们称访问结构满足单调性（本章假设均为单调）
13.3 访问结构和一般的秘密共享
• 设 是一个访问结构，称
是一个最小授权子集，如果对于任何满足 A B 和
A B 的集合A 都有 A 。 的最小授权集合记为 0 ，称为 的基。
{C P : B C, B 0}
18/
13.3 访问结构和一般的秘密共享
• 定义：在W 个参与者（记为集合P）中共享密钥K的方法称为是实现访问结构 的一个完 善的秘密共享方案，如果满足以下两个条件：
• （1）对于一个授权的参与者子集 定密钥K的值。
，如果把他们的共享集中到一起，那么就可以确
• （2）对于一个未授权的参与者子集 不能确定关于K值的任何信息。
15/
(补充) 基于中国剩余定理的门限方案
2. 秘密的分割
设s是待分割的秘密数据，令s满足
mnmn-1…mn-k+2<s<m1m2…mk
即s比最大的k-1个数的成绩大，同时比最小的k个数 的乘积小
从而： 对任意k个数的乘积T，s＝s mod T，模运算不起作 用 而任意k-1个数的乘积R有s mod R在数值上不等于s
项式F(X)，所以令X＝0，仅需以下表达式就可以求出S：
• S= k j 1
k
f (ij )
l 1
il
il ij
(modq)
k
bj yij (modq)
j 1
l j
不需保密
）
，（ b j 可以预计算
9/
13.2 SHAMIR门限方案
• 方案的完善性分析 • 如果K-1个参与者想获得秘密S，他们可构造出由K-1个方 程构成的线性方程组，其中有K个未知量 • 对GF(Q)中的任一值S0，可设F(0)＝S0，再加上上述的K-1 个方程就可得到K个方程，并由LAGRANGE插值公式得出 F(X)。因此对每一S0GF(Q)都有一个惟一的多项式满足 13-1方程组 • 所以已知K-1个子密钥得不到关于秘密S的任何信息，因此 这个方案是完善的。
x=b1 (mod m1) x=b2 (mod m2) … x=bk (mod mk)
有唯一解：x=M1M1b1+M2M2b2+…+ MkMkbk (mod m)
其中MiMi=1 mod mi (i=1,2,…,k)
14/
(补充) 基于中国剩余定理的门限方案
1. 参数的选择
• 为了实现上述意义上的秘密共享，人们引入了门限方 案(THRESHOLD SCHEME)的一般概念
2/
13.1引言
• 秘密分割门限方案的定义 • 定义1 设秘密 S 被分成N个部分信息，每一部分信息称为一个
子密钥或影子(SHARE OR SHADOW)，由一个参与者持有，使 得：
• ① 由K个或多于K个参与者所持有的部分信息可重构S • ② 由少于K个参与者所持有的部分信息则无法重构S 则称这种方案为(K,N)－秘密分割门限方案，K称为方案的门限 值。 • 极端的情况下是(N,N) －秘密分割门限方案，此时用户必须
• 简化的（T , T）门限方案：
1.D 秘密的选取（独立随机选取） 中的 T-1 个元素，记
为
，
2.D计算
，
3.对于
，D 把共享 的值发给 。
(补充) 基于中国剩余定理的门限方案
中国剩余定理，又称孙子定理
设m1,m2, … , mk是k个两两互素的正整数，m=m1m2…mk, Mi(i=1,…,k)满足m=miMi，则同余式组
yG,1,..., yG,t1
t 1
yG,t f (WG ) yG,i mod m i 1
FOR i 1,...,t DO f (Wi ) yG,i
中的 t 1个元素，记为
13.3.1 单调电路构造
• 例题A 0 {{P1, P2, P4},{P1, P3, P4},{P2, P3}}
16/
(补充) 基于中国剩余定理的门限方案
为了分发秘密，计算m=m1m2…mn 然后计算 si=s(mod mi) (i=1,2,…,n) 以(si,mi,m)作为一个子秘密 集合{(si,mi,m)}i=1n即构成了一个(k,n)门限方案
17/
(补充) 基于中国剩余定理的门限方案
• 计算S= F(0)
(1)k1
k j 1
k
f (ij )
l 1
il i j il
(modq)
l j
(1)31( f (2) 3 5 ) f (3) 2 5 ) f (5) 2 3 ) mod19
23 25
32 35
52 53
11
12/
13.2 SHAMIR门限方案
在（T,W）门限访问结构的情况中，基恰好是由所有T 个参与者的所有子集组成。
• 定义：子集
是最大的非授权子集，
如果对于所有的 B1 B, B1 B ，都有 B1 。
13.3.1 单调电路构造
• 设 0 {{P1, P2 , P4},{P1, P3, P4},{P2 , P3}} 我们得到布尔公式 (P1 P2 P4 ) (P1 P3 P4 ) (P2 P3) • 算法：单调电路构造（C）
秘密的恢复
对任取的k个参与者，不失一般性，设这k个参与
者为P1…Pk中，每个参与则Pi计算
Mi＝m/mi，Ni＝Mi-1(mod mi)，yi=siMiNi
结合起来根据中国剩余定理可求得
k
k
s＝ yij (mod mij )
j乘都比s大，它们 恢复出来的s必然相同，而少于k个参与者则不行
• N个参与者记为P1,P2,…,PN，其中PI分配到的子密钥为（I, F(I)）
7/
13.2 SHAMIR门限方案
• (2) 秘密的恢复 • 如果任意K个参与者PI1,PI2,…,PIK (1I1<I2<…<IKN)要想得到秘密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）
f (Wout ) K
当存在线 使得 f (W ) 未定义时，循环以下操作： • 找到C的一个门G使得f (WG )已经被定义，其中 WG是G的输出线，但是对于G的任意出入线
来说，f (W ) 都没定义过。
（1）如果G是一个“或”门，那么对于G的每一个输入线W，f (W) f (WG )
（2）否则，令G的输入线是 W1,...Wt ，独立的选择
(P1 P2 P4 ) (P1 P3 P4 ) (P2 P3 )
非授权子集
{P1, P2},{P1, P3},{P1, P4},{P2, P4},{P3, P4}
K c1
K a1 a2
K b1 b2
( y11, y12 ) (a1,b1)
• LAGRANGE插值：
• 已知(X)在K个互不相同的点的函数值(XI)(I=1,2,…,K)，可构造K-1次
LAGRANGE插值多项式
f (x)
k
k
(xj )
j 1
l 1
x xl x j xl
l j
• 显然，如果将函数(X)就选定F(X)，则差值多项式刚好完全恢复了多 项式(X)＝ F(X)
5/
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)的插值函数，也称插值多项式
都到场才能恢复密钥
3/
13.1引言
• 如果一个参与者或一组未经授权的参与者在猜测秘密S时，并不 比局外人猜秘密时有优势，即
• ③由少于K个参与者所持有的部分秘密信息得不到秘密S的任何信息
则称这个方案是完善的，即(K, N)－秘密分割门限方案是完善 的
• 攻击者除了试图恢复秘密外，还可能从可靠性方面进行攻击， 如果他能阻止多于N-K个人参与秘密恢复，则用户的秘密就难 于恢复
6/
13.2 SHAMIR门限方案
• 根据上述的思想，在有限域GF(Q)上实现上述方案，即可得到 SHAMIR秘密分割门限方案
• （1）秘密的分割 • 设GF(Q)是一有限域，其中Q是一个大素数，满足QN＋1 • 秘密S是在GF(Q)\{0}上均匀选取的一个随机数，表示为 SRGF(Q)\{0} • 令S等于常系数A0 • 其它K-1个系数A1,A2,…,AK-1的选取也满足AIRGF(Q)\{0} (I=1,…,K-1) • 在GF(Q)上构造一个K-1次多项式F(X)＝A0+A1X+…+AK-1XK-1
10/
13.2 SHAMIR门限方案
• 【例8－1】设门限K=3，份额数为N=5，模值Q=19，待分割的
秘密S=11，随机选取A1=2，A2=7，可构造多项式
• F(X)=(7X2+2X+11) MOD 19
• 将秘密分割成5份
• 分别计算 F(1)=(7×12+2×1+11) MOD 19＝1
•
F(2)=(7×22+2×2+11) MOD 19＝5