IACR News item: 30 September 2014
Nir Bitansky, Sanjam Garg, Sidharth Telang
ePrint ReportThis 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.
Additional news items may be found on the IACR news page.