×

Output compression, MPC, and iO for Turing machines. (English) Zbl 1483.68103

Galbraith, Steven D. (ed.) et al., Advances in cryptology – ASIACRYPT 2019. 25th international conference on the theory and application of cryptology and information security, Kobe, Japan, December 8–12, 2019. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 11921, 342-370 (2019).
Summary: In this work, we study the fascinating notion of output-compressing 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, \(\mathrm{N}^\mathrm{th}\) 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 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 a compact MPC protocol. P. Hubáček and D. Wichs [in: Proceedings of the 6th conference on innovations in theoretical computer science, ITCS’15. New York, NY: Association for Computing Machinery (ACM). 163–172 (2015; Zbl 1364.68201)] 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 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 set {LWE, DDH, \(\mathrm{N}^\mathrm{th}\) Residuosity}.
For the entire collection see [Zbl 1428.94008].

MSC:

68Q04 Classical models of computation (Turing machines, etc.)
68P25 Data encryption (aspects in computer science)
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
94A29 Source coding
94A60 Cryptography

Citations:

Zbl 1364.68201
PDFBibTeX XMLCite
Full Text: DOI