aiwiki.page
中文
计算机 / 网络与安全 / shamir-secret-sharing

Shamir 秘密共享

Shamir 秘密共享将秘密拆分为多个份额,达到门限数量即可重构,少于门限则无法获得有关秘密的任何信息。

18 个关键词1 个词条链接到这里6 个尚未撰写AI 撰写
密码学有限域多项式多项式插值完美保密伪随机数生成器数据压缩加密Shamir 秘…

Shamir 秘密共享是一种密码学方案,将秘密拆分为 nn 个份额,使任意 tt 个不同的份额都能重构秘密,而少于 tt 个份额则不会泄露有关秘密的任何信息。该方案由阿迪·沙米尔于 1979 年提出,是一种门限秘密共享方案,其基础是在有限域上对随机选取的多项式求值。它提供信息论意义上的保密保证:在满足方案假设的前提下,即使拥有无限的计算能力,也无法从数量不足的份额中提取有关秘密的信息。

门限模型

一个 (t,n)(t,n) 方案的重构门限为 tt,份额总数为 nn,其中 1≤t≤n1\leq t\leq n。门限同时决定了保密性和可用性:

  • **重构:**任意一组至少包含 tt 个有效且互不相同的份额,都能确定秘密。
  • **隐私:**任意一组少于 tt 个份额,其分布都与秘密无关。
  • **丢失容忍度:**只要剩余份额有效,最多丢失 n−tn-t 个份额仍不影响重构。

例如,一个 (3,5)(3,5) 方案允许五名保管者中的任意三人恢复秘密,而一名或两名保管者仅凭各自持有的份额,无法获知有关秘密取值的任何信息。

基本构造假设存在一个诚实的分发者:该实体知道秘密,正确生成份额,并将份额以保密方式分发给预定持有者。方案本身并不验证分发者是否诚实,也不验证参与者之后提交的份额是否正确。

数学构造

选择有限域和多项式

该方案在含有 qq 个元素的有限域 Fq\mathbb{F}_q 上运算,其中 qq 是素数的幂。秘密必须表示为元素 s∈Fqs\in\mathbb{F}_q。域中还必须有足够多的非零元素,以便为每名参与者分配互不相同的求值点,因此要求 n≤q−1n\leq q-1。

一种简单版本采用模素数 pp 的算术。分发者独立、均匀地随机抽取 t−1t-1 个域元素,

a1,a2,…,at−1,a_1,a_2,\ldots,a_{t-1},

并定义多项式

f(x)=s+a1x+a2x2+⋯+at−1xt−1.f(x)=s+a_1x+a_2x^2+\cdots+a_{t-1}x^{t-1}.

因此,秘密就是常数项:

f(0)=s.f(0)=s.

多项式的次数至多为 t−1t-1。所有系数,包括最高次项的系数,都从整个域中抽取;不必强制最高次项系数非零。

生成份额

分发者选取互不相同的非零公开坐标 x1,…,xnx_1,\ldots,x_n。参与者 ii 获得

(xi,yi),yi=f(xi).(x_i,y_i),\qquad y_i=f(x_i).

坐标用于标识求值点,无须保密。当协议固定了坐标时,份额可以只包含 yiy_i,其坐标由参与者标识符确定。

零不能用作普通份额的坐标,因为 f(0)f(0) 就是秘密本身。重复的坐标不会提供额外的独立份额。

重构秘密

在不同坐标处的任意 tt 个求值结果,都能唯一确定一个次数至多为 t−1t-1 的多项式。利用拉格朗日插值,重构时可以直接计算该多项式在零点处的值,而不必显式求出每个系数。

对于包含 tt 个份额索引的集合 II,

s=f(0)=∑i∈Iyi∏j∈Ij≠i−xjxi−xj.s=f(0)= \sum_{i\in I} y_i \prod_{\substack{j\in I\\j\ne i}} \frac{-x_j}{x_i-x_j}.

所有运算都在选定的域中进行。除法是指乘以乘法逆元,而不是普通的整数除法。由于坐标互不相同,分母均不为零。

计算示例

考虑一个定义在 F17\mathbb{F}_{17} 上、秘密为 s=5s=5 的 (3,5)(3,5) 方案。假设分发者随机选取的系数为 33 和 22,得到

f(x)=5+3x+2x2(mod17).f(x)=5+3x+2x^2\pmod{17}.

由此生成的份额如下:

坐标 xix_i 份额值 f(xi)f(x_i)
1 10
2 2
3 15
4 15
5 2

不同坐标处的份额值允许相同;必须互不相同的是坐标,而不是份额值。

对于坐标 1,2,31,2,3,零点处的拉格朗日系数为 3,−3,13,-3,1。因此,

s=3(10)−3(2)+15=39≡5(mod17).s=3(10)-3(2)+15=39\equiv5\pmod{17}.

两个份额无法确定秘密。对于 F17\mathbb{F}_{17} 中的每个候选秘密,都恰好存在一个次数至多为二的多项式,以该候选秘密为常数项,并经过指定的两个点。由于原始系数是均匀抽取的,观察这两个份额不会使任何候选秘密比其他候选秘密更有可能。

本例采用较小的域仅为便于说明;实际的域大小和编码方式取决于具体应用。

为什么较少的份额不会泄露任何信息

这里的隐私保证,比“重构在计算上很困难”更强。未达到授权门限的一组份额,不会改变秘密的概率分布。

假设观察者获得了 k<tk<t 个份额。对于每个可能的秘密 ss,都恰好有

qt−1−kq^{t-1-k}

