本科毕业设计（论文）

外文翻译

在区块链上建立安全计算

作者：Arka Rai Choudhuri,Vipul Goyal,Abhishek Jain

国籍：美国

出处：IACR-EUROCRYPT-2019

中文译文：

摘要

我们研究了区块链混合模型中安全计算的基础，在该模型中，区块链（建模为全局功能）可作为加密协议的所有参与者的Oracle。我们展示了区块链的破坏性和建设性应用：

我们证明了在许多安全证明中使用的经典的基于回卷的仿真技术在对抗区块链活动的对手时是失败的，这些对手已经读取并发布了对全局区块链的访问。特别地，我们证明了黑盒仿真的零知识(ZK)证明是不可能对抗区块链主动对手的。

然而，我们表明，如果诚实的各方也积极参与区块链，那么实现针对区块链活动对手的安全是可能的。我们构造一个与黑盒(1)轮ZK协议仿真。通过黑盒仿真证明了不可能实现等圆ZK，证明了该方法的有效性。

最后，我们演示了区块链的新应用，以克服在平面模型中并发安全计算的已知不可能结果。基于标准密码假设，构造了区块链混合模型中一般功能的并行自组合安全计算协议。

我们开发了一套在区块链混合模型中构建安全协议的技术，我们希望能在这一领域找到未来研究的应用。

1、简介

区块链是一项激动人心的新技术，对密码学界产生了深远的影响。区块链既提供了现有密码原语的新应用（如散列函数或零知识证明），也提供了新的密码原语实现基础（如公平安全计算[ADMM14、BK14、CGJ 17]或一次性程序[GG17]）。在这项工作中，我们试图研究区块链环境下安全计算协议的基础。更具体地说，我们研究了所谓的区块链混合模型，并研究了该模型中零知识和安全计算的构造。

区块链混合模型。为了便于在安全计算中使用区块链，我们研究了区块链混合模型，其中区块链（建模为全局分类账功能）可供密码协议的所有参与者使用。各方可以通过发布和阅读内容访问区块链，但没有任何一方对区块链拥有任何控制权。我们的建模遵循之前关于区块链功能形式化的优雅工作[KZZ16、BMTZ17、BGK 18]。特别是，我们的模型基于Badertscher等人[BMTZ17]的全球区块链分类账模型[BMTZ17]。

我们研究了基于模拟的区块链混合模型的安全性。在我们的模型中，模拟器对区块链没有任何控制权，只是把它当作一个Oracle，就像协议参与者一样。因此，与传统的可信设置模型（如公共参考字符串）不同，区块链混合模型没有为模拟器提供任何新的“动力”。特别是，模拟器仅限于其简单的模型功能，例如重置对手或使用其代码的知识。因此，在我们的模型中，区块链可以是全局的，因为它可以同时被多个不同的协议使用。这让人想起全球UC框架中的模拟[CDPW07，CJS14A，HPV16]。相关的模型是全局随机Oracle模型[CJS14A]，其中模拟器只能观察对手对随机Oracle的查询，但不能对随机Oracle进行编程（因为它是全局的，因此在许多协议中共享）。

基于区块链的安全计算。我们研究了存在全球区块链功能的安全计算的基础。有趣的是，我们演示了区块链在密码学中的破坏性和建设性应用。早期可能实现的原始事物现在变得不可能了。同样，在这个模型中的工作允许我们克服先前在密码学中建立的深层不可能性结果。有趣的是，我们还将挖掘延迟（通常被视为区块链的负面特征）用于本工作的建设性目的。我们接下来讨论主要结果。

1.1 我们的结果

区块链存在时的模拟失败。我们考虑一类新的对手，我们称之为区块链主动对手。这些对手与通常的密码对手类似，只是他们有用户访问区块链的权限，即他们可以在区块链上发布并在任何节点读取其状态。

我们注意到，这样的对手可以挫败许多用于证明标准密码方案安全性的现有仿真技术。为了说明主要思想，让我们考虑基于回卷的黑盒仿真技术，例如在零知识(ZK)证明[GMR85]、安全多方计算[Yao82,GMW87]和通过Fiat-Shamir启发式构造的随机oracle模型中的签名方案[FS86]。基于倒卷的仿真成功的一个关键条件是对手应该忽略倒卷。通常，这一要求可以很容易地满足，因为模拟器可以简单地“重置”对手的代码，从而防止它在整个重卷过程中保持状态。

然而，区块链活跃的对手可以定期发布区块链，并使用它在重绕时保持状态，因此检测到它正在重绕。在这种情况下，对手可以简单地中止模拟过程，从而使模拟过程失败，当模拟被要求为黑匣子时，将上述想法转化为正式的不可能结果，对区块链主动对手进行ZK证明并不太困难。

