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.

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?

share|improve this question
    
Should it be $V(C(x,r),x',r')=0$ if $x\neq x'$ or $r\neq r'$? –  mikeazo Jun 7 at 10:16
    
@mikeazo, I don't recall what the standard definition of a commitment scheme is; my recollection is that it doesn't really matter what $V(C(x,r),x,r')$ outputs, if $r \ne r'$ (it could output either $0$ or $1$, and no harm would be done either way). –  D.W. Jun 7 at 19:21

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
Also, your suggestion does not satisfy "the source code ... Alice's secret", since Alice could tell Carol $s(w||q)$, so that Carol doesn't know Alice's secret but seeing $P$ would reveal Bob's secret to Carol. $\hspace{.53 in}$ –  Ricky Demer Jun 7 at 10:24
    
@RickyDemer, good point. In that case $s$ would have to fully encode $x||r$. That is possible – e.g. Curve25519 secret keys are just bitstrings with about 30 bytes of data. For $x||r$ > 30 bytes you'd have to break it down to pieces and publish multiple public keys. –  otus Jun 7 at 10:28

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.

share|improve this answer
    
Thank you! Yes, I do have an a-priori bound on the length of $x$ and $y$, so that removes one possible complication. It would be fine to use any commitment scheme that makes the obfuscation task easy, so if Merkle tree based commitments make obfuscation easier, that would be fine. –  D.W. Jun 7 at 0:20
    
What makes the obfuscation task hard is that your formalization rules out Naor commitment; I have no idea how important non-interactivity is or isn't for your motivation. $\;$ –  Ricky Demer Jun 7 at 9:20
    
An interactive commitment protocol would be fine, as long as the verification is non-interactive (given an alleged opening of the commitment from Alice, Bob can check entirely on his own whether it is indeed a valid opening). If this problem gets easier for Naor commitments, that would be fascinating and useful! –  D.W. Jun 7 at 19:23

Your Answer

 
discard

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

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