1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Mikero
    Sep 10, 2022 at 3:00
  • $\begingroup$ 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). $\endgroup$
    – lamontap
    Oct 5, 2023 at 21:00

1 Answer 1

0
$\begingroup$

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).

This would be equivalent to providing the adversary a PRNG. With a PRNG details of the computation being performed are revealed. What makes a CSPRNG secure typically is that despite knowing details of the computation being performed it is not feasible to predict what input would derive which output in advance (without running the function with the input till it outputs the desired result).

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.

$\endgroup$
1
  • $\begingroup$ 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)". $\endgroup$ Jun 8, 2023 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.