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 $\Pi$ and input $x$, is essentially independent of $\Pi$'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 $(\Pi,x)$, 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 $iO({\Pi})$ computes the same function as $\Pi$ for inputs $x$ of apriori-bounded size. Obfuscating $\Pi$ is roughly as fast as encoding the computation of $\Pi$ on any such input $x$. Here we also require subexponentially-secure indistinguishability obfuscation for circuits. \item Succinct functional encryption, where a functional decryption key corresponding to $\Pi$ allows decrypting $\Pi(x)$ from encryptions of any plaintext $x$ 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 $x$ can be encoded separately of $\Pi$, independently of $\Pi$'s time and space complexity. \item Publicly-verifiable 2-message delegation where verifying the result of a long computation given by $\Pi$ and input $x$ 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.
Category / Keywords: obfuscation, randomized encoding, garbling, functional encryption, delegation Original Publication (with major differences): STOC 15'