3
$\begingroup$

I came across the following quotes in reading papers on obfuscation (1, ibid, and 2):

The next result follows from the fact that point functions are not exactly learnable (since a uniformly chosen point function is statistically indistinguishable from the all-zeroes function given a polynomial number of membership queries).

and

A family of circuits $C \in C_n$ is obfuscatable against general adversaries iff $C$ is (nonuniformly) efficiently and exactly learnable using membership queries.

and

Of course, if the function is (exactly) learnable via oracle queries (i.e., one can acquire a program that computes the function by querying it at a few locations)

What does it mean to say a program is learnable using membership queries? Or alternatively, I've seen it as "learnable with oracle queries". And what is the impact of it? Does it mean that we can learn what exactly the program does or just enter input and receive the result of the program running in each step? Without knowing which mathematical action influenced it?

$\endgroup$
  • $\begingroup$ @Laura, I updated your question to hopefully make it more clear. I'll reopen. If I destroyed the original meaning of the question, please feel free to edit. $\endgroup$ – mikeazo Oct 21 '14 at 17:14
  • $\begingroup$ cleaned up some comments that were no longer needed $\endgroup$ – mikeazo Oct 21 '14 at 19:14
4
$\begingroup$

A family $\mathcal{C}$ of circuits/functions is "learnable with oracle queries" if there is an efficient "learning" algorithm $L$ that, given oracle (or "black box") access to any $C \in \mathcal{C}$, outputs a circuit $C'$ (or other representation) that is equivalent to $C$, i.e., it agrees with $C$ on all inputs.

Oracle ("black box") access to $C$ means that $L$ can repeatedly query any values $x_i$ in the input domain of $C$, and receive $C(x_i)$ as the answer. Note that $L$ does not see how the output value $C(x_i)$ is computed, how many steps it takes to do so, etc. It just gets the value itself.

For example, consider the class of functions $\mathcal{C} = \{C_w(x) = \langle x, w \rangle \bmod 2 \}$. Each function $C_w(x)$ is simply the mod-2 inner product of some fixed $w \in \{0,1\}^n$ with the input $x \in \{0,1\}^n$. (This is often called the class of "parity" functions.) This class is learnable with oracle queries: given oracle access to some $C_w$ (where $w$ is initially unknown), the learning algorithm simply queries its oracle on $e_1=(1,0,\ldots,0)$, and receives $C_w(e_1) = \langle e_1,w\rangle = w_1$. It similarly queries all the other standard vectors $e_i \in \{0,1\}^n$, and receives each bit $w_i$ in response. After $n$ queries it knows $w$ entirely, which is equivalent to knowing a circuit for $C_w$.

What this has to do with obfuscation: if a class $\mathcal{C}$ is learnable by oracle queries, then one can obfuscate (according to the "virtual black box" definition) any code that computes a member of that class. The obfuscator is essentially just the learning algorithm: given any program/circuit that computes a function $C \in \mathcal{C}$, the obfuscator simply uses the code to answer the queries of the learning algorithm (by just running the code on the query). The obfuscator then outputs whatever code/circuit $C'$ the learning algorithm outputs.

This is a VBB obfuscator because a simulator that is given only black-box access to the function $C$ can do exactly the same thing (run the learning algorithm, using the oracle to answer queries). Notice, however, that this obfuscator is not actually "hiding" anything about the function that it's obfuscating; in fact, it's arguably revealing everything about that function! This still comports with the VBB definition of obfuscation, however, because any code that computes the function reveals everything about the function. So one might as well give out a "canonical" representation of the function, like the one computed by the learning algorithm.

| improve this answer | |
$\endgroup$

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.