Shamir’s Secret Sharing

Shamir’s Secret Sharing 方案是一种重要的加密算法，它允许私人信息 secret (机密)在一个不受信任的网络中安全地分发。

secret sharing

在密码学中，secret sharing 是一种安全地分发重要私人信息片段给分布式网络或群体的方法，这使得此类方案特别适用于保护高度敏感的信息，如私有加密密钥或生物识别数据。

secret sharing 通过将私人信息分割成更小的部分 shares，然后在群组或网络中分发这些 shares 来实现。
每个单独的 share 本身是无用的，但是获取所有的 shares 可以重建原始的 secret。

在大多数方案中，实施了一个额外的加密层，以确保额外的隐私和安全，允许在 secret 所有者不知道的网络或团体中分发 shares。
例如，每个 share 分配者只有一个看起来随机的数(share)：
19_____, _5____, __3___, ___18__, ____5_,_____20
通过加密，当获取到所有的 shares (例如上述的数字)，仍然需要解密密钥来得到原始的 secret (例如上述中表示其对应字母表中顺序)。这一重要步骤可以保护私人信息免受有组织的攻击，即使每个 shareholder 都勾结起来重新创建原始秘密，他们也无法了解该秘密的任何信息，因为原始秘密已经加密。

Shamir’s Scheme

问题：分发的 shares 可能丢失或被泄漏。 shareholder 可能不在线，或者丢失自己的 share 或者被窃取；此外 shareholder 可能称为敌对方。如果要使用所有的 share 来重构 secret 可能会变得不实际和低效。

Shamir’s Secret Sharing 是以色列密码学家 Adi Shamir 1979 年首次提出的算法。它允许信息被分成多份 (shares)，只需要一部分 shares 就可以重建原始 secret。需要的最小数量称为阈值。

原理

SSS(Shamir’s Secret Sharing) 依赖多项式插值，构造一个 $L$ 次多项式函数 $f(x)$ 将 secret s 分成 $n$ 个 share，使得：

• $f(0)=s$
• $\textbf{share}_{1}= f(1),\textbf{share}_{2}= f(2),\cdots,\textbf{share}_{n}= f(n)$
  其中：
• 任何 $\le L$ 数量的 shares 组合不能了解到 secret s 任何信息
• 任何 $> L$ 数量的 shares 可以得到完整的 secret s

解码

使用 Lagrange interpolation，例如使用 3 次多项式，获得了 $f(5)=3,f(7)=2,f(12)=6,f(30)=15$ 可以构造原多项式：

secret 就是计算 f(0)

当然，有限域中也是成立的，表达式中的除法改用元素的逆元计算

隐私保护

Shamir’s Secret Sharing 使互不相识的多方有可能存储私人信息。因为 Shamir 方案在信息理论上是安全的，即使是拥有无限计算能力的攻击者，如果没有足够的 share 来满足阈值(最低份 share)，也无法破解解密的 share 来访问数据。

该方案可以扩展为，对 secret 的 share 执行计算并且将组合起来得到 secret 的计算的结果(同态计算)，而不需要将 secret 先解密出来。
当与其他加密技术相结合时，如安全多方计算和零知识密码学，SSS 提供了一个额外的安全层，使数据共享和存储安全、私密，并能抵御意外的数据丢失和外部攻击。

链接

• https://web.mit.edu/6.857/OldStuff/Fall03/ref/Shamir-HowToShareASecret.pdf
• Simple introduction to Shamir's Secret Sharing and Lagrange interpolation

• Basics of Secure Multiparty Computation
• Finite Fields in Cryptography | Introduction to GF