Output Compression, MPC, and iO for Turing Machines
Output Compression, MPC, and iO for Turing Machines
复制标题
图灵机的输出压缩、MPC 和 iO
DOI：
10.1007/978-3-030-34578-5_13
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Waters, Brent
中科院分区：
文献类型：
--
作者：
Badrinarayanan, S.;Fernando, R.;Koppula, Venkata;Sahai, Amit;Waters, Brent
本文在共享随机模型下，研究了图灵机输出压缩随机编码这一有趣的概念。在这个模型中，编码器和解码器都可以访问一个共享的随机串，效率要求是，编码的大小必须与图灵机在给定输入上的运行时间和输出长度无关，而共享随机串的长度允许随着输出的长度而增长。我们展示了如何在共享随机模型中为图灵机构造输出压缩随机编码，假设电路的iO和集合LWE，DDH，NResiduosity中的任何假设。然后，我们展示了上述结果对安全多方计算（MPC）和不可混淆性混淆（iO）领域的基本可行性问题的有趣影响：1.随机预言机模型中图灵机的紧凑MPC。在MPC的背景下，我们考虑以下基本可行性问题：是否存在用于图灵机的恶意安全MPC协议，当在所有各方的组合输入上执行时，其通信复杂度与图灵机的运行时间和输出长度无关？我们称这种协议为acompactMPC协议。Hubácek和Wichs [HW 15]通过不可压缩性论证表明，即使对于电路的限制设置，也不可能在通信复杂度与输出长度无关的普通模型中构建恶意安全的两方计算协议。在这项工作中，我们展示了如何通过编译任何（非紧凑的）MPC协议到随机Oracle模型中的图灵机的MPC协议，假设在共享随机性模型中输出压缩随机化编码。2.共享随机性模型中的图灵机的简洁iO在图灵机的iO的所有现有构造中，混淆的程序的大小随着输入长度的界限而增长。在这项工作中，我们展示了如何构建一个IO计划图灵机的共享随机性模型的混淆程序的大小是独立的输入长度上的约束，假设IO电路和任何假设中的setLWE，DDH，NResiduosity。
In this work, we study the fascinating notion of output-compressing randomized encodings for Turing Machines, in ashared randomness model. In this model, the encoder and decoder have access to a shared random string, and the efficiency requirement is, the size of the encoding must be independent of the running time and output length of the Turing Machine on the given input, while the length of the shared random string is allowed to grow with the length of the output. We show how to construct output-compressing randomized encodings for Turing machines in the shared randomness model, assuming iO for circuits and any assumption in the setLWE, DDH, NResiduosity.We then show interesting implications of the above result to basic feasibility questions in the areas of secure multiparty computation (MPC) and indistinguishability obfuscation (iO):1.Compact MPC for Turing Machines in the Random Oracle Model.In the context of MPC, we consider the following basic feasibility question: does there exist a malicious-secure MPC protocol for Turing Machines whose communication complexity is independent of the running time and output length of the Turing Machine when executed on the combined inputs of all parties? We call such a protocol as acompactMPC protocol. Hubácek and Wichs [HW15] showed via an incompressibility argument, that, even for the restricted setting of circuits, it is impossible to construct a malicious secure two party computation protocol in the plain model where the communication complexity is independent of the output length. In this work, we show how to evade this impossibility by compiling any (non-compact) MPC protocol in the plain model to acompactMPC protocol for Turing Machines in the Random Oracle Model, assuming output-compressing randomized encodings in the shared randomness model.2.Succinct iO for Turing Machines in the Shared Randomness Model.In all existing constructions of iO for Turing Machines, the size of the obfuscated program grows with a bound on the input length. In this work, we show how to construct an iO scheme for Turing Machines in the shared randomness model where the size of the obfuscated program is independent of a bound on the input length, assuming iO for circuits and any assumption in the setLWE, DDH, NResiduosity.
登录
查看更多内容
图灵机 iO 的简单构建
DOI：
10.1007/978-3-030-03810-6_16
发表时间：
2018
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Sanjam Garg;Akshayaram Srinivasan
通讯作者：
Akshayaram Srinivasan
DOI：
10.1145/2746539.2746574
发表时间：
2015
期刊：
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Nir Bitansky;Sanjam Garg;Sidharth Telang
通讯作者：
Sidharth Telang
DOI：
10.1007/978-3-319-70500-2_25
发表时间：
2017-11
期刊：
--
影响因子：
--
作者：
S. Badrinarayanan;Vipul Goyal;Abhishek Jain;Dakshita Khurana;A. Sahai
通讯作者：
S. Badrinarayanan;Vipul Goyal;Abhishek Jain;Dakshita Khurana;A. Sahai
DOI：
10.1007/978-3-030-03810-6_17
发表时间：
2018-11
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
P. Ananth;Alex Lombardi
通讯作者：
P. Ananth;Alex Lombardi
重温乱码 RAM
DOI：
10.1007/978-3-642-55220-5_23
发表时间：
2014
期刊：
2013 IEEE 26th Computer Security Foundations Symposium
影响因子：
--
作者：
Craig Gentry;S. Halevi;Steve Lu;R. Ostrovsky;Mariana Raykova;Daniel Wichs
通讯作者：
Daniel Wichs