Shamir 秘密共享

基本思想：

一元 k 次多项式函数

只要有 k+1 个点，就可以求出来整个函数

门限秘密共享方案

定义

秘密 s 通过某种方式被分成 n 个部分，每个部分称为份额(share)， 每个份额由一个参与者持有，使得：

• 由 t 个或多于 t 个参与者所持有的份额可重构秘密 s;
• 由少于 t 个参与者所持有的份额则无法重构秘密 s;

称该方案为(t,n)门限秘密共享方案， t 称为门限值。少于 t 个参与者所持有的份额得不到关于秘密 s 的任何信息则 称该方案是完善的。

应用

• 导弹的发射控制
• 银行或政府机要库门的开启
• 核设施启动

Shamir 门限方案

eg. 复旦树洞https://github.com/treehollow/treehollow-v3-encryption-doc

二维空间

多项式函数：然后拿拉格朗日差值就可以求出秘密

构造思路

• 设 GF(q) 为大素数 q 生成的有限域，其中$q \ge n+1$。
• 秘密 s 是 GF(q)/{0}上均匀选取的随机数。
• 在 GF(q)上构建一个(t-1)次多项式 $f(x) = a_{t-1}x^{t-1}+ ...+a_1x_1+a_0$，其中 $a_0 = s, a_i \in GF(q)/\{0\}$。
• n 个参与者中第 i 个参与者的份额为 f (i) 。
• 任意$t$个参与者想要得到秘密 s，可使用利用 Lagrange 插值公式：$f(x) = \sum_{i=1}^n y_i \prod_{j=1,\\j\neq i}^n \frac{x-x_j}{x_i-x_j}\mod q$

例题

26-11/(6-1)=3

(26-19)/2=7/2

23-19/1=4

AB: 3

BD: 3

AD: 3

y=3x+8

c 错

密码是8

测试会有一道这个题

找错的人，然后求秘密

Blakley 方案

t 维空间

t 维空间多个平面，交点与秘密 s

可以构造 t 元 1 次方程

如果有人用了假的份额，求出来的秘密就会出错，

对称加密的东西加进来，就可以解决这个问题

恢复出来的

si，ci 发给每一个人

密码重构阶段，验证是否存在假的秘密