Shamir 秘密共享是一种密码学方案,将秘密拆分为 个份额,使任意 个不同的份额都能重构秘密,而少于 个份额则不会泄露有关秘密的任何信息。该方案由阿迪·沙米尔于 1979 年提出,是一种门限秘密共享方案,其基础是在有限域上对随机选取的多项式求值。它提供信息论意义上的保密保证:在满足方案假设的前提下,即使拥有无限的计算能力,也无法从数量不足的份额中提取有关秘密的信息。
门限模型
一个 方案的重构门限为 ,份额总数为 ,其中 。门限同时决定了保密性和可用性:
- **重构:**任意一组至少包含 个有效且互不相同的份额,都能确定秘密。
- **隐私:**任意一组少于 个份额,其分布都与秘密无关。
- **丢失容忍度:**只要剩余份额有效,最多丢失 个份额仍不影响重构。
例如,一个 方案允许五名保管者中的任意三人恢复秘密,而一名或两名保管者仅凭各自持有的份额,无法获知有关秘密取值的任何信息。
基本构造假设存在一个诚实的分发者:该实体知道秘密,正确生成份额,并将份额以保密方式分发给预定持有者。方案本身并不验证分发者是否诚实,也不验证参与者之后提交的份额是否正确。
数学构造
选择有限域和多项式
该方案在含有 个元素的有限域 上运算,其中 是素数的幂。秘密必须表示为元素 。域中还必须有足够多的非零元素,以便为每名参与者分配互不相同的求值点,因此要求 。
一种简单版本采用模素数 的算术。分发者独立、均匀地随机抽取 个域元素,
并定义多项式
因此,秘密就是常数项:
多项式的次数至多为 。所有系数,包括最高次项的系数,都从整个域中抽取;不必强制最高次项系数非零。
生成份额
分发者选取互不相同的非零公开坐标 。参与者 获得
坐标用于标识求值点,无须保密。当协议固定了坐标时,份额可以只包含 ,其坐标由参与者标识符确定。
零不能用作普通份额的坐标,因为 就是秘密本身。重复的坐标不会提供额外的独立份额。
重构秘密
在不同坐标处的任意 个求值结果,都能唯一确定一个次数至多为 的多项式。利用拉格朗日插值,重构时可以直接计算该多项式在零点处的值,而不必显式求出每个系数。
对于包含 个份额索引的集合 ,
所有运算都在选定的域中进行。除法是指乘以乘法逆元,而不是普通的整数除法。由于坐标互不相同,分母均不为零。
计算示例
考虑一个定义在 上、秘密为 的 方案。假设分发者随机选取的系数为 和 ,得到
由此生成的份额如下:
| 坐标 | 份额值 |
|---|---|
| 1 | 10 |
| 2 | 2 |
| 3 | 15 |
| 4 | 15 |
| 5 | 2 |
不同坐标处的份额值允许相同;必须互不相同的是坐标,而不是份额值。
对于坐标 ,零点处的拉格朗日系数为 。因此,
两个份额无法确定秘密。对于 中的每个候选秘密,都恰好存在一个次数至多为二的多项式,以该候选秘密为常数项,并经过指定的两个点。由于原始系数是均匀抽取的,观察这两个份额不会使任何候选秘密比其他候选秘密更有可能。
本例采用较小的域仅为便于说明;实际的域大小和编码方式取决于具体应用。
为什么较少的份额不会泄露任何信息
这里的隐私保证,比“重构在计算上很困难”更强。未达到授权门限的一组份额,不会改变秘密的概率分布。
假设观察者获得了 个份额。对于每个可能的秘密 ,都恰好有
个系数向量能够产生观察到的份额值。因此,无论秘密为何,观察到这些份额的概率都相同。
用 表示秘密,用 表示一组少于 个的份额,则只要条件事件的概率为正,就有
这就是针对未授权集合的完美保密。
这一保证并不要求秘密本身服从均匀分布。它意味着,除观察者已有的先验知识之外,这些份额不会提供任何新信息。其他信息披露,例如公开的校验值、暴露的应用数据或设备泄漏,仍可能独立于共享方案而泄露信息。
严格的信息论隐私以系数随机性均匀且相互独立为前提。如果实现使用密码学伪随机数生成器,那么其对理想随机性的近似就依赖于该生成器的计算安全性。
效率与存储
每个份额包含一个与秘密有关的域元素,以及坐标和任何协议元数据。当秘密是一个域元素时,Shamir 共享就是一种理想秘密共享方案:份额中的域元素载荷与秘密大小相同。
不过,不计元数据,全部 名参与者的总存储量约为秘密大小的 倍。共享并不是数据压缩。
使用直接的多项式求值方法,生成所有份额需要 次域运算。直接使用拉格朗日插值重构需要 次域运算,不过预先计算系数以及采用更快的算法,可以改善特定工作负载下的性能。
较长的秘密可以拆分为适合域元素大小的数据块,再逐块共享,每个块都使用新生成且相互独立的随机系数。另一种常见设计是先加密较大的对象,再仅共享其加密密钥。在这种设计中,对象的保密性还取决于加密方案及密钥管理方式。
应用与扩展
分布式保管与恢复
Shamir 共享支持对密码学密钥和恢复秘密进行门限保管。它可以将恢复权限分散到不同人员、设备、组织或地点,而不是集中在单一存储库中。
与普通的数据备份不同,持有一个类似副本的对象并不一定能够恢复秘密。与将文件拆成连续片段不同,在数学假设成立时,任何数量低于门限的份额集合,都不会泄露有关共享值的任何信息。
安全多方计算
Shamir 份额可以表示安全多方计算中的中间值,使参与者无须先重构各自的私有输入,就能进行联合计算。
该方案具有线性性质。如果 和 在相同坐标上分别共享秘密 和 ,参与者就可以在本地将各自的份额值相加,得到 的份额:
乘以公开常数同样可以在本地完成。两个共享值相乘则更为复杂,因为相应多项式相乘会增加次数,通常需要额外的协议。
门限密码学
在门限密码学中,多名参与者共同执行签名或解密等操作,而无须在某一处重构完整的私钥。
Shamir 共享常被用作基础构件,但仅仅共享密钥,并不能构成门限签名或门限解密协议。这类系统还需要用于计算、验证、随机性以及应对对抗行为的额外机制。
可验证共享与主动式共享
可验证秘密共享增加了一些机制,用于检查分发的份额是否与某个秘密的合规共享相一致。由此获得的保证及其所依赖的假设,取决于具体协议。
主动式秘密共享在不改变秘密的情况下定期刷新份额。一种基本的刷新方法,是为现有份额加上一个新生成的、常数项为零的随机多项式在对应坐标处的值。对于随时间推移逐步攻陷参与者的攻击者,防护效果取决于刷新协议、可容忍的攻陷数量,以及是否有效擦除了过时份额。
局限与实现注意事项
保密性不等于完整性
基本的 Shamir 共享不会认证份额,也无法检测恶意替换。当收到恰好 个坐标互不相同的提交值时,即使其中存在错误值,这些值仍能确定某个插值多项式,从而产生某个重构结果。
根据具体的信任模型,消息认证码、数字签名或可验证共享协议可以提供额外检查。认证能够确认份额的来源和完整性,但不一定能证明恶意分发者生成的份额彼此一致。
Shamir 份额与里德—所罗门码密切相关。如果提交的 个求值结果中至多有 个错误值,并且
那么适当的译码算法就能唯一恢复次数至多为 的多项式。仅靠普通插值无法实现这种纠错。
域运算与编码
任意整数运算、模合数运算或浮点数运算,都不能替代有限域运算。使用合数模数时,非零分母可能没有逆元;浮点计算则会引入舍入误差,使方案的安全性论证不再成立。
数据格式必须明确标识所用的域、门限、坐标和共享实例。缺少这些上下文信息,就可能意外混用属于不同秘密或不同刷新周期的份额。
随机性与关联信息泄露
可预测或有偏的系数可能破坏保密性。在不同秘密之间重复使用系数,可能暴露秘密之间的关系。例如,如果两个共享多项式只有常数项不同,那么将它们在同一坐标处的值相减,就会泄露两个秘密的差值。
实际运行中的信任边界
门限所提供的保护,针对的是攻击者获得的有效份额数量不足的情形;它无法阻止达到授权门限的一组参与者联合重构秘密,也无法在秘密于已被攻陷的设备上重构后继续保护该秘密。
由同一管理方控制、集中存储或通过同一基础设施暴露的份额,可能同时失守。因此,实际防护效果取决于系统的威胁模型、保管权的分散程度、传输安全性以及重构后秘密的处理方式,而不仅仅取决于门限数值。