Our main result is a characterization of VGB security, in all these cases, in terms of an indistinguishability-preserving notion of security, called $\Gamma^*-s-\textsf{IND}-\textsf{PRE}$ security, formulated using an extension of the recently proposed Cryptographic Agents framework (Agrawal et al., 2015). We further show that this definition is equivalent to an indistinguishability based security definition that is restricted to 'concentrated' distributions (wherein the outcome of any computation on encrypted data is essentially known ahead of the computation).
A result of Bitansky et al. (2014), who showed that VGB obfuscation is equivalent to strong indistinguishability obfuscation (SIO), is obtained by specializing our result to obfuscation. Our proof, while sharing various elements from the proof of Bitansky et al., is simpler and significantly more general, as it uses $\Gamma^*-s-\textsf{IND}-\textsf{PRE}$ security as an intermediate notion. Our characterization also shows that the semantic security for graded encoding schemes (Pass et al. 2014), is in fact an instance of this same definition.
We also present a composition theorem for rtestfamily-sINDPRE security. We can then recover the result of Bitansky et al. (2014) regarding the existence of VGB obfuscation for all NC1 circuits, simply by instantiating this composition theorem with a reduction from obfuscation of NC1 circuits to graded encoding schemas (Barak et al., 2014) and the assumption that there exists an $\Gamma^*-s-\textsf{IND}-\textsf{PRE}$ secure scheme for the graded encoding schema (Pass et al. 2014).
Category / Keywords: cryptographic agents, obfuscation, simulation-based security, indistinguishability-preserving security, concentrated distribution, composition theorem Original Publication (in the same form): IACR-TCC B--2016 Date: received 23 Aug 2016, last revised 26 Aug 2016 Contact author: sagrawal at cs utexas edu, mmp@illinois edu, cyu17@illinois edu Available format(s): PDF | BibTeX Citation Version: 20160826:190625 (All versions of this report) Short URL: ia.cr/2016/819 Discussion forum: Show discussion | Start new discussion