Foundations of Secure Interactive Computing
Foundations of Secure Interactive Computing
复制标题
DOI：
10.1007/3-540-46766-1_31
复制
发表时间：
1991-08
期刊：
影响因子：
--
通讯作者：
Donald Beaver
中科院分区：
文献类型：
--
作者：
Donald Beaver
安全多方计算问题通常描述如下：网络中的每个参与者都拥有一个私有输入。他们想一起计算函数F（x1，...，xn），而不泄露输入，即使没有特定的玩家可以被信任。试图设计问题的正式定义已经单独处理解决方案的属性（正确性，隐私等），给出了一系列令人满意的性质和各种各样的定义，这些定义不支持清晰或可比的证明.我们提出了一个清晰、简洁和统一的定义，用于交互计算中的安全性和可靠性.我们发展了一种称为相对有序性的简化方法，它可以在一次打击中获得所有想要的属性。相对弹性允许人们根据安全性和可靠性对任意协议进行分类和比较，就像图灵约简允许人们根据复杂性对算法进行分类和比较一样。安全性和可靠性可以归结为一个简单的陈述：一个可信的协议，如果它和一个理想的协议一样有弹性，那么它就是一个可信的协议。相对弹性（Relative Resilience）涵盖了各种交互式计算的安全性和可靠性概念，包括零知识证明系统、拜占庭协议、不经意传输、双方不经意电路评估等。相对弹性（Relative Resilience）提供了其他方法所缺乏的模块化证明技术：可以比较从真实世界协议到理想协议的协议序列，以更大的清晰度和更小的复杂性证明每个连续协议的相对弹性。关于安全性的“传递性”和级联协议的安全性的民间定理现在是可证明的;并且证明表明，这种民间定理在以前未被注意到的微妙条件下失败。我们的定义和证明技术的简洁性和模块化提供了很大的清晰度，在设计和推理协议，并已导致可证明安全的协议，显着更有效的比那些出现在文献中。
The problem of secure multiparty computation is usually described as follows: each ofnplayers in a network holds a private inputxi. Together they would like to compute a functionF(x1,...,xn) without revealing the inputs, even though no particular player can be trusted. Attempts to contrive formal definitions for the problem have treated properties of the solution separately (correctness, privacy,etc.), giving anad hoccollection of desirable properties and varied definitions that do not support clear or comparable proofs.We propose a clear, concise, and unified definition for security and reliability in interactive computations. We develop a reduction calledrelative resiliencethat captures all desired properties at a single blow. Relative resilience allows one to classify and compare arbitrary protocols in terms of security and reliability, in the same way that Turing reductions allow one to classify and compare algorithms in terms of complexity. Security and reliability reduce to a simple statement: a protocol forFisresilientif it is as resilient as anidealprotocol in which a trusted hostisavailable to computeF. Relative resilience captures the notions of security and reliability for a wide variety of interactive computations, including zero-knowledge proof systems, Byzantine Agreement, oblivious transfer, two-party oblivious circuit evaluation, among others.Relative resilienceprovides modular proof techniques that other approaches lack: one may compare a sequence of protocols ranging from the real-world protocol to the ideal protocol, proving the relative resilience of each successive protocol with greater clarity and less complexity. Folk theorems about the “transitivity” of security and the security of concatenated protocols are now provable; and the proofs reveal that such folk theorems fail under subtle conditions that have previously gone unnoticed. The conciseness1and modularity of our definitions and proof techniques provide great clarity in designing and reasoning about protocols and have already lead to provably secure protocols that are significantly more efficient than those appearing in the literature.