Paper 2014/554

On Virtual Grey Box Obfuscation for General Circuits

Nir Bitansky, Ran Canetti, Yael Tauman-Kalai, and Omer Paneth

Abstract

An obfuscator is Virtual Grey Box (VGB) for a class of circuits if, for any and any predicate , deducing given is tantamount to deducing given unbounded computational resources and polynomially many oracle queries to . VGB obfuscation is often significantly more meaningful than indistinguishability obfuscation (IO). In fact, for some circuit families of interest VGB is equivalent to full-fledged Virtual Black Box obfuscation. We investigate the feasibility of obtaining VGB obfuscation for general circuits. We first formulate a natural strengthening of IO, called {\em strong IO} (SIO). Essentially, is SIO for class if whenever the pair is taken from a distribution over where, for all , only with negligible probability. We then show that an obfuscator is VGB for a class if and only if it is SIO for . This result is unconditional and holds for any . We also show that, for some circuit collections, SIO implies virtual black-box obfuscation. Finally, we formulate a slightly stronger variant of the semantic security property of graded encoding schemes [Pass-Seth-Telang Crypto 14], and show that existing obfuscators, such as the obfuscator of Barak et al. [Eurocrypt 14], are SIO for all circuits in NC, assuming that the underlying graded encoding scheme satisfies our variant of semantic security. {\em Put together, we obtain VGB obfuscation for all NC circuits under assumptions that are almost the same as those used by Pass et al. to obtain IO for NC circuits.} We also show that semantic security is in essence {\em necessary} for showing VGB obfuscation.

Note: Noted that a preliminary version appears in the proceedings of crypto.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2014
Keywords
ObfuscationMultilinear Graded EncodingsSemantic SecurityVBBVGB
Contact author(s)
nirbitan @ tau ac il
History
2014-08-05: last of 2 revisions
2014-07-18: received
See all versions
Short URL
https://ia.cr/2014/554
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/554,
      author = {Nir Bitansky and Ran Canetti and Yael Tauman-Kalai and Omer Paneth},
      title = {On Virtual Grey Box Obfuscation for General Circuits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/554},
      year = {2014},
      url = {https://eprint.iacr.org/2014/554}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.