SP20 - 大规模参与方门限密码学系统

演讲视频简介

突然发现离知乎上次更新文章已经过了4个多月的时间了，罪过罪过…今天为知友们带来Security and Privacy 2020上的一篇论文报告《Towards Scalable Threshold Cryptosystems》。这个视频主要是胡斌同学@HuBinnnnn 听译的，我对内容进行了校对，并制作了时间轴。胡斌目前在北航就读，也是我的师弟，对门限签名方案感兴趣的只有也欢迎和胡斌交流。

这个报告最让我惊讶的是第一作者Robert Chen竟然是一位高中生，感觉前浪已经被按在深海爬不出来了…当然了，还有BIU Winter School on Cryptography的发起者Benny Pinkas。这篇论文的核心构造和Pinkas等人的论文《SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension》很像，可以说是SpOT这篇论文中快速多项式插值的另一种应用。对相应技术感兴趣的知友可以两篇论文一起阅读。

演讲视频信息

• 视频链接： https://www. youtube.com/watch? v=K9JfFS8Y-L4
• 论文链接： http:// people.csail.mit.edu/de vadas/pubs/scalable_thresh.pdf
• 中文视频： https://www. bilibili.com/video/BV1k K4y1E74g/

演讲视频字幕

大家好，我今天要为大家讲解我们在大规模门限密码系统设计方面的一些工作。此工作由我和我的高中学生联合完成，我很荣幸能在过去两年担任他的导师。我还要感谢我在VMware研究中心的合作者以及我的导师。

我们先来介绍一下数字签名方案。在数字签名方案中，你有一个存有私钥sk的设备，此设备可以对消息签名。一个拥有对应公钥的验证者可以验证任意消息m所对应的签名。现在的问题是，如果这个设备遭到攻击者的攻击，攻击者可以拿到私钥，从而可以伪造任何消息所对应的签名。

签名方案在很多场景都有广泛应用，如安全浏览网页、WhatsApp安全通信等。如果在此类场景下攻击者可以获得私钥，那问题就变得很严重了。攻击者可以伪装成好友用WhatsApp和你通信，也可以偷走你的Facebook口令。

解决这个问题的一种方法是使用门限签名方案。具体思路是：将私钥拆分到多个设备中，例如拆分到5个设备中。只有同时使用3个或以上的设备，才可以生成签名，少于3个设备无法产生签名。

举个例子，设备1用它的私钥份额生成消息m的一个签名份额，设备3也生成一个签名份额，设备5也生成一个签名份额。

随后，他们分别把自己的签名份额发送给一个聚合方。聚合方生成与私钥sk对应的门限签名，但5个设备均无法得到sk本身。接下来，验证方可以用私钥所对应的公钥验证此聚合签名σ是否有效。同时，验证方无法知道这个签名是由门限签名，而不是正常签名方案生成的。

很棒的是，如果使用n选t秘密分享构造门限签名，即需要t个参与方生成签名，则即使任意t-1个参与方合谋，方案也是安全的。因此，该方案具有很强的抗攻击性。

门限签名方案在很多场景下都有广泛的应用。例如在加密货币钱包中，可以将私钥份额分发给信任方，从而保护比特币私钥。门限签名使共识协议支持更多的参与方。门限签名可以作为共识机制的随机源。门限签名可以用于投票系统，这里指的是没有考虑隐私保护的朴素投票系统。在投票场景下，门限签名的参与方数量和门限值都会非常大。如果我们认为未来是去中心化的，则可能会出现更多的门限签名应用场景。

本次报告我们面向未来，使门限签名支持非常大的门限值t，支持大规模参与方。这里主要考虑门限签名方案，但方法可以应用到任何门限密码学系统中。这也是一个贡献点，毕竟去中心化未来可能非常遥远，永远不会到来，谁知道呢。我们希望此技术在规模较小的场景下也可以提高方案效率。

我们来看看我们面临的挑战是什么。

第一个挑战是如何分割私钥。第一种答案是使用可验证秘密分享方案，这是一个非常著名的研究路线。可验证秘密分享方案允许知道密钥的处理方用可验证的方式分割私钥。不幸的是，由于处理方已知私钥，因此处理方自己就可以生成签名，这意味着此方案就不是一个门限签名方案了。

针对此问题，我们可以使用分布式密钥生成协议，这包含了一系列研究工作。在幻灯片的例子中，5个手机可以在不获取私钥本身的条件下联合生成私钥，5个手机最终得到的是私钥的秘密份额。听起来非常神奇，但确实可以做到。事实上，DKG协议最关键的创新点是构建了n个并发执行的VSS协议。本次报告，我们主要讨论的是更大规模的可验证秘密分享协议，而不是更大规模的DKG协议 因为很容易应用并发实现更大规模的DKG协议。

另一个难点是如何实现更大规模的聚合过程。这里的问题是，可验证秘密分享基于多项式，需要使用拉格朗日多项式插值。更准确地说，应该是所有高效的可验证秘密分享都基于多项式。拉格朗日插值的效率有点低，我们要解决插值效率低的问题。

