International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 23 April 2015

Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, Sidharth Telang
ePrint Report ePrint Report
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 $\\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.

Expand

Additional news items may be found on the IACR news page.