Indistinguishability Obfuscation Does Not Reduce to Structured Languages
We prove that indistinguishability obfuscation (iO) and one-way functions do not naturally reduce to any language within NP∩coNP. This is proved within the framework introduced by Asharov and Segev (FOCS ’15) that captures the vast majority of techniques that have been used so far in iO-based constructions. Our approach is based on a two-fold generalization of a classic result due to Impagliazzo and Naor (Structure in Complexity Theory ’88) on non-deterministic computations via decision trees. First, we generalize their approach from the, rather restrictive, model of decision trees to arbitrary computations. Then, we further generalize the argument within the Asharov-Segev framework. Our result explains why iO does not seem to suffice for certain applications, even when combined with the assumption that one-way functions exist. In these cases it appears that additional, more structured, assumptions are necessary. In addition, our result suggests that any attempt for ruling out the existence of iO by reducing it “ad absurdum” to a potentially efficiently-decidable language may encounter significant difficulties. ∗IBM T.J. Watson Research Center. Supported by NSF Grant No. 1017660. Email: gsasharo@us.ibm.com. †Efi Arazi School of Computer Science, IDC Herzliya, Israel. Email: alon.rosen@idc.ac.il. Supported by ISF grant no. 1255/12, NSF-BSF Cyber Security and Privacy grant no. 2014/632, and by the ERC under the EU’s Seventh Framework Programme (FP/2007-2013) ERC Grant Agreement no. 307952. ‡School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem 91904, Israel. Email: segev@cs.huji.ac.il. Supported by the European Union’s 7th Framework Program (FP7) via a Marie Curie Career Integration Grant, by the Israel Science Foundation (Grant No. 483/13), by the Israeli Centers of Research Excellence (I-CORE) Program (Center No. 4/11), by the US-Israel Binational Science Foundation (Grant No. 2014632), and by a Google Faculty Research Award.