我们先来讨论VSS协议。我们从Shamir提出的不可验证秘密分享协议开始，这是非常经典的密码技术。你持有私钥sk，你随机选择一个t-1阶多项式φ，使得φ(0)=sk。你随后向n个参与方分别发送私钥的秘密份额φ(i)。幻灯片中是5个参与方，每个参与方i得到φ(i)，而φ(i)就是参与方i得到的私钥秘密份额。在重建过程中，n个参与方中的t个参与方将秘密份额发送给重建方 重建方根据求值结果φ(1)、φ(2)和φ(3)，用拉格朗日插值恢复私钥sk=φ(0)。实际上，重建过程不用考虑具体的子集是什么，任意超过t个参与方子集的秘密份额都可以恢复出正确的私钥sk。

然而，这里的假设是处理方需要正确执行协议，为参与方提供正确的秘密份额。参与方也要正确地执行协议，将正确的秘密份额发送给重建方。但实际过程要比这复杂得多，我们需要考虑攻击行为。

可验证秘密分享这一系列工作的出发点就是要抵御秘密分享中的攻击。基本思路如下。与之前相同，你使用多项式φ构建Shamir秘密分享方案。但此时，你需要使用多项式承诺方案对φ作出承诺，得到承诺值c。处理方将承诺值广播给所有的参与方。同时，处理方给每一个参与方发送一个证据 ，证明φ(i)是正确的。参与方可以应用承诺值c验证φ(i)是否正确。

你可能注意到，可以通过向不同的参与方发送不同的承诺值来实施攻击。但我前面讲到，我们用广播信道发送承诺值。处理方向所有参与方广播承诺值c，广播信道保证所有参与方都可以收到相同的承诺值c。这可以阻止处理方为不同的参与方发送用不同多项式φ构造的秘密份额。在重建过程中，我们还会面临一个问题，某些参与方会给出错误的秘密份额。但现在，重建方可以要求参与方提供秘密份额的证明，验证秘密份额是否有效，并忽略无效的秘密份额。我们需要假设重建方也可以从广播信道获得承诺值c。

令方案变得更具规模的挑战是，多项式承诺值要不然长度太长，要不然生成得太慢。特别地，Petersen承诺值的长度为O(t)，比门限值t略大。然而，如果我们考虑其他方案，如Kate-Zaverucha-Goldberg或KZG承诺，此承诺方案的承诺值长度比较小，长度为常数，但计算复杂度为O(nt)。由于门限值t可以为n/2，实际应用中这样的计算复杂度就变得有问题了。

我们来看看KZG承诺的形式。KZG承诺的形式为g的指数幂，指数上是某个未知秘密点τ在φ上的求值结果。这里存在的问题是，如何在不知道τ的条件下求得φ(τ)。只要当τ的承诺值满足特定的格式，就可以在不知道τ的条件下求得φ(τ)。这里我就不具体讲解细节了，这是一个非常漂亮的方案构造。我们工作的核心就是要降低计算出所有证据所需的计算复杂度O(nt)。

让我来给大家展示一下此计算复杂度会对VSS的处理造成何种影响。假设你使用KZG实现了VSS。幻灯片中，y轴表示处理时间，x轴表示参与方的数量n，门限值设定为n/2。处理时间与参与方数量成二次线性关系。举例来说，在门限值比较小的时候，我们可以得到比较好的性能结果。随着门限值的增大，方案性能降低得非常快。如果门限值非常大，性能就超出了可实际使用的范围了。

反之，应用我们提出的新计算技术，KZG会变得非常快，我们大幅降低了VSS的处理时间。在非常大规模参与方的条件下，我们将性能提高了几个量级。即使参与方规模下降，性能提升量仍然很显著。即使参与方规模比较小，性能也有相应的提升。当参与方数量为2,000时，性能提升量大约为10到14倍。

这里用到的关键技术是多项式多点求值。我们要做的是，假设我有一个多项式φ，我要对φ做出承诺。现在，我想为点1、2、3、4计算证据。我们用聚合方多项式φ除以(x-1)(x-2)(x-3)(x-4)，这样我就得到了商和余数。

现在，我递归执行多项式除法，在左侧和右侧进一步得到商和余数。我分别用余数除以(x-1)(x-2)(x-3)(x-4)的左半边和右半边，我就得到了一些新的商和一些新的余数。我再执行相同的多项式除法操作。如果我再用余数除以上一层多项式的左半边和右半边，还会得到商和余数。实际上，在树的叶子节点中，余数就是φ在多项式根下的求值结果。大家只需要记住此结论即可，详细过程请阅读我们的论文。事实证明，此多项式多点求值方法的计算复杂度为O(nlog(t))。只有点为多项式的单位根时求值才是正确的，我在幻灯片上没标注此条件。

