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 parallelcomplexity, 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 $\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 multilinear 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 aprioribounded size. Obfuscating $\Pi$ is roughly as fast as encoding the computation of $\Pi$ on any such input $x$. Here we also require subexponentiallysecure 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 aprioribounded 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 Publiclyverifiable 2message 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 2message delegation scheme to an essentially noninteractive 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 nonstandard 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.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. MAJOR revision.STOC 15'
 DOI
 10.1145/2746539.2746574
 Keywords
 obfuscationrandomized encodinggarblingfunctional encryptiondelegation
 Contact author(s)
 nirbitan @ csail mit edu
 History
 20150423: received
 Short URL
 https://ia.cr/2015/356
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/356, author = {Nir Bitansky and Sanjam Garg and Huijia Lin and Rafael Pass and Sidharth Telang}, title = {Succinct Randomized Encodings and their Applications}, howpublished = {Cryptology ePrint Archive, Paper 2015/356}, year = {2015}, doi = {10.1145/2746539.2746574}, note = {\url{https://eprint.iacr.org/2015/356}}, url = {https://eprint.iacr.org/2015/356} }