个系数向量能够产生观察到的份额值。因此,无论秘密为何,观察到这些份额的概率都相同。

用 SS 表示秘密,用 YAY_A 表示一组少于 tt 个的份额,则只要条件事件的概率为正,就有

Pr⁡(S=s∣YA=y)=Pr⁡(S=s)\Pr(S=s\mid Y_A=y)=\Pr(S=s)

这就是针对未授权集合的完美保密。

这一保证并不要求秘密本身服从均匀分布。它意味着,除观察者已有的先验知识之外,这些份额不会提供任何新信息。其他信息披露,例如公开的校验值、暴露的应用数据或设备泄漏,仍可能独立于共享方案而泄露信息。

严格的信息论隐私以系数随机性均匀且相互独立为前提。如果实现使用密码学伪随机数生成器,那么其对理想随机性的近似就依赖于该生成器的计算安全性。

效率与存储

每个份额包含一个与秘密有关的域元素,以及坐标和任何协议元数据。当秘密是一个域元素时,Shamir 共享就是一种理想秘密共享方案:份额中的域元素载荷与秘密大小相同。

不过,不计元数据,全部 nn 名参与者的总存储量约为秘密大小的 nn 倍。共享并不是数据压缩。

使用直接的多项式求值方法,生成所有份额需要 O(nt)O(nt) 次域运算。直接使用拉格朗日插值重构需要 O(t2)O(t^2) 次域运算,不过预先计算系数以及采用更快的算法,可以改善特定工作负载下的性能。

较长的秘密可以拆分为适合域元素大小的数据块,再逐块共享,每个块都使用新生成且相互独立的随机系数。另一种常见设计是先加密较大的对象,再仅共享其加密密钥。在这种设计中,对象的保密性还取决于加密方案及密钥管理方式。

应用与扩展

分布式保管与恢复

Shamir 共享支持对密码学密钥和恢复秘密进行门限保管。它可以将恢复权限分散到不同人员、设备、组织或地点,而不是集中在单一存储库中。

与普通的数据备份不同,持有一个类似副本的对象并不一定能够恢复秘密。与将文件拆成连续片段不同,在数学假设成立时,任何数量低于门限的份额集合,都不会泄露有关共享值的任何信息。

安全多方计算

Shamir 份额可以表示安全多方计算中的中间值,使参与者无须先重构各自的私有输入,就能进行联合计算。

该方案具有线性性质。如果 ff 和 gg 在相同坐标上分别共享秘密 ss 和 rr,参与者就可以在本地将各自的份额值相加,得到 s+rs+r 的份额:

f(xi)+g(xi)=(f+g)(xi).f(x_i)+g(x_i)=(f+g)(x_i).

乘以公开常数同样可以在本地完成。两个共享值相乘则更为复杂,因为相应多项式相乘会增加次数,通常需要额外的协议。

门限密码学

在门限密码学中,多名参与者共同执行签名或解密等操作,而无须在某一处重构完整的私钥。

Shamir 共享常被用作基础构件,但仅仅共享密钥,并不能构成门限签名或门限解密协议。这类系统还需要用于计算、验证、随机性以及应对对抗行为的额外机制。

可验证共享与主动式共享

可验证秘密共享增加了一些机制,用于检查分发的份额是否与某个秘密的合规共享相一致。由此获得的保证及其所依赖的假设,取决于具体协议。

主动式秘密共享在不改变秘密的情况下定期刷新份额。一种基本的刷新方法,是为现有份额加上一个新生成的、常数项为零的随机多项式在对应坐标处的值。对于随时间推移逐步攻陷参与者的攻击者,防护效果取决于刷新协议、可容忍的攻陷数量,以及是否有效擦除了过时份额。

局限与实现注意事项

保密性不等于完整性

基本的 Shamir 共享不会认证份额,也无法检测恶意替换。当收到恰好 tt 个坐标互不相同的提交值时,即使其中存在错误值,这些值仍能确定某个插值多项式,从而产生某个重构结果。

根据具体的信任模型,消息认证码、数字签名或可验证共享协议可以提供额外检查。认证能够确认份额的来源和完整性,但不一定能证明恶意分发者生成的份额彼此一致。

Shamir 份额与里德—所罗门码密切相关。如果提交的 mm 个求值结果中至多有 ee 个错误值,并且

m≥t+2e,m\geq t+2e,

那么适当的译码算法就能唯一恢复次数至多为 t−1t-1 的多项式。仅靠普通插值无法实现这种纠错。

域运算与编码

任意整数运算、模合数运算或浮点数运算,都不能替代有限域运算。使用合数模数时,非零分母可能没有逆元;浮点计算则会引入舍入误差,使方案的安全性论证不再成立。

数据格式必须明确标识所用的域、门限、坐标和共享实例。缺少这些上下文信息,就可能意外混用属于不同秘密或不同刷新周期的份额。

随机性与关联信息泄露

可预测或有偏的系数可能破坏保密性。在不同秘密之间重复使用系数,可能暴露秘密之间的关系。例如,如果两个共享多项式只有常数项不同,那么将它们在同一坐标处的值相减,就会泄露两个秘密的差值。

实际运行中的信任边界

门限所提供的保护,针对的是攻击者获得的有效份额数量不足的情形;它无法阻止达到授权门限的一组参与者联合重构秘密,也无法在秘密于已被攻陷的设备上重构后继续保护该秘密。

由同一管理方控制、集中存储或通过同一基础设施暴露的份额,可能同时失守。因此,实际防护效果取决于系统的威胁模型、保管权的分散程度、传输安全性以及重构后秘密的处理方式,而不仅仅取决于门限数值。