Cobo 密码知识讲堂：ECDSA 门限签名算法分析与比较

从多维度对不同 ECDSA 门限签名算法进行横向比较。

撰文：Cobo 密码学团队

本讲概述：在上一期课程中，我们对已有的 ECDSA 门限签名算法技术路线进行了归纳和总结，本期课程将构建一套评价体系，并对不同算法进行横向比较。首先，紧密结合应用需求，提出 ECDSA 门限签名算法的衡量指标，并解释其概念内涵，完成评价体系的构建；其次，从各衡量指标出发，分析比较各算法在该指标上的表现；最后，结合分析比较结果，对未来 ECDSA 门限签名算法的设计提供指引方向。

Part 1：ECDSA 门限签名算法衡量指标

在区块链领域，ECDSA 门限签名主要用于分布式场景下的数字资产托管，其核心功能需求为「高效」和「安全」。「高效」是指算法流程简单，交互次数和计算量较少；「安全」是指签名无法伪造，同时恶意节点偏离协议的行为并不会导致任何私钥信息的泄漏。通过对「高效」和「安全」两个概念的拆解，我们提出 ECDSA 门限签名算法的四个关键衡量指标，即门限最优、交互轮数、安全性和可审计性，而每个指标内部又可以进行进一步细化，具体见图 1。

图 1 ECDSA 门限签名衡量指标

门限最优

门限最优（Threshold Optimality）是指在  （n，t）-ECDSA 门限签名算法中，节点总数仅需满足 n>=t 。在签名门限  t 不变的条件下，非门限最优算法相比门限最优算法，需要将私钥碎片分发到更多的节点上，这增加了运营成本以及私钥泄露的风险。因此从应用成本和安全性角度考虑，门限最优是非常必要的性质。

交互轮数

交互轮数是指在签名过程中节点之间需要进行数据交互的次数，是衡量算法是否高效的一个核心指标。在分布式应用场景中，节点地理区域分布广泛，节点之间的网络连接存在不稳定性和延迟性，较少的交互次数能够有效提高算法运行的成功率。需要说明的是，目前很多算法支持预处理阶段（Preprocess Stage），即将与待签名消息无关的计算预先处理，使得线上阶段（Online Stage）仅需一轮交互即可完成签名。这种设计方式是门限签名算法在应用模式上的创新，并不直接反映该算法的复杂度或者高效性。因此在本文在统计算法交互轮数时，不对预处理过程和线上计算过程进行区分。

安全性

算法的安全性是一个非常综合的概念，对于 ECDSA 门限签名而言，安全一般是指签名不可伪造，相关论文也提供算法安全性的形式化证明。为了更加精细化地描述安全性，我们将其拆解为以下三方面内容：

（1）安全假设

在算法安全性形式化证明中，会将某些困难问题的求解过程规约为该算法的攻击过程。一旦该算法是不安全的，那么一定能够构造出解决某些困难问题的方法，而该问题是公认的难解或不可解问题，因此被证明算法是安全的。而这些问题就是该算法的安全假设。安全假设越少或者越弱，说明算法的安全依赖少，安全性更高。

（2）攻击模型

攻击模型中，我们重点关注恶意节点对诚实节点的腐化能力（Corruption），具体可以分为静态模型（Static）和动态模型（Adaptive）两种。在静态模型下，恶意节点需要在签名开始之前，确定需要腐化的节点，且在签名开始后不可以更换或者新增；在动态模型下，恶意节点可以根据数据发送情况，在签名过程中重新确定腐化节点。显然，动态模型下的安全性更高，但是由于存在通用方法能够将静态安全转化为动态安全，因此二者没有根本性区别。

（3）通用组合

通用组合模型（Universal Composability）是基于模拟（Simulation）的安全范式，强调已经证明安全的协议组合后形成的高级协议同样能保证安全。可以说 UC 安全不仅仅局限于算法本身，而且上升到复杂系统中的安全性，因此比普通安全性级别更高。

可审计性

可审计性（Auditability）是指节点在签名过程中发送数据的合法性是可验证的，能够精准定位在签名过程中发送错误数据从而导致签名失败的恶意节点，因此该性质也称为可验证退出（Identifiable Abort）。这一性质在 ECDSA 门限签名算法实际应用场景中非常必要，保证能够及时识别恶意节点，排除安全隐患，确保签名过程安全顺畅。

