Limitations of limitations on RE/tampering (was: Re: biometrics)
dmolnar
dmolnar at hcs.harvard.edu
Tue Jan 29 12:11:38 EST 2002
On Sun, 27 Jan 2002, Sean Smith wrote:
>
> >the non-existence of obfuscators
>
> It would be interesting to see how this impossibility theorem
> reconciles with the last few years of work in encrypted functions...
Could you be a bit more specific? There are at least two distinct
scenarios which come to mind here. In both cases, it's not clear that
the non-obfuscation result is a problem.
1) Secure multiparty computation. "How to play any mental game" and
following. In this scenario, Alice has a private input a and Bob
has a private input b. Both have agreed on a public function f.
The goal is for both to learn f(a,b) but neither learns anything
"more" about the others' input. Generalize to multiple parties.
The question is whether some variant of multiparty computation
implies obfuscation (and is therefore impossible). At first that
seems unlikely, since in this scenario we don't care about hiding the
function f.
But maybe there's a way around that. For instance, set f to be a
universal TM and then smuggle in the function to "obfuscate" as the
private input a. Let the other private input b be the input to
the function a. Then the output f(a,b) is the result of running program
a on input b, but by secure multiparty computation, Bob learns
nothing about the program a.
The other main difference is that all the protocols I can think of
in this scenario are interactive. Obfuscation is not interactive;
once you've released the supposedly obfuscated program, anyone can
come along and query it to his/her heart's conent.
Now if you could obfuscate "self-modifying code" then maybe you could
get closer to this by having obfuscated functions which refuse to
answer after a small number of queries..? I'd have to check the
paper carefully to see how many queries are sufficient to reveal
one of the unobfuscatable functions - maybe as little as one.
2) CryptoComputing. "Noninteractive CryptoComputing for NC^1,"
Sander, Young, and Yung FOCS '99.
Alice has a function f and Bob has a private input b.
The goal is for Alice to learn f(b), but not b. At the same
time, Bob must learn nothing about f or f(b).
Here we *do* care about hiding the function f, so this is
closer in spirit to obfuscation. The difference is, however,
that Bob does not get to see f(b). So he can query the function
all he wants, but the answers will be of no help.
In the paper, Bob ends up with the value f(b) encrypted with Alice's
public key, which he then sends to Alice. If you know Alice's private
key, then you can decrypt the circuit description as well. So it seems
difficult/impossible to create an obfuscator from their CryptoComputing
construction, because either you don't know the output or you know
the circuit description. So I'm not sure what bearing the
impossibility result has here.
-David
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com
More information about the cryptography
mailing list