[BGLPT15] Succinct Randomized Encodings and their Applications
Authors: Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, Sidharth Telang | Venue: STOC 2015 | Source
Abstract
A randomized encoding allows to express a “complex” computation, given by a function and input , by a “simple to compute” randomized representation whose distribution encodes , while revealing nothing else regarding and . 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: the time required to encode. We construct succinct randomized encodings where the time to encode a computation, given by a program and input , is essentially independent of ‘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 , 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:
- Succinct indistinguishability obfuscation, where the obfuscated program computes the same function as for inputs of apriori-bounded size. Obfuscating is roughly as fast as encoding the computation of on any such input . Here we also require subexponentially-secure indistinguishability obfuscation for circuits.
- Succinct functional encryption, where a functional decryption key corresponding to allows decrypting from encryptions of any plaintext of apriori-bounded size. Key derivation is as fast as encoding the corresponding computation.
- Succinct reusable garbling, a stronger form of randomized encodings where any number of inputs can be encoded separately of , independently of ‘s time and space complexity.
- Publicly-verifiable 2-message delegation where verifying the result of a long computation given by and input 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.
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.
BibTeX
@Inproceedings{STOC:BGLPT15,
author = {Nir Bitansky and Sanjam Garg and Huijia Lin and Rafael Pass and Sidharth Telang},
title = {Succinct Randomized Encodings and their Applications},
pages = {439--448},
editor = {Rocco A. Servedio and Ronitt Rubinfeld},
booktitle = {47th Annual {ACM} Symposium on Theory of Computing},
address = {Portland, OR, USA},
month = {jun~14--17},
publisher = {{ACM} Press},
year = {2015},
doi = {10.1145/2746539.2746574},
}