updated:

Shamir秘密共享协议

基于挂锁的门限

有这样的一条新闻，某小区业主使用66把锁串联锁住了小区大门，保证只有小区住户才能打开其中一把锁，打开大门。

这种将锁串联的操作实现了一种可以理解为“或”的逻辑。从另一种角度理解，这可以被看作一种门限方案，即小区的个业主中，只要有一位同意，即可开锁。

进一步的，通过将锁并联，我们可以构造出“与”逻辑，从而实现门限方案。

例如，当时，记参与的三方为，一个简单的方案如下（假设锁可以复制）： 

1
2
3
4
方案一：
A B
A C
B C
（其中横向表示串联，纵向表示并联） 可以看到，该方案需要6把锁，每一方需要1把钥匙。然而，我们还有另一种方案： 
1
2
3
4
方案二：
a
b
c
其中，携带钥匙，携带钥匙，携带钥匙。如此以来，我们只需要使用3把锁，但代价是每一方需要携带2把钥匙。

下面的证明可略过

假设锁不可复制，但是钥匙可以复制。我们接下来研究门限问题中需要的锁的最小数量以及每个参与者需要携带的钥匙数量。我们需要保证：

  • 必要性：对于任意的个参与者，总是存在至少一把无法打开的锁。
  • 充分性：任意的两组个参与者不能存在共同的无法打开的锁，否则这意味着我们可以找出个无法开门的参与者。

假设锁数量为，这些锁构成了一个集合。将第组个参与者不能打开的锁记为。从必要性条件我们有。从充分性条件知构成的一个划分，且。为了得到最小需要的锁的数量，取，因此最小为。

进一步的，对于一个参与者，我们从剩下的名参与者中挑出一组名参与者，从上述必要性条件知至少拥有一把他们没有的钥匙。同时由充分性条件知任意两组个参与者至少缺少两把钥匙。因此至少要有把钥匙。即每一位参与者所需要的最少的钥匙数量为。

在Shamir的论文中，他提到一个的门限方案需要至少462把锁，每个参与者需要携带252把钥匙，这是不切实际的。

拉格朗日插值

拉格朗日插值是Shamir秘密共享的核心。对于给定的个点，拉格朗日插值法能够计算出通过这些点的多项式。利用该方法给出的阶多项式形式如下：

直觉上来看，为了让该多项式在时取值为，我们需要保证

因此我们可以构造如下：

可以看到，当时，每一项都为，否则总有一项分子为，该构造满足上述要求。我们构造出的多项式被称为拉格朗日多项式。

可以证明，对于个点，我们可以构造出一个唯一的阶拉格朗日多项式。

Shamir协议

协议描述

Shamir对之前提到的门限方案给出了更严格的限制：假设要共享的秘密为，将分为份，该方案应当能保证

  • 可以从中的任意份数据简单的计算出
  • 即使持有中的任意小于份数据，也无法得知任何关于的信息

通过将上述拉格朗日插值的过程倒转过来，我们很容易得到Shamir秘密共享的基本思想： 给定一个阶多项式

其中为要共享的秘密。计算，将分别分发给秘密共享的参与方，那么只要其中方合作，即可唯一确定该拉格朗日多项式，并可以简单地求出。

协议安全性证明

在实际应用中，该多项式可以被定义在素域上，其中多项式的每一个系数是从素域中随机选取的非零且不等元素。假设一位攻击者拥有部分数据，且

因此

注意上式中，只有黄色的部分不是常量。由于我们的操作在素域上进行，上式给出了一个和之间的一对一映射关系。因此通过这些数据生成的多项式共有个，且由它们得到秘密的可能性相等，攻击者无法获得任何关于的信息。

参考资料

  1. Shamir1979 - How to share a secret
  2. https://crypto.stackexchange.com/questions/64082/formal-proof-of-shamirs-secret-sharing-scheme-security
← Prev 属性加密入门 | A Graduate Course of Applied Cryptography - Solution Next →