Return to Answer

Barak et al. study in this paper the possibility of achieving even stronger notions of obfuscation (such as virtual grey box obfuscation, or virtual black box obfuscation) for the class of evasive functions. A class of function is evasive if, for any fixed input $x$, a random function from the class evaluates to $0$ on $x$ with overwhelming probability. While their results are mainly negative, Barak et al. also provide an interesting positive result: under a new perfectly-hiding multilinear encoding assumption, which is the same kind of assumption that is used in construction of iO schemes (hence suffer from comparable weaknesses and gives comparable (in)efficiency), there exists a virtual black box obfuscator for evasive functions that test if a low-degree polynomial evaluates to zero modulo some large prime. Virtual black box obfuscation is the ultimate security notion for obfuscation: while iO states that it should be infeasible to distinguish two functionally equivalent obfuscated circuits, VBB states that everything that the adversary sees, given the VBB obfuscation of the function, can be simulated given only black-box access to the function. It is known that VBB is in general impossible to achieve; hence, this work shows that this impossibility does not seem to hold anymore for this restricted class of evasive functions.

Barak et al. study in this paper the possibility of achieving even stronger notions of obfuscation (such as virtual grey box obfuscation, or virtual black box obfuscation) for the class of evasive functions. A class of function is evasive if, for any fixed input $x$, a random function from the class evaluates to $0$ on $x$ with overwhelming probability. While their results are mainly negative, Barak et al. also provide an interesting positive result: under a new perfectly-hiding multilinear encoding assumption, which is the same kind of assumption that is used in constructions of iO schemes (hence suffers from comparable weaknesses and gives comparable (in)efficiency), there exists a virtual black box obfuscator for evasive functions that tests if a low-degree polynomial evaluates to zero modulo some large prime. Virtual black box obfuscation is the ultimate security notion for obfuscation: while iO states that it should be infeasible to distinguish two functionally equivalent obfuscated circuits, VBB states that everything that the adversary sees, given the VBB obfuscation of the function, can be simulated given only black-box access to the function. It is known that VBB is in general impossible to achieve; hence, this work shows that this impossibility does not seem to hold anymore for this restricted class of evasive functions.

However, as far as we know, it is perfectly possible that all efficiently computable functions (hence in particular all functions you are interested about) can be obfuscated with an iO scheme. We have a bunch of concrete candidates, and there has been a large body of work on the underlying assumptions. Providing a complete treatment would be out of scope for this question (I count more than 160 papers on the subject since 2013), but roughly, all known constructions of iO rely on exotic assumptions: either the existence of graded encoding schemes, whose security is poorly understood and with many (many) existing attacks, the latest being this one, or recent assumptions regarding the weak pseudorandomness of some extreme families of low depth pseudorandom generators -- some assumptions made in the three latest results in this area have already been broken. Furthermore, none of the iO schemes we currently know of would be concretely efficient. Still, as a theoretical feasibility result, all functions you care about can be obfuscated (under exotic assumptions), where the obfuscation security notion is that of indistinguishability obfuscation.

However, as far as we know, it is perfectly possible that all efficiently computable functions (hence in particular all functions you are interested about) can be obfuscated with an iO scheme. We have a bunch of concrete candidates, and there has been a large body of work on the underlying assumptions. Providing a complete treatment would be out of scope for this question (I count more than 160 papers on the subject since 2013), but roughly, all known constructions of iO rely on exotic assumptions: either the existence of graded encoding schemes, whose security is poorly understood and with many (many) existing attacks, the latest being this one, or recent assumptions regarding the weak pseudorandomness of some extreme families of low depth pseudorandom generators -- some assumptions made in the three latest results (1, 2, 3) in this area have already been broken. Furthermore, none of the iO schemes we currently know of would be concretely efficient. Still, as a theoretical feasibility result, all functions you care about can be obfuscated (under exotic assumptions), where the obfuscation security notion is that of indistinguishability obfuscation.

From Indistinguishability Obfuscation

However, as far as we know, it is perfectly possible that all efficiently computable functions (hence in particular all functions you are interested about) can be obfuscated with an iO scheme. We have a bunch of concrete candidates, and there has been a large body of work on the underlying assumptions. Providing a complete treatment would be out of scope for this question (I count more than 160 papers on the subject since 2013), but roughly, all known constructions of iO rely on exotic assumptions: either the existence of graded encoding schemes, whose security is poorly understood and with many (many) existing attacks, the latest being this one, or recent assumptions regarding the weak pseudorandomness of some extreme families of low depth pseudorandom generators -- some assumptions made in the three latest results in this area have already been broken. Furthermore, none of the iO scheme we currently know of would be concretely efficient. Still, as a theoretical feasibility result, all functions you care about can be obfuscated (under exotic assumptions), where the obfuscation security notion is that of indistinguishability obfuscation.

From Multilinear Maps

From LWE

1. Conjunctions. Several papers have proposed scheme to obfuscate functions of the form

From Group-Based Assumptions

From One-Way Functions

Underlying assumptions: exponentially strong one-way functions, or one-way permutations

From Indistinguishability Obfuscation

However, as far as we know, it is perfectly possible that all efficiently computable functions (hence in particular all functions you are interested about) can be obfuscated with an iO scheme. We have a bunch of concrete candidates, and there has been a large body of work on the underlying assumptions. Providing a complete treatment would be out of scope for this question (I count more than 160 papers on the subject since 2013), but roughly, all known constructions of iO rely on exotic assumptions: either the existence of graded encoding schemes, whose security is poorly understood and with many (many) existing attacks, the latest being this one, or recent assumptions regarding the weak pseudorandomness of some extreme families of low depth pseudorandom generators -- some assumptions made in the three latest results in this area have already been broken. Furthermore, none of the iO schemes we currently know of would be concretely efficient. Still, as a theoretical feasibility result, all functions you care about can be obfuscated (under exotic assumptions), where the obfuscation security notion is that of indistinguishability obfuscation.

##From Multilinear Maps##

##From LWE##

1. Conjunctions. Several papers have proposed schemes to obfuscate functions of the form

##From Group-Based Assumptions##

##From One-Way Functions##

Underlying assumptions: exponentially strong one-way functions, one-way permutations, or deterministic encryption