在前面的一篇文章《保护委托人隐私的社交密钥恢复》中,介绍了一种基于智能合约的密钥恢复策略以及PoC实现。这是一种链上(Onchain)的方案,巧妙的解决了密钥丢失的问题,对提高区块链的安全性和可用性有着重要的意义。 实际上,关于如何提供冗余的抗风险密钥管理方案,在密码学中有相当长的研究历史,最早可以追溯到1979年Shamir(RSA发明人之一)的著名论文《如何分享秘密》,而其中使用的技术更可以追溯到18世纪的多项式插值(polynomial interpolation)。在Shamir之后,密钥分享的研究有个长足的发展,现在是包括云端密码管理、加密货币托管钱包等应用的核心组件之一。本文以“如何分享秘密”主题的系列第一篇,文中涉及的工程实践代码放在bitrocks/verifiable-secret-sharing中,欢迎star。

Shamir密钥分享基本原理

Shamir密钥分享(Shamir’s Secret Sharing,SSS)要解决的问题,可以用一个例子来讲述:

自从阿里巴巴和四十大盗的故事流传出来后,后世的强盗们考虑加强藏宝洞的安保措施,他们找到了一家安保公司,提出这样一个要求:n个强盗每人都有一把钥匙,任意k个强盗聚在一起都可以打开藏宝洞的锁,k-1或更少的钥匙都无法开启。

这个要求其实很巧妙,n个人最坏情况即使丢失了n-k把钥匙,依旧能够打开锁;而少于k个人聚在一起或者密钥被窃取,也不会造成财产损失。它既能提供冗余性,也能防共谋。

Shamir给出的著名方案是这样的:

形如 的k-1次多项式函数,将要分享的秘密(secret)编码为常数项a0。

  1. 分割密钥(split):随机生成a1到ak-1的系数值。在这条k-1次曲线上,任意取n个不同的点{(x1,y1),(x2,y2),…,(xn,yn)},将这些点分配给参与者,每个人拿到的都是一个密钥分片(secret share)。
  2. 恢复密钥(recover):k个人把密钥分片聚合在一起,即k个点代入原函数,确定一条唯一的曲线,即确定的{a0, a1, a2..}的值,其中的a0即是隐藏起来的秘密。而过任意k-1个点,在实数域理论上有无数条曲线,不会泄漏出关于a0的任何有用信息。

拉格朗日插值

由曲线上的点求原曲线的过程被叫做多项式插值,它有不同的方法,比如用高斯消去法解范德蒙矩阵,复杂度为O(k^3)。不过由于我们实际上只需要求出a0即可,而不是全部的系数,一种更快捷的方案是拉格朗日插值法,它能够直接根据给出的点坐标写出多项式的函数。

它的构造思路非常巧妙,值得写一篇数学小品,但不是本文的重点,感兴趣的同学可以阅读这份斯坦福大学的讲义

工程实践及注意事项

在实际实现中,需要注意: 多项式定义在有限域而不是实数域上或自然数域。 为什么这么选择呢?这个小问题留给读者去思考。

src/simple_sss.rs的实现为例,选择在素数域上。这样就涉及到有限域上的算术操作,如求乘法逆元。

SSS的缺点

如果在生产环境中去部署一套密钥分享服务时,我们发现,SSS方案存在诸多风险。我们将该服务中的角色分为dealer和众多的player,dealer负责密钥的分割和聚集恢复,而player作为密钥分片的持有人。 上图是一个阈值结构为2/3的Shamir密钥分享过程,任意两把密钥分片可以恢复出原密钥。可能存在以下风险:

  1. Dealer作恶,发送给三个Player的密钥分片并不能恢复出一致的密钥,如给Player1和Player2的分片是正常的,而Palyer3的分片是错误的;
  2. Player作恶,在恢复阶段发送的分片是错误的,这样恢复的密钥也是错误的;

这意味着使用平凡的Shamir密钥分享是不安全的。

Feldman的可验证密钥分享

可验证密钥分享(Verifiable Secret Sharing,VSS)要解决的就是上面的问题,最早由Chor, Goldwasser, Micali, Awerbuch提出,并给出一个基于大数分解难题的常数轮交互方案。

本文介绍的是现在较广泛应用的Feldman的方案,也是第一个非交互的可验证密钥分享。

基础原理及构造

FeldmanVSS方案基于离散对数问题,在SSS基础上增加了校验的过程。

  1. 分割密钥及生成承诺:分割密钥的过程和SSS类似,同时生成多项式系数的承诺,c(i) = g^a(i),g为循环群的生成元(generator),原理和椭圆曲线上由私钥导出公钥类似,commits = {c1,c2,..,ck}公开广播出去。将share(i) = (xi,yi)分别发送给Player。
  2. 验证分片:收到分片和承诺后,每个Player可执行下面的计算: ,正常情况下,Palyer在不知道多项式系数的情形下可以验证该等式左右两边成立,满足加法同态;如果Dealer作恶,则收到错误分片的Player本地将无法通过这个测试,这由离散对数问题的困难性质保证。
  3. 恢复密钥及验证正确性:恢复密钥的过程和SSS类似,Dealer计算出a0后还需要验证 c0 = g^a0是否成立,避免Player发送错误的分片导致恢复出错误的密钥。

采用FeldmanVSS后的2/3密钥分享流程如下图所示。

工程实践及注意事项

在工程实践中,可选择基于椭圆曲线的有限域,计算承诺。以src/feldman_vss.rs实现为例,采用了Secp256k1。需要注意,多项式的系数和取的x值都要转换成Scalar计算。

应用

FeldmanVSS是SSS的一个非常不错的改进,在实际生产中有着广泛的应用:

  1. 可以直接用于云服务和区块链托管钱包的密钥管理;
  2. 用于模拟一个同步广播网络,Dealer只有在k个Players的信息全部收集到的时候才可以揭露出隐藏的秘密,用在诸如秘密竞标、选举等场景;
  3. 可以用于构造快速的拜占庭容错协议,或者其他容错的协议;