Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations
译：基于安全多方计算的两方椭圆曲线数字签名

• 摘要部分
• • 引言
  • 总结

论文地址：https://eprint.iacr.org/2019/503.pdf
因为该篇文章太长，所以将分两次进行介绍，该篇博文只介绍背景知识、结论等，核心部分推导我将会在下一篇博文中进行介绍。如果翻译与理解有不对的地方，还请读者大大们指摘。（部分翻译内容也会进行增加补充）>-<

摘要部分

ECDSA is a widely adopted digital signature standard. Unfortunately, efficient distributed variants of this primitive are notoriously hard to achieve and known solutions often require expensive zero knowledge proofs to deal with malicious adversaries. For the two party case, Lindell [Lin17] recently managed to get an efficient solution which, to achieve simulation-based security, relies on an interactive, non standard, assumption on Paillier’s cryptosystem. In this paper we generalize Lindell’s solution using hash proof systems. The main advantage of our generic method is that it results in a simulation-based security proof without resorting to any interactive assumptions.
Moving to concrete constructions, we show how to instantiate our framework using class groups of imaginary quadratic fields. Our implementations show that the practical impact of dropping such interactive assumptions is minimal. Indeed, while for 128-bit security our scheme is marginally slower than Lindell’s, for 256-bit security it turns out to be better both in key generation and signing time. Moreover, in terms of communication cost, our implementation significantly reduces both the number of rounds and the transmitted bits without exception.

译: ECDSA（椭圆曲线数字签名）是一个被广泛采用的数据签名标准。但不幸的是ECDSA的密码学原语却很难实现高效的分布式变种方案，且经常需要高昂的零知识证明去处理恶意攻击。从现有两方的案例上看，Lindell最近有做出了一个有效的解决方案去实现基于模拟的安全¹，该方案依赖于一个交互式非标准的Paillier密码体制的假设。本论文中我们归纳了Lindell使用hash证明体制的解决方案。而我们的泛用方法的主要优势在于它无需进行任何交互式的假设即可实现基于模拟的安全。在具体的构造上，我们用虚二次域类群²来展示我们怎么实例化方案架构的。我们的实现表明（在Lindell方案上）删除此类的交互式假设的实际影响较小。事实而言，在128-bit安全等级下我们的方案比Lindell的要慢一些，但是在256-bit安全等级下，它在密钥生成和签名时间上都比Lindell的方案要好。此外，在通信开销上，我们的方案显著减少了轮换次数并且没有遗漏任何传输比特。

引言

门限密码学中允许 n n n个使用者以某种方式去共享一个通用密钥，任何 t t t方（ t t t为门限阈值）的子集都可以使用这个通用密钥去解密或者签名，这个而任何小于t的联盟都无能为力去解密或签名。这个范例的关键特征在于它允许使用无需重构的共享密钥。这意味着每当密钥被使用（去签名/解密）时， t t t方子集中人员就必须积极参与。
门限密码学应用范围比较广，从多个签名者需要签署同一份文件到分布式场景下敏感文件需要被定额人数授权。这种多用途引发了对门限密码学研究的热潮，主要表征在1990年早期到2000年早期，产生了最广泛被使用的门限密码学方案。因为如下的原因近些年可以看出在这个领域的研究兴趣又一次高涨：首先，很多初创公司正在使用这种技术去保护现实生活中的应用程序。此外，对于使用ECDSA作为基础签名方案的比特币和其他加密货币，即有安全漏洞就会导致实际的金融损失的数字货币类。虽说基于多重签名的对策已经内置到比特币中，但它们提供的灵活性较差并且在匿名以及可伸缩性上产生了问题（见[GGN16]）。最后，一些20年前被开发出的方案并不能满足当前应用程序所希望的那样高效，像ECDSA/DSA签名就是如此。事实上，对于许多其他方案，快速门限变种（例如RSA解密/签名和ECIES解密）是已知的构造其签名的有效门限变种比证明它们要困难得多。这种不对等的原因似乎是需要从一个未知 k k k中反推计算出 k − 1 m o d q k^{-1}mod q k−1modq的结果困难造成的（这边意译）。为了解释为何如此，让我们首先简单回顾一下ECDSA是如何实际运作的。公钥是一个椭圆曲线上的点 Q Q Q并且签名密钥是 x x x，像 Q ← x P Q\leftarrow xP Q←xP，其中 P P P是一个椭圆曲线上基于 q q q阶的生成的点。为了签名消息 m m m首先要用一些合适的hah函数 H H H对其进行hash处理，然后根据以下算法步骤进行处理：

