From Indistinguishability Obfuscation to One-Way Functions
Indistinguishability Obfuscation
A PPT algorithm is said to be an indistinguishability obfuscator for if it satisfies:
Functionality: For any ,
Indistinguishability: For any (not necessarily uniform) PPT distinguisher , there exists a negligible function such that the following holds: For all security parameters for all pairs of circuits we have that if for all inputs , then
One-way Function
A family, of efficiently computable functions is said to be one-way if for all PPT adversaries , the exists a negligible function such that for every security parameter :
where and are uniformly chosen in their corresponding domains.
From iO to OWF
Let be a canonical constant zero circuit with inputs of bits padded to gates.
Let be the corresponding (efficiently computable) family of functions.
Theorem: If then is a family of one-way functions.
Suppose, in contradiction, that is not one-way. Then there exists a PPT adversary who can invert (for all ) with probability such that is some inverse polynomial in Let and define
This is the difference in the probability that successfully finds a preimage for with respect to when it is given a random obfuscation of the circuit (i.e., a random element in the image of ) and when is given a random obfuscation of the circuit Note that obfuscations of might not even be in the image of However, the following claim asserts that this happens with negligible probability for s that implement the zero function:
Claim 1: For all , every PPT and every circuit with gates that implements the constant zero function for inputs of bits, where is a negligible function.
: This follows immediately from the security of the obfuscation scheme. since and have identical functionality and size, it must hold that for every PPT :
Taking to be the algorithm that runs and outputs 1 iff we get a distinguisher for obfuscations of and with advantage .
On the other hand, for any circuit that does not implement the constant zero function, there will never be a preimage under .
Claim 2: For all , every PPT A and every circuit with gates such that it holds that
: This claim follows immediately from the functionality property of the obfuscation algorithm: since the output of the obfuscator is a circuit that has identical functionality to the input circuit, the output of cannot be a circuit that implements the constant zero function. Thus, it cannot be in the image of (Note that for this argument to hold, it is critical that the obfuscator perfectly preserve functionality).
Given a Circuit-SAT instance on variables with gates, we will now use to (one-sided) probabilistically decide if is satisfiable with inverse polynomial advantage:
If is unsatisfiable, then it implements the constant zero function. Hence, by Claim 1 it follows that the condition in line 5 will be true with probability independently in each iteration (since we choose and s uniformly at random and independently in each iteration of the loop). The probability that it fails in all iterations is which is negligible. Thus, in this case the algorithm will return "Unsatisfiable" with all but negligible probability.
If is satisfiable, by Claim 2 the inverting adversary will never succeed, hence with probability 1 the algorithm will output "Satisfiable"
Remarks
Barak et al. showed that iO is always realizable, albeit inefficiently: the iO can simply canonicalize the input circuit C by outputting the lexicographically first circuit that computes the same function.
If P = NP then one-way functions do not exist but iO does exist (since the lexicographically first circuit that computes the same function can be found efficiently). Therefore, we do not expect to build many “cryptographically interesting” tools just from iO, but usually need to combine it with other assumptions. (One exception is witness encryption , which can be constructed from iO alone.) It is known that iO can be combined with one-way functions (OWFs) to construct many powerful primitives such as public-key encryption, identity-based encryption, attribute- based encryption (via witness encryption), as well as NIZKs, CCA encryption, deniable encryption, and two message multi-party computation. However, it is still not clear whether assuming one-way functions is actually necessary for any of the above applications.
The existence of iO, combined with the assumption that (a worst-case hardness assumption) implies the existence of one-way functions (an average-case hardness assumption).
If is achievable, then Impagliazzo's five worlds collapse to two: we are either in Algorithmica, where , or in Cryptomania, where public-key encryption is possible. Minicrypt, where one-way functions exist but public-key encryption is not possible, is ruled out due to the existing constructions of public-key crypto from and one-way functions. Result here rules out Pessiland, where BPP but one-way functions do not exist, and Heuristica, where NP problems are hard in the worst case but easy on average. It is an interesting question whether an approximate version of iO also implies one-way functions.