我们继续往下讲。目前我们只讨论了如何对多项式求值，我没有讲解如何得到这些求值所对应的证据，下面是证据的计算过程。让我们忽略除法过程和余数，重点关注商。基本思想是，我们应用KZG多项式承诺方案对商做出承诺，这样我们就得到了认证多点求值树，即AMT。这里的核心结论是，可以用O(nlog(t))的计算复杂度得到AMT。因此，我执行多点求值、计算承诺值，总计算复杂度仍然为O(nlog(t))。

现在，求值结果φ(3)所对应的证据就是从φ(3)到根节点路径上的所有值，此证据的长度为O(log(t))。我们通过增加证据长度来提高计算性能，因为原始KZG证据的长度为O(1)。我之前没有提到证据长度增加的问题，但增加量非常小。我们方案的证据长度会变得稍大，但计算所花费的时间会变得非常非常少。总之，增加证据长度来提高计算性能。计算n个点的KZF证据 之前的开销是O(nt)，现在的开销是O(nlog(t))，而证据的长度从常数变为了O(log(t))。

到目前为止，我们讨论了如何更高效地拆分私钥。我们让可验证秘密分享协议支持更多的参与方，方法是提出了一个新的KZG多项式承诺的证据计算方案。这个证据计算方案也可以用于构造更大规模的分布式密钥生成协议。可以阅读我们的论文，了解更多的细节。

接下来的问题是，如何在更大规模下聚合门限签名，答案是你可以使用拉格朗日插值，但插值过程仍然有点慢。我们来看看为什么插值过程会比较慢。在讲解为什么插值过程会比较慢之前，我们来看看插值过程慢到什么程度。幻灯片中，y轴是执行时间，单位是秒。x轴是签名方数量，门限值设置为n/2。正如大家所见，聚合时间与t成二次线性关系，方案不能支持太大规模的参与方。在小规模参与方下，协议性能还不错，但性能下降速度非常快。在大规模参与方下，性能会变得不可接受。

为什么会这样呢？当聚合集合P中t个参与方的签名时，我们要计算所有t个拉格朗日系数。我们来看看拉格朗日系数的形式。拉格朗日系数形式为一个分子除以一个分母。我们可以用O(t)时间计算出分子，因为可以用一次O(t)时间来计算所有乘积。随后，可以将乘积除以t次，这样就得到了所有的t个分子。不幸的是，如果用朴素的方法计算分母，则计算复杂度为O(t^2)。

事实证明，使用多项式多点求值方法，可以快速计算得到所有t个分母。这里我就不详细展开讲解了。基本思想是，你需要计算特定多项式的导数。实际上，你需要计算我前面提到的聚合多项式的导数。随后，你计算导数在集合P中所有参与方索引值下的求值结果，对求值结果进行转换，就能得到所有的分母。可以阅读我们的论文，了解计算过程的所有细节。

这个优化计算方法所带来的性能提升是非常明显的。多项式多点求值的计算复杂度为O(tlog^2(t))。我们把聚合时间从数十小时降低到数十秒，从几分钟降低到几秒。在签名方数量比较小的场景下，性能大约提升了2倍。

我们对性能提升结果很满意。我们希望一部分未来应用场景可以因为此技术而受益。但我们认为，有些应用场景可以立刻使用此技术来提升性能。举个例子，以Dfinity为代表的共识协议需要数千个法定选举人的投票，而这些协议可以利用我们提出的快速门限签名来获得更好的效率。

我们总结一下。我们展示了如何使用快速插值算法聚合门限签名，O(t^2)时间变为了O(tlog^2(t))时间。此算法不仅可以用于门限签名，还可以用到门限加密等其他门限密码学系统中。只要密码学系统用到质数阶有限域单位根多项式插值，此技术就有用武之地。随后，我们展示了如何实现更大规模的VSS协议和DKG协议，方法是应用AMT技术更高效地计算KZG多项式的证据。计算时间从O(nt)提高到O(nlog(t))，但我们把证据长度从O(1)提高到O(log(t))。一般情况下，任何可提高KZG证据计算效率的技术都是非常有用的，因为可以使用更高效的KZG证据计算方法替代Petersen承诺或构造其他方案，例如基于多项式承诺的认证数据结构，这也是当今非常流行的一个研究方向。

此领域有个非常令人振奋人心的新工作，是由Feist和Khovratovich完成的。他们给出在O(nlog(n))时间计算所有KZG证据，且证据长度为常数的方法。近似复杂度下，此方法比AMT更优。我们实现了他们的方案，虽然计算时间变得稍长，但证据长度很小。我们非常激动地看到这个新的方法也能用在VSS和DKG协议中。你可能会说100万个参与方有点太多了 哪有这样的应用场景？再次重申，应用场景由未来决定，且小规模场景下我们的方法仍然更快。未来工作方面，我们需要解决VSS和DKG协议广播数据量过大的问题。我们希望能广播信道支持更大规模，广播信道要为上百个参与方发送承诺值。幻灯片最下方给出了我们代码的仓库链接。欢迎大家提问，非常感谢大家的聆听。