On Statistically Secure Obfuscation With Approximate Correctness

The existence of indistinguishability obfuscators (iO) will have many sought after consequences. It would be most desirable to achieve statistical iO, where the security properties hold unconditionally without relying on cryptographic assumptions. This would allow, for example, to construct public-key cryptography directly from symmetric-key cryptography, thus resolving one of the main open problems in theoretical cryptography.
It is well established that statistical iO with perfect correctness cannot be constructed (assuming $\mathsf{NP} \not\subseteq \mathsf{SZK}$, a widely believed complexity postulate). However, for cryptographic applications, an approximately correct version of iO, where the functionality of the obfuscated circuit only needs to be preserved in a slightly non-trivial way, suffices. It had thus been an open problem to construct or refute the existence of statistical approximately correct iO (saiO).
In this work, we resolve this question by showing that saiO cannot exist if one-way functions exist (and $\mathsf{NP} \not\subseteq \mathsf{SZK}$). Further, we show that relying on one-way functions is essential since if they do not exist, then we can construct (average-case) saiO in a straightforward manner. Technically, previous works obfuscated evasive functions (which are zero almost everywhere). However, these functions are approximately equal to the zero function, which makes their saiO useless. The heart of our technical contribution is showing how to overcome this barrier by using a PRF as a “baseline” for the obfuscated program.
Another intriguing consequence of our negative result is that constructions of iO in various ideal models (random oracle, generic groups, ideal constant degree graded encodings, and others) are unlikely. Constructions of iO in various ideal models imply saiO in the standard-model and, therefore, due to our result, also $\mathsf{NP} \subseteq \mathsf{SZK}$ or the non-existence of one-way functions.
Finally, we generalize saiO to statistically secure approxiately correct correlation obfuscation (sacO) by parametrizing not only the correctness, but also the security of the obfuscator. We show that for some security and correctness parameters, sacO suffices for cryptographic applications. We then construct sacO for weaker parameters (that seem unlikely to be useful for applications), and we extend our negative to sacO for a large class of parameters. Interestingly, a small range of useful parameters survives. It seems that ruling them out requires new techniques, and it remains an important open question to study sacO in this parameter interval.