I overheard in a lecture on cryptographic obfuscation that the learnable functions are obfuscable. But to me this seems so counter-intuitive.

Let's take a linear function (as an example of learnable function), then say I am given any obfuscated version of the function, I can always find the original function by querying an oracle having access to the original function- then how did I manage to obfuscate the original learnable function to begin with?


I am not sure what definition of obfuscation you care about, but in cryptography, we usually consider the virtual black-box obfuscation (VBBO) or indistinguishability obfuscation (IO). And as far as I can say, both definitions allow to extract learnable information from the obfuscated program (here learnable means learnable by querying the oracle having access to the original function). That is, the cryptographic obfuscation essentially does not hide anything about the learnable functions.

In other words, the cryptographic obfuscations do not rule out to learn something from the oracle access to the program. Instead, the cryptographic obfuscations do rule out the possibility to learn anything except the oracle access, or input-output behavior of the program. In particular, using the VBBO or IO, it is meaningless to obfuscate the learnable function with respect to security.

Let me briefly describe the (in-)formal definition of VBBO. A compiler $C$ that takes a program $P$ and outputs another program $C(P)$ is called VBBO if the following hold: For any efficient algorithm $A$ that learns anything about $C(P)$, there is a simulator $S$ that learns exactly the same thing only via oracle access to $P$. More formally, it holds that $$\Pr_{C,A} [A(C(P))\rightarrow 1] \approx \Pr_S[S^P ()\rightarrow 1]. $$ I omitted security parameters, negligible difference, etc. This definition does not prevent learning by querying the oracle having access to the original program.

Perhaps you are interested in this discussion.

  • $\begingroup$ I am reading it after few month, and it is the answer I was looking for. Thanks. $\endgroup$
    – DaveIdito
    Mar 13 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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