定理1（非正式）纯模型中不存在交互论证，即零知识w.r.t.黑箱模拟对抗区块链活跃对手。

上述不可能结果扩展到安全多方计算和其他自然加密原语，其安全性通过倒带模拟器得到验证。构造零知识协议。为了克服区块链带来的上述问题，我们也寻求区块链的解决方案。我们的想法是让协议区块链也活跃起来。也就是说，除了对手之外，诚实的各方也可以访问区块链。我们的第一个积极结果是区块链混合模型中的轮ZK证明系统，其安全性得到了w.r.t.黑盒模拟的验证。

定理2（非正式）在区块链混合模型w.r.t.黑盒模拟中，假设存在抗碰撞散列函数，存在轮ZK证明系统。有趣的是，在我们的构建中，诚实的各方不会在区块链上发布任何消息。相反，他们只在区块链的当前状态上保留一个“标签”，以决定是否继续该协议。

我们还表明，上述结果是严格的。也就是说，我们证明了在区块链混合模型中，使用黑盒模拟不可能实现恒圆ZK。

定理3（非正式）假设单向函数，在一个块链混合模型w.r.t.(期望概率多项式时间)黑盒模拟器中不存在O(1)轮ZK参数系统。

这与普通模型形成了鲜明的对比，在普通模型中，有许多经典的常数归零知识协议被证明是安全的w.r.t.黑盒模拟器[GK96，FS90，BJY97]。使用区块链进行并发安全计算。经典的安全计算协议，如[Yao82，GMW87]只实现“独立”的安全性，在对手的控制下，一个协议的多个副本可以同时执行，而不能设置并发的自合成。事实上，在普通模型中实现并发安全计算是不可能的[CKL06、LIN03、LIN04、LIN08、BPS06、GOY12、AGJ 12、GKOV12]。上述不可能的结果影响深远，排除了在各种设置下对大类功能进行安全计算的可能性。

有趣的是，我们证明了在区块链混合模型w.r.t.标准现实/理想模型概念中，使用PPT模拟器可以实现并发自合成。因此，我们的研究结果（综合起来）表明，在区块链混合模型中设计密码原语在某种意义上是困难的，同时也是容易的。

定理4（非正式）在区块链混合模型中，假设存在抗碰撞散列函数和无记忆传递，存在一个针对所有多项式时间函数的并行自组合安全计算协议。在我们的协议中，每一方都需要在区块链上发布一条初始消息（对应于对其输入和随机性的承诺）。然而，在协议开始之前，诚实的一方可以在“离线”阶段执行这个发布。特别是，一旦协议启动，诚实的一方就不需要在区块链上发布任何额外的消息。

许多以前的漂亮作品已经在各种设置模型中构建了并发（和普遍可组合）安全计算，例如可信公共参考字符串模型[CLOS02]、注册公钥模型[BCNP04]、防篡改硬件模型[Kat07、CGS08、GIS 10]和物理上不可分离的功能模型[BFSK11、DFK 14，BKOV17]。我们认为，区块链模型为这些模型提供了一个吸引人的去中心化替代方案，因为不涉及物理假设或集中信任方。此外，它允许将并发安全性建立在已经存在且广泛使用的基础设施上。此外，可以获得以下形式的有力保证：能够破坏我们构造的对手也可以破坏基础区块链的安全（可能允许其获得大量加密货币）或基础加密假设（在我们的例子）

UC安全不可能性。虽然定理4确定了并发自合成的可行性，但我们证明了区块链混合模型中不可能存在通用的合成安全性[Can01a]。

定理5（非正式）在区块链混合模型中，普遍可组合的承诺是不可能的。我们通过简单地将[CF01a]的不可能结果改编为区块链混合模型来证明上述结果。这一结果背后的主要直觉是，区块链混合模型中的模拟器与普通模型中的模拟器具有相同的功能，即，倒带对手或使用其代码知识的能力。至关重要的是，（与非可编程随机Oracle模型[CJS14A]不同），查看对区块链的查询的能力并不构成模拟器的新功能，因为每个人都可以看到这些查询。

1.2 技术概述

我们首先观察到，如果对手是区块链活跃的，它可以通过在区块链上发布迄今为止的交互记录来“检测”它正在被重绕。更详细地说，在收到一条传入消息后，对手将整个副本与会话ID连接起来，并将其提交给区块链Oracle。在给出响应之前，对手等待下一个块被挖掘并检查以下内容：它在区块链上发布的转录本确实已经出现，并且，在之前的任何块上都没有这样的转录本（对于同一会话和同一轮）。如果检查通过（在实际执行中得到保证），对手将诚实地进行计算并发送下一个协议消息。我们证明，任何多项式时间模拟器都不可能倒带这个对手，这是我们零知识黑盒不可能结果的基础。

