Obfuscate an "I'll reveal if you do" function

Question

Is there any cryptographic obfuscation scheme that will let me obfuscate a program that reveals my secret, if you reveal yours?

Formalization. Let $C(\cdot),V(\cdot)$ be a secure commitment scheme. In other words, $C(x,r)$ is a commitment to $x$ under randomness $r$, and $V(\cdot)$ is the corresponding verification function, so that $V(C(x,r),x,r)=1$ and $V(C(x,r),x',r')=0$ if $x\ne x'$.

For instance, one example commitment scheme is $C(x,r) = H(x \;||\; r)$ and $V(c,x,r)=1$ if $H(x \;||\; r)=c$, $0$ otherwise; where $H$ is a cryptographic hash function.

Suppose Alice has a secret $x$, and she publishes a commitment $c=C(x,r)$ to her secret. Suppose Bob has a secret $y$ of his own. Can Bob build a obfuscated program $P$ so that, when you run $P$ on input $x,r$, it outputs Bob's secret $y$, but the source code of $P$ doesn't reveal anything about Bob's secret to someone who doesn't know Alice's secret?

To make this precise, we can define the function $f$ by $f(w,q) = y$ if $V(c,w,q)=1$ and $f(w,q)=0$ otherwise (in fact I don't really care what the output is, in the latter case, as long as it doesn't reveal anything about $y$).

My question. Can Bob obfuscate $f$ to get a program $P$ that computes the same functionality as $f$ (so $P(w,q)=f(w,q)$ for all $w,q$), but where the source code of $P$ reveals nothing about $y$?

Can this be done in a way that is efficient enough to be practical? I am fine with a solution for any commitment scheme of your choice: you can co-design the commitment scheme and the obfuscation method. I am fine with the random oracle model and any plausible cryptographic hardness assumptions you might want to make.

Motivation. This would help with the construction of cryptographic fair exchange protocols, where intuitively we want Bob's secret to be revealed if Alice's is (except there are many more details I'm omitting that are out of scope for purposes of this question).

One thing that makes me think it might be doable is that this is a lot like a point function, which we do know how to obfuscate. The difference here is that the obfuscator (Bob) does not know Alice's secret $x$ -- he only knows the commitment $c$ -- whereas the standard methods for obfuscating a point function would require Bob to know the secret value $x$. So, the standard methods for obfuscating point functions do not immediately solve this problem... but can they be adjusted or extended somehow? Alternatively, I know there have been recent breakthroughts in indistinguishability obfuscation; might those help with this obfuscation task?

Answer 1

Choose a public key encryption scheme, where $(s(x||r), p(x||r))$ is a key-pair derived from $x||r$ using a cryptographic hash function so that $s(x||r)$ is invertible.

To make a commitment $C(x, r)$, Alice derives the key-pair and publishes the public key $c = p(x||r)$. If she reveals $x$ and $r$ then anyone can see if the same key-pair can be derived: $V(c, x, r) = 1$ if $p(x||r) = c$ else $0$.

To make his secret $y$ conditional on knowing $x$, Bob encrypts $y$ using Alice's public key to get $d = E_{p(x|r)}(y)$. Then he can define $P(w, q) = D_{s(w||q)}(d)$ if $p(w||q) = c$ else $0$.

Can this be done in a way that is efficient enough to be practical?

As long as the public key system chosen can derive key-pairs fast (e.g. Curve25519), it should be practical.

Answer 2

If there is _______________ obfuscation scheme for such $\hspace{.03 in}f$s then there is a scheme
that does what you describe, where _______________ is either "a differing-inputs"
or "an extractability", depending on how you define "doesn't know Alice's secret".

Note that if there is no a-priori bound on the length of $x$, then the $\hspace{.03 in}f$s will have to be Turing machines with unbounded input length rather than just circuits. $\:$ In order to obfuscate such programs with the latter paper's candidate construction, one needs (publicly verifiable) SNARKs instead of just SNARGs.
However, if there is an a-priori bound on the length of $x$ or the commitment scheme's
verification function is sufficiently parallelizable (for example, if it follows a Merkle tree),
then one can replace the FHE scheme with a leveled FHE scheme.

On the other hand, this paper gives an argument against
the plausibility of the types of obfuscation that I linked to.


I see a lot of papers mentioning that standard assumptions suffice for the existence of a pseudorandom generator with linear stretch in NC1, although I cannot actually find any good candidate for that. $\:$ If there is one, then by chaining it to make the stretch sufficiently large and applying Naor's construction to the resulting PRG, one gets a commitment scheme whose verification function is in NC1. $\:$ Observe that
the $\hspace{.03 in}f$s are computable by just ANDing the output of the verification function with each bit of $y$.
Thus, if there is a pseudo-random generator with linear stretch in NC1 and a
_______________ obfuscation scheme for NC1, then there is a scheme whose
commitment is slightly interactive but otherwise does what you describe.