Paper 2015/356

Succinct Randomized Encodings and their Applications

Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, and Sidharth Telang

Abstract

A {\em randomized encoding} allows to express a ``complex'' computation, given by a function $f$ and input $x$, by a ``simple to compute'' randomized representation $\hat{f}(x)$ whose distribution encodes $f(x)$, while revealing nothing else regarding $f$ and $x$. Existing randomized encodings, geared mostly to allow encoding with low parallel-complexity, have proven instrumental in various strong applications such as multiparty computation and parallel cryptography. This work focuses on another natural complexity measure: {\em the time required to encode}. We construct {\em succinct randomized encodings} where the time to encode a computation, given by a program $$ and input $$, is essentially independent of $$'s time complexity, and only depends on its space complexity, as well as the size of its input, output, and description. The scheme guarantees computational privacy of $$, and is based on indistinguishability obfuscation for a relatively simple circuit class, for which there exist instantiations based on polynomial hardness assumptions on multi-linear maps. We then invoke succinct randomized encodings to obtain several strong applications, including: \begin{itemize} \item Succinct indistinguishability obfuscation, where the obfuscated program $$ computes the same function as $$ for inputs $$ of apriori-bounded size. Obfuscating $$ is roughly as fast as encoding the computation of $$ on any such input $$. Here we also require subexponentially-secure indistinguishability obfuscation for circuits. \item Succinct functional encryption, where a functional decryption key corresponding to $$ allows decrypting $$ from encryptions of any plaintext $$ of apriori-bounded size. Key derivation is as fast as encoding the corresponding computation. \item Succinct reusable garbling, a stronger form of randomized encodings where any number of inputs $$ can be encoded separately of $$, independently of $$'s time and space complexity. \item Publicly-verifiable 2-message delegation where verifying the result of a long computation given by $$ and input $$ is as fast as encoding the corresponding computation. We also show how to transform any 2-message delegation scheme to an essentially non-interactive system where the verifier message is reusable. \end{itemize} Previously, succinct randomized encodings or any of the above applications were only known based on various non-standard knowledge assumptions. At the heart of our techniques is a generic method of compressing a piecemeal garbled computation, without revealing anything about the secret randomness utilized for garbling.