如何使用密码原语？逼近阈值算法

隐私数据密文控制只能由单个主体控制？多个不受信任的**如何安全地使用表示控制权的密钥？如何在技术层面保证多重授权的公平公正？当参与协作的主密钥丢失时，如何实现安全可靠的容灾？

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

因为谁拥有密钥就等于谁获得了控制权。不能控制密钥的另一方可能在合作关系中处于弱势地位。这将成为实现公平、平等多党合作的关键障碍。

以多方决策为例，在上市公司董事会会议上，多数董事需要签署决策事项才能生效。由于某些原因，会议不能面对面举行，所有董事必须使用数字签名远程完成签名过程。为了保证决议过程的保密性和公平性，每一位董事都不希望其他董事知道自己的选择，同时让股东群体对最终的决议结果进行核实，即汇总签名。

在此过程中，有三个主要功能点与隐私保护相关：

每一位董事的签名控制权应由其自己控制，而不是由一个中心化可信的第三方授权。

代表决策结果的总签名可以在大多数董事同意的情况下生成合法声明。

股东组需要验证聚合签名，但不需要知道哪些董事已签名。

上述功能点涉及到在多方协作过程中如何将原单密钥安全地分解成多个密钥段，并让各主体独立使用各自的密钥段进行协作，完成所需的密码协议过程。解决这一问题的关键在于阈值密码算法的巧妙构造。

门限密码算法广泛应用于多方协作的相关场景中，可以实现数据的联合授权、认证、密钥安全恢复、密钥安全交换等要求，在许多分布式多方计算协议中都可以看到。

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

秘密分享

在1979，ADI Shamir和George Blakley独立地提出了秘密共享的概念，这为门限密码学奠定了基础。

具体来说，秘密共享是指在多个参与者之间安全地共享秘密的一种方式，它具有以下特点：

每个参与者独立地持有秘密的一部分片段。只有把足够多的碎片组合起来才能找回秘密。

当获得的片段数量不足时，无论采用何种组合策略，都不会泄露秘密s的信息。

秘密共享的学术价值在于它以密钥分割的形式，为多个参与者安全、平等地分配原单密钥提供了技术手段。此外，它还实现了以下附加安全功能：

容错高可用：由于少量密钥碎片的损坏和丢失，密钥将不可用。

抗侧信道攻击：在密码学算法工程实现过程中，原有的固定密钥可能泄露部分密钥信息（见第五理论中的灰盒安全模）。然而，在碎片化之后，成功实施此类攻击的难度将成倍增加。

对于商业应用来说，其主要特点是密钥安全性分布均匀，容错性高，可以用来满足单个实体无法控制的贵重物品或权利的商业需求，从而控制潜在的盗用和滥用风险。

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

为了达到安全的秘密共享效果，最直接的秘密字符串分割方法并不能保证其安全性。攻击者无需收集足够的段就可以获取部分机密信息。示例如下：

因此，我们需要引入一种更复杂的片段构建方法。

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

只要不同点的个数达到T，就可以用拉格朗日多项式插值算法求解多项式中表示秘密的系数。

如果点的个数小于t，则存在无穷多项式，且对应的秘密可以是任意值。秘密的保护实现了信息理论的安全。

具体构造可参考Shamir秘密共享的（T，n）秘密共享方案，即秘密可分为n部分，任意T部分可在拆分前完全恢复秘密。施工过程如下：

将秘密S作为多项式零阶的常数系数，其余T-1系数随机生成。由此构造了一个T-1阶多项式，对应的曲线为C。

随机选择曲线C上的n个不同点，并将它们分配给n个参与者。

只要不少于t个参与者同意利用自己的点参与合作运算，就可以恢复曲线C的相应多项式，并取0阶常系数得到秘密s。

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

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

秘密共享是所有门限密码算法的基础。解决了算法设计中密钥控制权的安全分配问题，通过技术手段保证了隐私数据多方合作中的权利平衡和平等互信的效果。

阈值加密

门限加密方案是门限加密算法的常用应用之一，它往往体现为一种分布式的加解密协议。它可以实现以下功能：

任何用户都可以使用公钥来加密数据。

私钥的所有权由多个指定的秘密持有者共同控制。只有当多个秘密持有者合作并聚合解密片段时，才能实现解密。