1. 在 Z / q Z Z/qZ Z/qZ中选择随机数 k k k
2. 计算 R ← k P R\leftarrow kP R←kP
3. 令 r ← r x   m o d   q r\leftarrow r_{x}\ mod\ q r←rx​ mod q 其中 R = { r x ,   r y } R=\{r_{x},\ r_{y}\} R={ rx​, ry​}
4. 设置 s ← k − 1 ( H ( m ) + r x )   m o d   q s\leftarrow k^{-1}(H(m) + rx)\ mod\ q s←k−1(H(m)+rx) mod q
5. 输出 ( r , s ) (r, s) (r,s)
   
   现在，最自然实现以上算法分配步骤应是在参与方之间分享并累加 x x x，然后开始用一个多方计算协议去产生签名。在两方案例中，这意味着参与方需开始共享 x 1 x_1 x1​和 x 2 x_2 x2​使得 Q = ( x 1 + x 2 ) P Q=(x_1+x_2)P Q=(x1​+x2​)P。参与方可以继续产生随机数 k 1 k_1 k1​和 k 2 k_2 k2​进行共享，使得 R = ( k 1 + k 2 ) P R=(k_1+k_2)P R=(k1​+k2​)P。然而在这一点上如何有效地计算 k 1 ′ , k 2 ′ k^{'}_1,k^{'}_2 k1′​,k2′​使得 k 1 ′ + k 2 ′ = k − 1   m o d   q k^{'}_1+k^{'}_2=k^{-1}\ mod\ q k1′​+k2′​=k−1 mod q并不是很清晰。
   从论文[MR04]开始，两方ECDSA签名协议开始在 x x x和 k k k间采用共通乘法方式共享。构建的基本思路是非常简单的。参与方起初持有 x 1 x_1 x1​和 x 2 x_2 x2​使得 Q = x 1 x 2 P = x P Q=x_1x_2P=xP Q=x1​x2​P=xP。每当新签名产生时，他们产生随机数 k 1 ， k 2 k_1，k_2 k1​，k2​使得 R = k 1 k 2 P = k P R=k_1k_2P=kP R=k1​k2​P=kP。显然，这样的方式将允许获得反置 k ′ k^{'} k′，即 ( k 1 ′ ) − 1 ( k 2 ′ ) − 1 = ( k 1 k 2 ) − 1   m o d   q (k^{'}_1)^{-1}(k^{'}_2)^{-1}=(k_1k_2)^{-1}\ mod\ q (k1′​)−1(k2′​)−1=(k1​k2​)−1 mod q。最后他们将会用Paillier的同态加密方案去秘密添加他们自己秘密并完成签名。举例而言，就是参与方 P 1 P_1 P1​计算 c 1 ← E n c ( ( k 1 ) − 1 H ( m ) ) c_1\leftarrow Enc((k_1)^{-1}H(m)) c1​←Enc((k1​)−1H(m))和 c 2 ← E n c ( ( k 1 ) − 1 x 1 r ) c_2\leftarrow Enc((k_1)^{-1}x_1r) c2​←Enc((k1​)−1x1​r),然后 P 2 P_2 P2​可以利用方案中的同态特性完成签名，如下：
   c ← c 1 k 2 − 1 c 2 k 2 − 1 x 2 = E n c ( ( k 1 ) − 1 H ( m ) ) E n c ( ( k 1 ) − 1 x 1 r ) = E n c ( k − 1 ( H ( m ) + x r ) ) c\leftarrow c_1^{k_2^{-1}}c_2^{k_2^{-1}x_2 }= Enc((k_1)^{-1}H(m))Enc((k_1)^{-1}x_1r)=Enc(k^{-1}(H(m)+xr)) c←c1k2−1​​c2k2−1​x2​​=Enc((k1​)−1H(m))Enc((k1​)−1x1​r)=Enc(k−1(H(m)+xr))
   
   P 2 P_2 P2​通过将 c c c发回给 P 1 P_1 P1​来结束协议。现在，如果 P 1 P_1 P1​也知道解密密钥，那么他就能够从 c c c中提取签名 s ← k − 1 ( H ( m ) + x r ) s\leftarrow k^{-1}(H(m)+xr) s←k−1(H(m)+xr)
   但是，证明各方都正确遵守了协议是很难的。最初的尝试[MR04]通过高昂的零知识证明解决了这一问题。此外最近Lindell在[Lin17]中提供了一个更加简便和有效的协议。Lindell的协议的关键思路是有观察到在上述两方ECDSA签名协议中，不诚实方能制造非常小的麻烦。但事实上，如果在准备阶段， P 2 P_2 P2​同时收到了Paillier方案中要用的加密密钥和 P 1 P_1 P1​的签名密钥的加密 E n c ( x 1 ) Enc(x_1) Enc(x1​)，那么根本上来说，一个不诚实的 P 1 P_1 P1​能做的就是参与 R ← k 1 k 2 P R\leftarrow k_1k_2P R←k1​k2​P的产生。但需要注意后者建立在DH协议基础之上，是非常有效且鲁棒性的协议。
   
   另一方面，如果 P 2 P_2 P2​不诚实，那么她能做的就是（除了再次产生一个R）去构造一个有损害的 c c c作为最终反馈给 P 1 P_1 P1​的结果。但是，当 P 2 P_2 P2​真的尝试那样做的话，那么通过简单验证结果签名的合法性将很容易检测到它的恶意行为。
   但是实际证明的话将会引发一些问题。首先第一个问题是由Paillier的明文空间是 Z / N Z Z/NZ Z/NZ（ N N N是一个大合数）而ECDSA签名依赖于 Z / q Z Z/qZ Z/qZ（ q q q是素数）。因此为了避免这个不一致的问题，需要确保将 N N N取得足够大，以便在整个签名过程中不会发生wrap-around情形³。这也意味着将 E n c ( x 1 ) Enc(x_1) Enc(x1​)发送给 P 2 P_2 P2​时， P 1 P_1 P1​需要证明明文 x 1 x_1 x1​在正确的范围内（即足够小）。
   在此证明中使用Paillier加密会产生一个微小的问题。事实上，如果要使用该方案在实际和模拟的执行中分辨敌手的不可区分性，似乎有必要设置一个关于Paillier密码体系不可区分性的规约。 这意味着必须设计一种证明技术，该技术可以成功使用Paillier加密方案而无需知道相应的密钥。 根据Lindell的协议，在设计基于模拟的安全策略来应对有恶意参与方 P 2 P_2 P2​时会出现问题。 在这种情形下， P 2 P_2 P2​确实可能会发送一个错误的密文 c c c（即不对签名进行加密）而模拟器根本无法将其识别为错误的密文。
   Lindell [Lin17]提出了两种可替代的证明来克服这一问题。 第一个依靠一个基于博弈的定义，并通过允许仿真模拟器异常终止来避免该问题，概率取决于已提出签名 q s q_s qs​的数量。 但这似乎导致了不紧密的安全性证明（因为规约减少了一个 q s q_s qs​因子）。 第二个证明是基于模拟的定义避免异常终止，但需要引入有关Paillier加密案的新的交互式的非标准假设。
   因此，可以说，尽管该领域最近有取得了进展，但仍然存在以下公开的问题：
   是否有可能设计出一种实用的两方ECDSA签名协议（两者都就计算效率和带宽消耗而言）不需要交互性假设并允许一个严密的安全规约？

总结

受到Lindell方案的启发，我们提出了第一个哈希证明系统的两方ECDSA签名的通用构造，系统构造是基于同质模数的。理论上来说，由于底层语义安全的同态加密方案的结构，我们的构造可以实现基于模拟的安全性证明，该证明即严格且无需交互性假设。事实上而言，我们使用CL框架从虚数二次域类组提供详细的实例化案并用C实现。与Lindell的基于Paillier的方案相比，在高级别的安全性方面，它产生了更好的性能；在标准级别上（128bit），它具有同样数量级。我们的解决方案在192bit以后的安全等级上比Lindell的运算要快。虚二次域中理想⁴算术的进步可能会带来改进（见[IJS10]实例）基于类组的可验证延迟功能也应激发该领域的最新研究（例如Chia 网络[Chi]也为此展开了竞争）。

这一段有点翻译和理解有些困难，后续进行更新改进。

最后，我们的工作聚焦在两方案例下。我们相信我们构造方案的想法将引发门限ECDSA签名案例的改善。我们留至下一步工作。