Paper 2018/866
Output Compression, MPC, and iO for Turing Machines
Saikrishna Badrinarayanan, Rex Fernando, Venkata Koppula, Amit Sahai, and Brent Waters
Abstract
In this work, we study the fascinating notion of outputcompressing randomized encodings for Turing Machines, in a shared 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 set {LWE, DDH, Nth Residuosity}. 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 malicioussecure 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 a compact MPC protocol. Hubacek 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 (noncompact) MPC protocol in the plain model to a compact MPC protocol for Turing Machines in the Random Oracle Model, assuming outputcompressing 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 set {LWE, DDH, Nth Residuosity}.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A major revision of an IACR publication in ASIACRYPT 2019
 Keywords
 Randomized encodingscompact MPCindistinguishability obfuscation
 Contact author(s)
 bsaikrishna7393 @ gmail com
 History
 20191018: revised
 20180922: received
 See all versions
 Short URL
 https://ia.cr/2018/866
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/866, author = {Saikrishna Badrinarayanan and Rex Fernando and Venkata Koppula and Amit Sahai and Brent Waters}, title = {Output Compression, MPC, and iO for Turing Machines}, howpublished = {Cryptology ePrint Archive, Paper 2018/866}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/866}}, url = {https://eprint.iacr.org/2018/866} }