There are standard schemes for obfuscating a point function; I'm wondering if we know how to obfuscate a slight generalization of a point function. I'll elaborate more precisely.

Definition 1. A point function is a function $f_{v,w}$ defined by $f_{v,w}(x) = w$ if $v=x$ and $f_{v,w}(x)=0$ otherwise.

We know how to obfuscate a point function. For instance, one pragmatic obfuscation of the point function $f_{v,w}$ is the following circuit:

$$C(x) = \text{if $H(x,0)=c_0$ then $D_{H(x,1)}(c_1)$ else $0$},$$

where $c_0 = H(v,0)$ and $c_1=E_{H(v,1)}(w)$, $H$ is a cryptographic hash function (modelled as a random oracle), and $E,D$ are a secure encryption scheme. Note that the constants $c_0,c_1$ don't reveal $v,w$ if $v$ comes from a space of sufficiently high entropy, so the obfuscated circuit $C$ conceals $v,w$ if $v$ has high enough entropy.

Now let's consider a slight generalization.

Definition 2. A point-like function is a function $f_{m,v,w}$ defined by $f_{m,v,w}(x)=w$ if $x\land m = v$ and $f_{m,v,w}(x)=0$ otherwise.

Here $\land$ represents the bitwise logical-and operator, so $x \land m = v$ holds when the bits of $x$ selected by the mask $m$ match the corresponding bits of $v$ (I assume $v \land \neg m = 0$).

My question: Do we know of any plausible, practical way to obfuscate the class of point-like functions?

I am fine with any reasonable definition of obfuscation. I do want the obfuscated circuit to hide the values of $m,v,w$. I am fine with a scheme that might plausibly be secure in practice, even if we don't have a rigorous proof of security under standard cryptographic assumptions, or even if it requires the random oracle model or the generic group model or somesuch. I would prefer a solution that is efficient enough that you could plausibly use it in practice.

(For instance, I'm thinking maybe there's some way to do this using schemes for homomorphically evaluating 2-DNF formulas, but I don't know if that direction will actually work out or not. Maybe there's a better direction.)


Your Answer

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

Browse other questions tagged or ask your own question.