分享而不把秘密交给每个人
秘密只有一份可能丢失;每人都有副本,任何一人便能泄露。门限方案处理另一个问题:分发份额,使足够大的群体能重构秘密,而较小群体不能从份额获得秘密的信息。
定义 8.1.1
(多项式门限方案)
令 为素数,并取整数 。在域 中运算;公开的参与者标识为 ,它们在该域中互异且非零。秘密 可以服从任何分布。与 独立地,从 中均匀且独立地选取系数 。定义
参与者 收到份额 。
多项式次数至多为 :最高次系数可以为零。所有运算都模 。
常见错误
(标识是域元素,不是整数)
条件 正是保证标识 模 互异且非零的原因。在 中,标识 与 是同一个域元素,所以这两个份额只是一个插值点;标识 则是被禁止的点 ,其份额就是 。
任意 份的重构
定理 8.1.2
(门限重构)
任意 个不同参与者的份额唯一确定 ,从而确定 。
证明
(由根数得唯一性,由 Lagrange 插值得存在性)
若两个次数至多为 的多项式在 个互异域元素处相同,它们的差有 个根,次数却至多为 ,故差必为零。存在性由 Lagrange 插值给出:对 的 ,其中 互异,
每个分母都非零,因而在域中可逆。代入 便得秘密。多于 个诚实份额必含这样的子集。
例题 8.1.3
( 上四人中的三人方案)
取 、、,并仅为示范取 、、。则 给出份额 。由前三份,在零处的 Lagrange 权重为 、 和 ,因此
这些具体系数只用来核对计算;实际分发者必须每次重新均匀抽取,而不能预先固定。
例题 8.1.4
(另一组三份与另一组权重)
由标识 的份额,在零处的权重为 、 和 ;三者之和为 ,正如能重现常数多项式的权重所必须的。于是
与唯一性的要求一致,得到同一个秘密。
常见错误
(Lagrange 权重属于特定的子集)
权重取决于所用的标识。把子集 的权重 套用到标识 的份额,得 ,而不是秘密 。每换一组份额,都要重新计算权重。
为什么较少份额不泄露信息
定理 8.1.5
(完全保密)
对任意固定的 个参与者标识及任意 ,以下固定秘密的试验给出 上均匀的份额值向量:令 ,并如上抽取系数。因此对 的任何先验分布,该向量都与 独立。
证明
(每个观测值对应同样多的系数向量)
时结论显然。对 ,固定候选秘密 及系数 的任意值。 个互异非零标识 处的方程唯一确定 。其系数矩阵 的行列式为
它非零。因此每个指定的份额向量恰好对应 个系数向量中的 个,在秘密固定为 的试验中概率为 。这些相同的固定秘密分布给出任何先验下的独立性。对概率为正的观测份额事件,由 Bayes 公式, 的先验分布保持不变;它不会使非均匀先验变成均匀。
证明透视
可能性不等于概率
只说每个候选秘密都与观测到的份额相容并不足够。关键一步是固定观测者看不到的 个系数,再解出其余 个:这把概率问题变成数等可能的系数向量,而对每个观测值和每个候选秘密,数目都是同一个 。系数均匀且独立这一假设正是在这里使用,把计数转成概率。标识互异且非零用于行列式非零:零标识给出零行,而它的份额就是秘密本身。由于份额分布是在 固定时计算的,论证无需对 的先验作任何假设便告闭合。
例题 8.1.6
(两份份额同样地符合每个秘密)
对例子中的两份 ,每个候选 恰与一个多项式 相容。由方程 与 得 ,从而 ,故模七下 、。例如 给出 ,而 给出原多项式。对每个固定的候选秘密,相应系数对被抽中的概率都是 ;观测者的后验仍取决于其先验。
反例模式
不能重用随机性
若两个秘密使用相同的非常数系数,同一参与者把两个份额值相减,便得到两个秘密之差。在 上取 ,并对秘密 与 重用 :参与者 持有 和 ,而 。虽然每次共享只见 份,却已泄露了差。单次共享的保证本身并不蕴含多次共享之间的保密性;重新独立抽取系数可避免这种重用泄露。份额还需要安全的分发与存储;这个构造本身不认证份额,也不能阻止恶意参与者提交假份额。
习题
快速检查
(在 上,取 、、 及 。求各份额,并由前两份重构秘密。)
解答 · 答案
份额为 。直线满足 (模十一)。
快速检查
(设 、,固定秘密 ,并如上抽取系数。两个固定参与者标识处出现任一指定份额值对的概率是多少?)
解答 · 答案
由计数证明,对每个秘密都是 。
快速检查
(为什么禁止标识 ?为什么标识必须互异?)
解答 · 答案
标识 的份额直接等于 。重复的标识不能提供互异插值点,也违反行列式论证。
快速检查
(看到少于 份份额,会不会使对 严重偏斜的先验变得均匀?请解释。)
解答 · 答案
不会。份额向量与 独立,所以只要观测事件的概率为正,后验就等于先验。
延伸阅读
Adi Shamir, “How to Share a Secret” (1979) 提出多项式门限构造。