秘密分享 Secret Sharing

学习《How to Share a Secret》- Adi Shamir

原文学习

原文问题:

Eleven scientists working on a secret project. They wish to lock up the documents in a cabinet so that the cabinet can be opened if and only if six or more of the scientists are present. What is the smallest number of locks needed? What is the smallest number of keys to the locks each scientist must carry?

11个科学家一起在工作一个秘密的项目. 他们希望将工作文件所在一个橱柜里，这个橱柜只能被6个或者更多个数的科学家一起打开。那最少要多少把锁呢？每个科学家至少要带多少把钥匙呢？

基于上个问题, Shamir 提出了门限方案，以下是简单解释:

• 数字 D ，也是需要藏起来的 secret ，拆分为 i 份，记为D_i 。
• 选取最高项为 k-1 项的多项式, q(x)=a_0 + a_1x+ ... a_{k-1}x^{k-1}, 其中系数(coefficients) a_1,...a_{k-1} 也是随意选择，而让 a_0=D 。
• 随后D_i 的值就在这个多项式上取出，得到D_1 = q(1),..., D_i = q(i),...,D_n = q(n)) , 将D_i 分发给其他人。
• 只要知道 k 个D_i ，将能还原多项式 q(x) 的系数。
• 得到 q(x) 后，通过计算 q(0) = a_0 = D , 最后还原出 secret D。

​Shamir在论文中写到​

To make this claim more precise, we use modular arithmetic instead of real arithmetic

为了阐述更精确，我们用 模算数（modular arithmetic） 代替 实数算数 (real arithemtic)

在以前所学知识中会让我们对这个modular arithmetic 产生一些误解。小学的时候学的求余，我们会误认为余数没有负数。但事实上不是这样的，可以学习以下 mudular arithmetic，帮助理解密码学。

以下是基于 modular arithmetic 的过程：

• 需被分享的秘密整数记做 D , 分享给 n 个人，选取一个素数(prime) p , 选取的素数 p 需要满足大于 D 和 n 。
• 同样多项式的常数项 a_1,...,a_{k-1} 需要被随机选择，但是要满足 [0, p) 。
• 被分发的 D_1,...,D_n 通过取模计算出来, D_1 = q(1) mod p ，... D_n =q(n) mod p 。
• 只要知道 k 个D_n ，将能还原多项式 q(x)的系数。
• 得到 q(x) 后，通过计算 , 最后还原出 secret D。