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.Category / Keywords: Date: received 3 Jun 2016, withdrawn 14 Aug 2016 Contact author: segev at cs huji ac il Available format(s): (-- withdrawn --) Version: 20160814:111824 (All versions of this report) Short URL: ia.cr/2016/576 Discussion forum: Show discussion | Start new discussion