[3th of series ABE] Shamir‘s Secret Sharing
Abstract
This blog is going to discuss Shamir’s Secret Sharing Scheme.
1. Polynomial Interpolation
设给定n个互不相同的节点P_1, P_2, \dots, P_n（其中每个P_i = (x_i, y_i)且x_i \neq x_j当i≠j）），寻求通过这些点的最大次数多项式的函数形式。
给定平面上任意两个不同点(x_1, y_1)和(x_2, y_2)，能够唯一确定一个线性方程y = ax + b。
给定平面上任意三个不同的点(x_1, y_1)、(x_2, y_2)和(x_3, y_3)（其中x_1 \neq x_2 \neq x_3），它们可以唯一地决定一个关于x的二次多项式y = ax^2 + bx + c）。
以此类推，
在平面内任取n个互不相同的点必可唯一确定一个关于x的多项式其其次数为n−1
2. Shamir’s Secret Sharing
2.1. Definition
该算法属于密码学领域中的一种秘密共享机制，在其中一个秘密被划分为多个部分以便分发给不同参与者。每个参与者只持有自己独特的部分信息而不了解其余任何部分的内容。为了恢复原始秘密至少需要一定数量的部分信息而这些信息必须由指定数量的参与者共同提供。在阈值方案中这个最低数量少于所有参与者的总数因此当参与者的数量不足时则无法恢复原始信息
Suppose that our secret is 1234.
Aim is to partition the secret into 6 parts (n=6), where any subset of 3 parts being sufficient allows reconstruction of the secret. This indicates that three nodes are capable of uniquely determining a polynomial function with a maximum degree of two. Importantly, higher-degree polynomial functions cannot be uniquely determined by three nodes alone.
Initially, we assume that two random parts have been generated: 166 and 94. Let us specify that a₀ = 1234; a₁ = 166; and a₂ = 94, with the understanding that a₀ represents the secret value. Once this secret value (i.e., a₀ = 1234) has been determined, the remaining coefficients of the third-degree polynomial are randomly generated. The rest of the coefficients for the second-degree polynomial are specifically assigned random values of 166 and 94. As such, we can easily construct an equation of second degree that meets our design requirements. In this manner, we obtained an expression for the target second-degree polynomial function.
构建出目标多项式后可知，在有限域上任意选取三个点即可唯一确定该二阶多项式函数。基于构建的目标二阶多项式模型f(x)=1234+166x+94x²的基础上，在域内随机选取六个不同的点进行计算（其中我们生成了六个不同的点），其中我们生成了六个不同的点（x=1到x=6），这些点满足：仅需任意三个不同点即可还原该函数所对应的秘密值secret。具体计算结果如下：
f(1)=1494, f(2)=1942, f(3)=2578, f(4)=3402, f(5)=4414, f(6)=5614.
// 给定任意三个节点恢复出原始多项式的具体操作上，我们采用[拉格朗日插值法/范德蒙特插值法]()
令
(x0, y0) = (2, 1942)
(x1, y1) = (4, 3402)
(x2, y3) = (5, 4414)
通过插值法，最终可以恢复出唯一的2阶多项式函数，
f(x)=1234+166x+94x^2
通过目标多项式函数的确定，得到secret.2.2. Security Analysis
Shamir's Secret Sharing遵循(k, n)门限方案的安全机制。其核心在于构建n组数据对，在任何情况下只要有任意k组数据对即可重建目标k-1阶多项式函数以获取密钥。
安全性一：(k, n)阈值的安全性表示从n组节点中选择任意k组即可实现敏感数据的权限获取。
安全性一的分析是显然的，这里不作讨论。
**安全性二：**基于(k−1,n)阈值的安全机制表明，在未收集到至少k个节点对的数据时无法推导出敏感信息。
本研究重点分析了安全策略二的相关特性。例如，在获取n个节点对时，采用k-1对的方式是否会影响整体的安全性？
如果n个节点对(x, y)以及k-1阶多项式函数y=f(x)都采用非负整数的形式表示，在k-1阶多项式非负的前提下。假设已知k-1个节点对，则f(x)中各系数所构成的解空间必然受到影响——这意味着安全性将会降低——这是一个显而易见的问题。问题是：解空间平均减少了约多少？安全性平均降低了约多少？我们可以说：只要已知k-1个节点对，则可以在线性时间内求得第k个节点对——这表明：如果攻击者能够获取到k-1个节点对，则其攻击的成本将为线性时间复杂度O(n)——这种情况下攻击是极其致命的
结论：(x, y)节点和目标多项式之间光滑确定的关系容易导致安全问题。
该方案基于模糊逻辑学原理，在数据处理过程中通过采用Galois域理论的应用来规避潜在漏洞。具体而言，在该k-1阶多项式方程中，所有可能的(x, y)组合都是其有效解。值得注意的是，在恢复最终节点信息的过程中，攻击者必须进行2^n次独立测试以确保准确结果。
在Galois Field中，在第一个节点集合上构建了一个次数为n-1的多项式f_1；而在第二个节点集合上生成了一个次数同样为n-1的多项式f_2。那么f_1与f_2各自是否唯一呢？换句话说，在什么情况下可能会出现两个不同的节点集合生成相同的多项式呢？为了进一步分析这一现象，请设计相应的实验并尝试从理论角度寻找支持这一结论的依据。
Reference
- Shamir's Secret Sharing Link