该门限加密方案能有效地保护需要多方授权的隐私数据。回到前面的董事会决策示例，目前有一个敏感的业务数据需要向董事会成员报告。由于数据的敏感性，有必要确保在解密数据之前有足够数量的控制器。

门限加密方案能很好地满足这一要求。在业务数据传输之前，使用门限加密的公钥对其进行加密。生成的密文只有在阈值授权的控制器数目不小于后才能解密。

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

初始化：n个参与者同意设置阈值T，获取自己的私钥片段x，共同计算数据加密公钥PK并公开。

加密：数据贡献者使用公钥PK加密数据明文m并生成密文e（m）。

生成解密片段：参与者使用自己的私钥片段x来解密密文e（m）并生成解密片段D_x（m）

聚合解密碎片：参与者聚合解密碎片，在X（m）之后只得到不少于t个不同的解密碎片，我们就可以完成聚合解密，得到数据明文m。

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

在工程上，门限加密方案目前已经比较成熟，以经典的基于gap-Diffie-Hellman组的简单高效的门限加密开源参考实现为例，在个人计算机上用微秒来聚合和解密单个数据，能够满足大多数企业的商业性能要求。

在应用中，除了前面描述的多方授权数据解密外，门限加密方案在匿名电子投票、数据**服务等领域有着广阔的应用前景，数据外包计算等领域需要为多个数据贡献者提供具有联合数据使用授权特征的数据。

门限签名

门限签名方案是门限密码最常用的应用。基于秘密共享的核心思想，门限签名方案通过将私钥分割成多个秘密片来实现以下效果：

只有秘密碎片的持有者相互合作，才能产生有效的签名。

即使某些秘密片段丢失，只要剩余的秘密片段不小于阈值，仍然可以生成有效的签名。

在共同生成的签名中，不披露哪些持有人参与了签名过程。

在商业应用中，门限签名方案可以用来构造有效的多方联合签名过程。与传统的数字签名方案相比，整个签名过程消除了单一主体保留密钥所带来的系统单点失效风险以及跨机构信任问题。

秘密分区的每个持有者对签名私钥具有同等的控制权。门限签名方案提供了私钥容灾和外部验证匿名的功能。

这种方案可以显著提高用户对数据认证的信任度，促进多方的平等合作。它适用于目前使用数字签名的所有应用场景，可以看作是传统数字签名方案在分布式业务环境下的全面升级。

使用门限签名方案的一般过程如下：

初始化：n个参与者同意设置阈值T，获取自己的私钥分区x，共同计算数据签名公钥PK并公开。

生成签名片段：参与者使用私钥片段x为数据M_x生成签名片段sig

聚合生成签名：合并签名片段，只有不少于t个签名片段才能生成完整的签名sig。

验证签名：验证者使用公钥PK验证数据M的签名sig。

与门限加密方案类似，门限签名方案可以根据不同的计算困难来构造和实现（见理论3）。例如，可以构造基于2国家安全标准算法的门限签名方案。

目前，最常见的开源实现是基于BLS（BonehAMPLndash；nnAMPLndash；shacham）签名算法。该方案的验证效率并不差，但在签名聚合过程中，签名生成的时间会随着参与者数量的增加而显著增加，可以达到毫秒级，比传统数字签名方案慢几个数量级。

另外，在当前门限签名方案的初始化过程中，如果不依赖可信第三方，将面临交互轮过多、构造复杂等问题。上述工程问题可能会给需要高频签名操作的应用带来一些性能挑战，但对于一般应用来说，它们不应该成为性能瓶颈。

一般来说，门限密码技术为隐私保护提供了一系列高效、易用的分布式数据协作技术。随着它的应用越来越广泛，NIST在2019年提出将与门限密码相关的密码原语标准化。从单主体使用和多方协同使用两个方向，尝试对多个门限密码方案进行分类和标准化。

标准化完成前，根据具体业务需求，门限加密方案的基本技术选择可参考下图：

它是：谁控制多方合作密钥，而门限密码是去中心化的！

门限密码体制通过对隐私保护方案中的密钥进行划分，使得按需分配密钥所代表的数据控制权成为可能。对于来自多方的隐私数据，门限密码技术提供了一种安全、平等、高效的协同认证和计算工具，可用于解决现代分布式业务环境中多方数据认证和可信数据交换等核心业务挑战。

在多方数据协作场景中，基于可信硬件（TEE）的解决方案也是业界研究的热点。它背后的原则是什么？详情请注意以下分解。