On the Power of Secure Two-Party Computation
On the Power of Secure Two-Party Computation
复制标题
论安全两方计算的威力
DOI：
--
复制
发表时间：
2016
影响因子：
3
通讯作者：
Muthuramakrishnan Venkitasubramaniam
中科院分区：
文献类型：
--
作者：
Carmit Hazay;Muthuramakrishnan Venkitasubramaniam
Ishai, Kushilevitz， Ostrovsky和Sahai （STOC 2007; SIAM J computer 39(3): 1121-1152, 2009）介绍了强大的“MPC-in-the-head”技术，该技术以“黑盒”方式将信息论MPC协议从被动对手安全转换为ZK证明。在这项工作中，我们扩展了这一技术，并在所谓的记忆转移混合模型中提供了任何半诚实的安全两方计算（2PC）协议（具有温和的自适应安全保证）的通用转换，以适用于任何NPdocumentclass[12pt]{minimal} uspackage {amsmath} uspackage {wasysym} uspackage {amsfonts} uspackage {amssymb} uspackage {amssyb} uspackage {mathrsfs} uspackage {upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ extsf {NP}$$end{document}语言，以“黑盒”的方式假设只有单向函数。我们基于goldreich - micli - wigderson的2PC协议的基本构造产生了一个自适应ZK证明，其通信复杂度与实现NPdocumentclass[12pt]{minimal} uspackage {amsmath} uspackage {wasysym} uspackage {amsfonts} uspackage {amssymb} uspackage {mathrsfs} uspackage {upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ extsf {NP}$$end{document}关系的电路大小成二次比例。以前这样的证明依赖于NPdocumentclass[12pt]{minimal} uspackage {amsmath} uspackage {wasysym} uspackage {amsfonts} uspackage {amssymb} uspackage {amssymb} uspackage {upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ extsf {NP}$$end{document}语言来图哈密tonicity [Lindell and Zarosim (TCC 2009; J Cryptol 24(4): 761-799, 2011)]。作为我们技术的一个应用，我们展示了如何为任何NPdocumentclass[12pt]{minimal} uspackage {amsmath} uspackage {wasysym} uspackage {amsfonts} uspackage {amssymb} uspackage {mathrsfs} uspackage {upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ extsf {NP}$$end{document}语言获得具有“输入延迟”属性的ZK证明，而不依赖于昂贵的Karp约简，即底层单向函数中的黑盒子。也就是说，输入延迟属性允许诚实的证明者的算法接收到只在最后一轮被证明的实际陈述。我们进一步推广这一点，以获得具有相同属性的“提交-证明”协议，其中证明者在第二条消息中向证人w提交，并在零知识中证明关于证人w的陈述x，其中陈述仅在最后一轮中确定。这改进了先前Lapidot和Shamir （Crypto 1990）的构造，该构造是专门为图哈密性问题设计的，并且以非黑盒的方式依赖于底层原语。此外，我们还提供了一个通用的转换，从任意2PC协议构建函数f的随机编码，从而安全地从单向函数中计算相关功能（以黑盒方式）。我们证明，如果2PC协议具有温和的自适应安全保证（姚协议和GMW协议都满足），那么产生的随机编码可以分解为离线/在线编码。
Ishai, Kushilevitz, Ostrovsky and Sahai (STOC 2007; SIAM J Comput 39(3):1121–1152, 2009) introduced the powerful “MPC-in-the-head” technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a “black-box” way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so-called oblivious-transfer hybrid model to an adaptive ZK proof for any NPdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ extsf {NP}$$end{document} language, in a “black-box” way assuming only one-way functions. Our basic construction based on Goldreich–Micali–Wigderson’s 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the NPdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ extsf {NP}$$end{document} relation. Previously such proofs relied on an expensive Karp reduction of the NPdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ extsf {NP}$$end{document} language to Graph Hamiltonicity [Lindell and Zarosim (TCC 2009; J Cryptol 24(4):761–799, 2011)]. As an application of our techniques, we show how to obtain a ZK proof with an “input-delayed” property for any NPdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$ extsf {NP}$$end{document} language without relying on expensive Karp reductions that is black box in the underlying one-way function. Namely, the input-delayed property allows the honest prover’s algorithm to receive the actual statement to be proved only in the final round. We further generalize this to obtain a “commit-and-prove” protocol with the same property where the prover commits to a witness w in the second message and proves a statement x regarding the witness w in zero-knowledge where the statement is determined only in the last round. This improves a previous construction of Lapidot and Shamir (Crypto 1990) that was designed specifically for the Graph Hamiltonicity problem and relied on the underlying primitives in a non-black-box way. Additionally, we provide a general transformation to construct a randomized encoding of a function f from any 2PC protocol that securely computes a related functionality (in a black-box way) from one-way functions. We show that if the 2PC protocol has mild adaptive security guarantees (which are satisfied by both the Yao’s and GMW’s protocol), then the resulting randomized encoding can be decomposed to an offline/online encoding.