Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.