Part 2：ECDSA 门限签名算法比较

根据上一部分内容所提出的 ECDSA 门限签名算法的四个关键衡量指标及其拆解细化结果，我们对各算法进行了详细比较。除此之外，为方便门限签名相关领域工程师更好的完成技术选型，我们新增一个指标「算法热度」，去衡量该算法目前开源库的多样性、在产业中的应用范围以及受认可程度。具体比较结果见表 1。

表 1 ECDSA 门限签名算法比较

（1）门限最优

除了最早 ECDSA 门限签名算法 GJK96 不满足以外，其余算法均满足该性质。这侧面表明门限最优是目前 ECDSA 门限签名设计的基本需求，而设计难点也集中在这里。需要说明的是，GGN16 首次提出门限最优的性质，并给出了明确定义，也是首个满足门限最优的 ECDSA 门限签名算法。

（2）交互轮数

根据交互轮数，可以将算法分为两类，即固定轮数和变化轮数。固定轮数算法中，BGG17、CMP20、CGGMP21 的交互轮数最少，为 4 轮，其他算法交互次数均高于 4 轮；变化轮数算法中，DKLs20 交互次数为 6+logt，其中 t 为签名门限值，这是因为在签名中，未完成乘法碎片到加法碎片的转化，使用的 Binary Tree Approach 的计算模式。

（3）安全假设

共性方面，所有 ECDSA 门限签名算法都是以 ECDSA 签名算法本身的安全性为基础，但是对于有预计算的协议（如 GG20、CMP20），标准的 ECDSA 安全性（Standard ECDSA Security）是不足的，需要依赖于增强 ECDSA 签名算法（Enhanced ECDSA Security），即在攻击者预先知道 R 的情况下，签名仍保持安全。个性方面，不同 ECDSA 门限签名算法的安全假设与其使用的核心密码学技术高度相关，如 GG18、GG20、CMP20 等算法使用了 Paillier 同态加密算法，都需要依赖于 Strong RSA 假设，如 CCLST20 使用的 CL 同态加密算法，则需依赖 Low Order Assumption 和 Strong Root Assumption。

（4）攻击模型

攻击模型方面，CMP20 和 CGGMP21 支持动态腐化（Adaptive Corruption），而其余算法均为静态腐化（Static Corruption）。鉴于已经存在通用算法完成静态腐化安全到动态腐化安全的转化，我们认为所有算法在该指标下都是同等安全的。

（5）UC 安全

CMP20 和 CGGMP21 明确给出了算法 UC 安全的形式化证明；DKLs20 中使用的零知识证明协议如果满足 UC 安全，那么 DKLs20 也是 UC 安全的；其他算法虽然大部分都是基于 Simulation-based 安全定义下完成的安全性证明，但是并没有证明是 UC 安全的。

（6）可审计性

GG20 和 CGGMP21 明确给出了算法在不同中止情况下对作恶者身份的揭示方法，主要依赖于零知识证明和挑战验证两种模式完成；其他算法并没有直接给出类似的机制，但是我们不排除个别算法在相关步骤增加零知识证明后，也满足该性质。

（7）算法热度

目前业内热度较高的算法为 GG18、GG20、LNR18、CGGMP21、DKLs20，这些算法有丰富的开源库可供选择，同时根据公开消息已经被多个公司采用用于数字资产的安全托管；而算法 GJK96、GGN16、BGG17 热度较低，GJK96 是由于非门限最优不满足应用场景需求，而 GGN16 和 BGG17 则是由于门限化同态加密算法构建的复杂性导致实用性较低。当前典型的开源库及其实现的算法见附录。

Part 3：ECDSA 门限签名算法设计方向

以上两部分分别介绍了 ECDSA 门限签名算法的衡量指标和各算法在该评价体系下的分析与比较。综合以上结果，未来 ECDSA 门限签名算法的设计中，要以门限最优为基本要求，通过协议的巧妙设计，尽可能较低交互轮数（4 轮或以下），在依赖较少安全假设下（最好仅需 Standard ECDSA Security），保证 UC 安全，且具备可审计性。

附录：典型算法开源库汇总