crypto question

Nathaniel Daw daw at cs.cmu.edu
Thu Mar 21 11:39:49 EST 2002


On Thu, 2002-03-21 at 00:33, dmolnar wrote:

> There's a recent result showing that there exist some functions which
> *cannot* be obfuscated, for several technical formalizations of the notion
> "obfuscated." That result is available as:
> 
> On the (Im)possibility of Obfuscating Programs
> Boaz Barak Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai,
> Salil Vadhan, Ke Yang
> http://citeseer.nj.nec.com/barak01impossibility.html
> 
> It is important to note that this result doesn't necessarily apply to the
> kinds of programs we want to obfuscate in practice. Rather it shows that
> there is a large class of "unobfuscatable functions" and builds such
> functions through clever means. At least that's my current take; I should
> hedge here and say I haven't gone through it thoroughly -- I'd welcome
> correction from anyone who's taken more time to map out the practical
> implications (for instance, "is it possible that a block cipher could be
> obfuscated?").

I attended a talk on this result and the impression I came away with was
similar to yours. They argued that they can construct some of these
unobfuscatable functions that also belong to the class of encryption
functions (and I think the class of "block ciphers" would work just as
well in this argument), and that therefore anyone who claims to have a
general scheme for obfuscating encryption functions is selling snake
oil. They actually used Cloakware as an example of such impossible
claims. However, this result would still seem to leave hope that any
particular encryption function, not so artificially constructed, might
still be obfuscatable. I go to school with a couple of these guys, so I
can feel them out a bit on what they think the practical implications of
the proof are.

n


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list