[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},
}