# Indistinguishability obfuscation and PRFs

Consider a family of pseudorandom functions $$F$$, each member $$f_k$$ of this family is indexed by a key $$k$$. It is true, due to a result by Barak et al, that black box obfuscation is not possible for a generic family of this type.

However, is it possible to apply something like indistinguishability obfuscation ($$\mathsf{iO}$$) to "special classes" of pseudorandom functions and still have the obfuscated circuit retain its "pseudorandom properties"?

Here is the functionality I want.

I randomly pick an $$f_k$$ from the family and then get the description of some circuit $$D = \mathsf{iO}(f_k)$$ using indistinguishability obfuscation. Then, if I describe $$D$$ to the adversary, I want it to be computationally equivalent to just giving the adversary black box access to a random function.

I looked in the literature, and it seems like a special class of pseudorandom functions, called punctured PRFs, that have some properties similar to what I am looking for. But, the paper I linked seems to only be a partial proof. Is the functionality I want believed to be true in cryptography or is it too pie-in-the-sky?

• A random function does not have any polynomial-sized circuit, with overwhelming probability. But you want to give out a polynomial-sized circuit computing the function in question. So it is not possible for your scenario to be "equivalent" to black box access to a random function. As soon as you start defining "equivalent" a bit more formally, you will probably run into the Barak et al. impossibility. Sep 10, 2022 at 3:00
• The impossibility result you mention is about virtual black-box obfuscation, which is a very strong notion. Indistinguishability obfuscation is possible using enough computational assumptions (dl.acm.org/doi/10.1145/3406325.3451093). However, like @Mikero mentionned, this is not at all equivalent to giving the adversary black-box access to a random function (even pseudo-random). Oct 5, 2023 at 21:00

Assuming that $$f_k$$ and $$f_j$$ from the family of functions $$F$$ perform identical computation (but with different seeds as input), then indistinguishability obfuscation would imply that an adversary would not be able to differentiate $$f_k$$ and $$f_j$$ (other than noting differences in input and output). Describing it as black-box access would be incorrect because it would potentially reveal details of the computation being performed. However, it would continue to retain the same input-output mapping of the original function (hence retaining pseudorandomness).
In other words, $$f_k$$ and $$f_j$$ would appear indistinguishable (other than noting differences in input and output) and as such a CSPRNG $$f_k$$ would be equivalent to $$iO(f_k)$$ in security. The security of $$iO(f_k)$$ is only as great as that of $$f_k$$. If the length of the circuit $$f_k$$ was equal to $$n$$, then the adversary would need $$O(n)$$ operations to brute-force either of these functions.
• Sorry, but this makes no sense to me. To functions $f_k$ and $f_j$ from the PRF family will, with overwhelming probability, not be functionally equivalent. iO only implies indistinguishability when used to obfuscate functionally equivalent programs -- i.e., programs with exactly the same input-output behavior. Given that, I can't make sense of the sentence "indistinguishability obfuscation would imply that an adversary would not be able to differentiate $f_k$ and $f_j$ (other than noting differences in input and output)". Jun 8, 2023 at 8:38