Cryptology ePrint Archive: Report 2016/226

On Statistically Secure Obfuscation with Approximate Correctness

Zvika Brakerski and Christina Brzuska and Nils Fleischhacker

Abstract: Goldwasser and Rothblum (TCC '07) prove that statistical indistinguishability obfuscation (iO) cannot exist if the obfuscator must maintain perfect correctness (under a widely believed complexity theoretic assumption: $\NP \not\subseteq \SZK\subseteq\AM\cap\co\AM$). However, for many applications of iO, such as constructing public-key encryption from one-way functions (one of the main open problems in theoretical cryptography), \emph{approximate} correctness is sufficient. It had been unknown thus far whether statistical approximate iO (saiO) can exist.

We show that saiO does not exist, even for a minimal correctness requirement, if $\NP \not\subseteq \AM\cap\co\AM$, and if one-way functions exist. A simple complementary observation shows that if one-way functions do not exist, then average-case saiO exists. Technically, previous approaches utilized the behavior of the obfuscator on \emph{evasive} functions, for which saiO always exists. We overcome this barrier by using a PRF as a ``baseline'' for the obfuscated program.

We broaden our study and consider relaxed notions of \emph{security} for iO. We introduce the notion of \emph{correlation obfuscation}, where the obfuscations of equivalent circuits only need to be mildly correlated (rather than statistically indistinguishable). Perhaps surprisingly, we show that correlation obfuscators exist via a trivial construction for some parameter regimes, whereas our impossibility result extends to other regimes. Interestingly, within the gap between the parameters regimes that we show possible and impossible, there is a small fraction of parameters that still allow to build public-key encryption from one-way functions and thus deserve further investigation.

Category / Keywords: foundations / obfuscation, approximate iO, statistical iO

Original Publication (with minor differences): IACR-CRYPTO-2016

Date: received 1 Mar 2016, last revised 9 Jun 2016

Contact author: fleischhacker at cs uni-saarland de

Available format(s): PDF | BibTeX Citation

Version: 20160609:121835 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]