密码学原语如何应用？走近门限密码算法

来源：微众银行区块链作者：李昊轩

隐私数据密文控制权只能由单一主体掌控？代表控制权的密钥如何才能安全地交由多个互不信任的主体协同使用？如何在技术层面保障多方授权的公平公正性？任一参与协作的主体密钥丢失，如何实现安全可靠的容灾恢复？

在业务方案设计中，安全可控地让多个隐私主体参与数据协作，是隐私保护技术创造新兴商业价值的关键之一。在这一过程中，代表控制权的密钥由哪一方来掌握，是影响参与者合作意愿的重要因素。

因为哪一方拥有了密钥，相当于哪一方就获得了控制权，未能掌控密钥的另一方，则可能在合作关系中处于弱势。这将成为实现公平对等多方协作关系的一个关键阻碍。

以多方决策为例，上市公司的一次董事会会议中，需要多数董事对决策项进行签字才能生效。出于某些影响，会议无法面对面举行，所有董事必须使用数字签名来远程完成这一个签字过程。为了保证决议过程的机密性和公正性，每位董事不希望其他董事知晓自己的选择，同时要让股东团体对最后的决策结果，即聚合后的签名，进行验证。

这个过程中，存在三个隐私保护相关的主要功能点：

每位董事的签名控制权须由自己控制，而不是由中心化的可信第三方来代理行使权力。

代表决策结果的聚合签名只需多数董事同意，便可生成合法的声明。

股东团体需要对聚合后的签名进行验证，但无需知道具体哪些董事对此进行了签名。

以上功能点涉及在多方协作过程中，如何将原本单个的密钥安全地打碎成多个密钥分片，并让每个主体独立使用自己的密钥分片，合作完成所需的密码学协议过程。解决这一问题的关键，就在于门限密码算法的巧妙构造。

门限密码算法在多方协作的相关场景中应用十分广泛，可以实现数据联合授权、认证、密钥安全恢复、密钥安全交换等需求，在诸多分布式多方计算协议中均可见其身影。

本文主要从秘密分享、门限加密、门限签名三大应用方向，分享门限密码算法的奇妙之处。

01
秘密分享

1979年，Adi Shamir和George Blakley各自独立地提出秘密分享（Secret Sharing）的概念，奠定了门限密码学体系的基础。

具体而言，秘密分享是指一种安全地在多个参与者之间分享秘密的方式，其满足以下特性：

每个参与者都独立持有一部分关于秘密S的分片，只有将足够数目的分片组合起来，才能够重新恢复出秘密S。
当获得的分片数量不足时，无论采用何种组合策略，不会泄露关于秘密S的任何信息。

秘密分享在学术上的价值在于，提供了一种技术手段，将原本单一的密钥，以密钥分片的形式，安全地、平等地分配到多个参与者手中，除此之外，还实现了以下额外的安全特性：

容错高可用：不会因为少量密钥分片损坏和丢失，而导致密钥不可用。
抗侧信道攻击：原本固定的密钥，在密码学算法工程实现的执行过程中，可能会泄露一部分密钥的信息（参见第5论中的灰盒安全模型），但进行分片之后，成功实施此类攻击的难度将指数上升。

对于业务应用而言，主要使用的特性是密钥安全平等分配和容错高可用，可以用来满足价值贵重的物品或权利不能由单一主体掌控的业务需求，以此控制盗用、滥用等潜在风险。

例如，董事会的印章不能由单独的成员持有，银行保险箱的钥匙不能由单独的职员保管。在数字化的场景中，涉及多方隐私数据的业务合作，数据密钥也不能由单一主体掌管。

为了实现安全的秘密分享效果，最直接的秘密字符串分片方式并不能保障其安全性，攻击者无需收集足够的分片，便可以获得秘密的部分信息，示例如下：

因此，我们需要引入更为精巧的分片构造方式。

最常见的构造方式利用了拉格朗日多项式插值算法。其核心思想为，t个点可以确定一个t-1阶多项式对应的曲线。每一个秘密分片都相当于多项式曲线上的一个点：

只要收集不同点的数目达到t个，就可以通过拉格朗日多项式插值算法求解出多项式中代表秘密的系数值。
如果点的数目不足t个，对应的多项式有无限多个，对应的秘密可能是任意值，对秘密的机密性保护达到了信息论安全。

具体构造方式可以参考Shamir Secret Sharing的(t, n)秘密分享方案，即，将秘密分为n份，任意t份都可以完整地恢复出拆分前的秘密。构造过程如下：

将秘密S作为多项式的第0阶常量系数，其余t-1个系数随机生成，由此构造出一个t-1阶的多项式，对应的曲线为C。
在曲线C上随机选n个不同的点，将其分发给n个参与者。
只要不小于t个参与者同意使用自己的点参与协同运算，便可恢复出曲线C对应的多项式，取其中第0阶常量系数，便可获得秘密S。

秘密分享在分布式密钥生成、密钥容灾恢复、数字版权管理、数据安全传输等业务领域中都有广泛应用。同时，秘密分享也是用于构造安全多方计算的重要技术之一。

基础的秘密分享方案可以进一步扩展为可验证秘密分享、多级多秘密分享、定期更新分片的主动秘密分享、可随时变更参与者的动态秘密分享、基于身份的秘密分享等方案，满足多方协作中多样化的业务需求。

秘密分享是所有门限密码算法的基础，解决了算法设计中密钥控制权安全分发的问题，用技术手段保障了隐私数据多方协作中，权利均衡、平等互信的效果。

02
门限加密

门限加密方案是门限密码算法常见应用之一，常常体现为一类分布式加解密协议，可以实现如下功能：

任意用户都可以使用公钥对数据进行加密。
私钥的所有权由多个指定的秘密持有者联合控制，只有满足数目的秘密持有者合作，将解密分片聚合，才能实现解密。

门限加密方案可以有效保护需要多方授权才能使用的隐私数据。回到之前董事会决策的示例，目前有一份敏感的业务数据需要给董事会成员汇报，由于数据的敏感性，需要确保有足够数量的董事在场，数据才能被解密。

门限加密方案可以很好地满足这一需求。传输业务数据前，使用门限加密的公钥对其进行加密，产生的密文只有当数量不少于门限值的董事授权同意之后才能进行解密。

使用门限加密方案的一般流程如下：

初始化：n个参与者约定设置门限值t，并获取自己的私钥分片x，联合计算数据加密公钥PK并公开。
加密：数据贡献者使用公钥PK对数据明文m进行加密，生成密文E(m)。
生成解密分片：参与者分别使用自己的私钥分片x对密文E(m)进行解密，生成解密分片D_x(m)。
聚合解密分片：参与者将解密分片聚合，只有获得不小于t个不同的解密分片D_x(m)之后，才可以完成聚合解密，获得数据明文m。

理论上，门限加密方案可以基于不同的计算困难性问题（参见第3论）构造，例如，基于离散对数的ElGamal门限密码学体系、基于Diffie-Hellman的门限密钥交换协议、基于大素数分解的RSA门限密码学体系、基于椭圆曲线离散对数问题的BLS门限密码学体系等。

工程上，门限加密方案目前已经比较成熟，以经典论文《Simple and Efficient Threshold Cryptosystem from the Gap Diffie-Hellman Group》为基础的开源参考实现为例，在个人计算机上，对单个数据块进行单次分片聚合和解密的耗时都在微秒级，已经可以满足大部分业务的商用性能要求。

应用上，除了之前描述的多方授权数据解密之外，门限加密方案在匿名电子投票、数据代理服务、数据外包计算等需要为多个数据贡献者提供联合数据使用授权特性的领域，均有广泛应用前景。