You are looking at a specific version 20150423:191617 of this paper. See the latest version.

Paper 2014/771

Succinct Randomized Encodings and their Applications

Nir Bitansky and Sanjam Garg and Sidharth Telang

Abstract

A {\em randomized encoding} allows to represent a ``complex'' function $f(x)$ by a ``simpler'' randomized function $\hat{f}(x;r)$ whose output distribution encodes $f(x)$, while revealing nothing else regarding $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 a computation given by a (Turing or random-access) machine $M$, and input $x$, requiring time $t$ and space $s$, can be encoded roughly in time $\poly(|x|,\log t,s)$, thus inducing significant savings in time when $s \ll t$. The scheme guarantees computational input-privacy and is based on indistinguishability obfuscation for a relatively simple circuit class, which can in turn be based on a polynomial version of the subgroup elimination assumption on multilinear graded encodings. We then invoke succinct randomized encodings to obtain several strong applications, including: \begin{itemize} \item Indistinguishability obfuscation for uniform (Turing or random-access) machines, where the obfuscated machine $\iO(M)$ computes the same function as $M$ for inputs $x$ of apriori-fixed maximal size $n$, and is computed in time $\poly(n,\log t,s)$. \item Functional encryption for uniform machines, where a functional decryption key corresponding to $M$ allows decrypting $M(x)$ from encryptions of $x$. As in the previous case, inputs $x$ are of apriori-fixed maximal size $n$, and key derivation time is roughly $\poly(n,\log t,s)$. \item Publicly-verifiable 2-message delegation where verification time is roughly $\poly(n,\log t,s)$. 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} For the first application, we also require subexponentially-secure indistinguishability obfuscation for circuits, and for the second polynomial indistinguishability obfuscation, which can be replaced by more concrete polynomial hardness assumptions on multilinear graded-encodings. Previously, both applications were only known based on various non-standard knowledge assumptions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
ObfuscationRandomized-EncodingGarbled-CircuitFunctional-EncryptionSNARGdelegation
Contact author(s)
nirbitan @ csail mit edu
History
2015-04-23: revised
2014-09-30: received
See all versions
Short URL
https://ia.cr/2014/771
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.