k-Round Multiparty Computation from k-Round Oblivious Transfer via Garbled Interactive Circuits
k-Round Multiparty Computation from k-Round Oblivious Transfer via Garbled Interactive Circuits
复制标题
DOI：
10.1007/978-3-319-78375-8_17
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Fabrice Benhamouda;Huijia Lin
中科院分区：
文献类型：
--
作者：
Fabrice Benhamouda;Huijia Lin
本文从不经意传输（OT）协议出发，提出了一种新的多方计算（MPC）协议的构造方法。我们的构造在MPC和OT之间建立了紧密的联系：在半诚实安全的情况下，对于任何一个，k轮半诚实OT都是必要的，并且是完全fork轮半诚实MPC。在轮最优的情况下，我们从2轮半诚实OT得到2轮半诚实MPC，解决了半诚实MPC的轮复杂性假设弱和必要的。相比之下，以前的2轮构造依赖于不可分割性混淆或见证加密的重型机器，或者双线性对群的代数结构。更一般地说，对于任意轮数k，所有k轮半诚实MPC的构造都需要至少有轮数的OT。在恶意安全性的设置中，我们证明了：对于任意轮，k轮恶意OT是必要的，并且完全fork轮恶意MPC。事实上，OT满足一个较弱的延迟半恶意安全概念就足够了。在公共参考串模型中，对于任意一个，我们从任意k轮半恶意OT和非交互零知识得到任意k轮恶意UC协议。以往的普通模型中的5轮协议和公共参考串模型中的2轮协议都需要DDH或LWE等代数假设。粗略地说，它允许混淆参与特殊形式交互的交互式机器。乱码机器可以模拟原始的交互，接收以透明方式发送的消息（不使用秘密编码），并且只显示交互的转录本，前提是转录本在计算上是唯一定义的。我们表明，乱码的交互式电路的目的，构建MPC可以使用OT实现。沿着的方式，我们还提出了一个新的原语的证人选择器，加强证人加密，和一个新的概念的零知识功能承诺。
We present new constructions ofround-efficient, or evenround-optimal, Multi-Party Computation (MPC) protocols from Oblivious Transfer (OT) protocols. Our constructions establish atightconnection between MPC and OT: In the setting of semi-honest security, for any,k-round semi-honest OT isnecessary and completefork-round semi-honest MPC. In the round-optimal case of, we obtain 2-round semi-honest MPC from 2-round semi-honest OT, resolving the round complexity of semi-honest MPC assuming weak and necessary assumption. In comparison, previous 2-round constructions rely on either the heavy machinery of indistinguishability obfuscation or witness encryption, or the algebraic structure of bilinear pairing groups. More generally, for an arbitrary number of roundsk, all previous constructions ofk-round semi-honest MPC require at least OT withrounds for.In the setting of malicious security, we show: For any,k-round malicious OT isnecessary and completefork-round malicious MPC. In fact, OT satisfying a weaker notion ofdelayed-semi-malicioussecurity suffices. In the common reference string model, for any, we obtaink-round malicious Universal Composable (UC) protocols from anyk-round semi-malicious OT and non-interactive zero-knowledge. Previous 5-round protocols in the plain model, and 2-round protocols in the common reference string model all require algebraic assumptions such as DDH or LWE.At the core of our constructions is a new framework forgarbling interactive circuits. Roughly speaking, it allows for garbling interactive machines that participates in interactions of a special form. The garbled machine can emulate the original interactions receiving messages sent in theclear(without being encoded using secrets), and reveals only the transcript of the interactions, provided that the transcript iscomputationally uniquely defined. We show that garbled interactive circuits for the purpose of constructing MPC can be implemented using OT. Along the way, we also propose a new primitive ofwitness selectorthat strengthens witness encryption, and a new notion ofzero-knowledge functional commitments.