构建黑盒零知识协议。为了克服区块链带来的上述问题，我们也寻求区块链的解决方案。我们的想法是让协议区块链也活跃起来。具体地说，我们让诚实的证明者跟踪区块链状态，并且，如果自协议开始以来挖掘的新块的数量超过固定数量k，则中止。因此，诚实的当事人使用区块链来实现超时机制。然而，我们强调，我们并不要求诚实的双方拥有同步时钟。唯一的要求是，协议必须在预先限定的时间内完成，正如区块链的进度所衡量的那样。例如，当使用比特币时，如果k设置为20，这将使双方在超时发生前近3.5小时完成零知识协议（因为比特币中大约每10分钟挖掘一个区块）。为了简单起见，我们将把参数k视为一个常量（即使我们的构造可以通过适当地调整协议的整数复杂性来处理k的任意值）。

我们设计了一个黑盒零知识证明的构造，协议中的“槽”（或倒带机会）的数量大于k。虽然对手可以在任何时间点向区块链Oracle发送任何信息，但在协议执行中最多可以有k个点，对手实际上从该点接收信息。Oracle一个新的（不可开采的）采空区。然而，通过我们的构造，这仍然会在协议中留下几个插槽，模拟器可以自由倒带（而不必伪造区块链状态）。

模拟器设计中的一个潜在的复杂因素是，除了新挖掘的区块外，对手还可以实时“监听”网络通信。这可能包括当前在网络上未完成的各种（诚实方）交易，并将等待包括在下一个区块中。这是通过Badertscher等人[BMTZ17]模型中的缓冲区读取形式化的。我们通过让模拟器简单地重放诚实方未完成的事务来处理这个问题，因为它们不能从主线程更改为前瞻线程。由于模拟器可以读取来自对手的所有传出消息，所以当前线程中的对手未完成事务（可能会从线程更改为线程）已经为模拟器所知。上述思想构成了我们第一个正结果模的基础，接下来我们将讨论仿真时间的问题。

模拟时间问题。有趣的是，区块链可用于实现全球不可伪造时钟这一事实在证明针对区块链活跃对手的安全性方面提出了一个新的挑战，据我们所知，这在密码学中并不存在。在密码学中，模拟器的运行时间通常大于对手的运行时间。这意味着在模拟执行期间挖掘的块的数量可能高于实际执行期间挖掘的区块的数量。然后，如果对手和区分者处于区块链活动状态，则挖掘的区块数可用作“侧通道”信息来区分真实和模拟执行！在普通模型中不会出现这样的困难，因为模拟器被认为完全控制了对手的时钟(包括冻结它的能力)。

为了解决这个问题，我们试图构建一个运行时间与实际协议执行时间相同的模拟器。为了达到这个目的，我们建立在精确零知识概念的技术基础上[MP06]。首先，我们似乎需要构造一个精确到1的模拟器，目前还不知道这是可能的。为了解决这个问题，我们的关键观察是，在模拟器完成所需的时间和它执行的计算步骤之间有一个关键的区别。特别是，如果模拟器可以并行执行许多计算，那么它在实际执行中可能会比验证程序执行更多的计算，但在相同的时间内完成。我们的重绕策略将并行运行多个执行线程（例如，通过复制多个对手代码），并确保在主线程完成时，所有重绕的执行线程也都已完成。为了确保模拟成功，我们的模拟器必须有一个超级恒定数量的重绕机会（可以并行进行）。这样的模拟器可以保证以下形式：协议中的对手验证器学习到的任何信息也可以由能够并行运行足够（多项式）数量计算的算法从头生成。例如，四核处理器能够运行4个并行计算。

我们认为仿真时间问题是一个相互独立的问题。特别是，理解模拟器所需的时间(而不是计算步骤的数量)可以进一步了解密码结构的知识复杂性，并激发对强安全性概念的研究。

黑盒零知识圆复杂度的下限。我们证明了在区块链混合模型中，恒定的圆形ZK参数是不可能的w.r.t黑盒模拟。我们的不可能结果甚至适用于预期的多项式时间模拟器。考虑一个敌对的验证器，它在响应来自验证程序的任何消息之前等待一个固定的恒定时间c。

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 44 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[273108]，资料为PDF文档或Word文档，PDF文档可免费转换为Word