Authors
Saikrishna Badrinarayanan, Rex Fernando, Venkata Koppula, Amit Sahai, Brent Waters
Publication date
2019/11/25
Book
International Conference on the Theory and Application of Cryptology and Information Security
Pages
342-370
Publisher
Springer International Publishing
Description
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, N 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. 1.
    Compact MPC for Turing Machines in the Random Oracle …
Total citations
201920202021202220231113
Scholar articles
S Badrinarayanan, R Fernando, V Koppula, A Sahai… - International Conference on the Theory and …, 2019