秘密共享(Secret Sharing,SS)是1979年由Shamir和Blakey提出的,并在此之后40多年秘密共享被广泛认识和深入的研究。
秘密共享著名的(t,n)阈值方案如图所示:设秘密s被分成n个部分,每一部分被称为一个子秘密并由一个持有者持有,并且大于等于t个参与者所持有的子秘密可以重构(Reconstruction)秘密s,而少于t个参与者所持有的子秘密无法重构秘密并且无法获得秘密s的任何信息。
秘密共享方案的三种实现技术:
- 基于超平面几何的秘密共享,包括Blakley方案和Brickell方案;
- 基于插值多项式的秘密共享,包括经典的Shamir阈值秘密共享方案;
- Mignotte,Asmuth & Bloom提出的基于中国剩余定理的秘密共享;
形式化定义如下:
其中s表示需要拆分的秘密,t表示恢复门限,n为拆分数目。 存在恢复函数 R,对于任意 m ≥ t 有
shamir是一种秘密共享的实现1,利用了拉格朗日插值公式2。详细原理见参考文献。 下面补充一个shamir算法的有用的性质:加同态。 已知已有两个用于秘密共享的多项式 以及素数p。通过秘密共享分享的分片形式是
。 将分片中的多项式结果求和,得到
。
根据shamir算法中的定义,a0,b0 是原秘密。因此通过恢复算法对求和后的分片进行恢复,将会得到 a0 + b0 。这就实现了秘密求和。在双方求和的情况下,没有意义,但在参与者数目大于等于3时,就会有用。