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