From: tcmay@netcom.com (Timothy C. May)
Date: Sun, 10 Apr 94 18:10:09 PDT
To: hfinney@shell.portal.com (Hal)
Subject: Re: Zero Knowledge, Hamiltonian Cycles, and Passwords
In-Reply-To: <199404102332.QAA06039@jobe.shell.portal.com>
Message-ID: <199404110111.SAA24584@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Hal Finney writes:

> I think something like this may be the idea behind "obfuscated computing,"
> which Mike Duvos was writing about here a little while back.  The idea is
> that you do this trick not just with a graph, but with a boolean circuit
> composed of and, or, not gates, etc.  Take your algorithm and express it as
> such a circuit, then obfuscate it by drawing in extra gates, connections,
...
> I'm not 100% certain that this technique is used, but Tim's posting reminded
> me that I had read something about this several years ago, and this is how
> I remember it.

Yeah, sounds like a possibility, but we never got a fuller explanation
from Mike, so it's hard to tell.

I'm a bit skeptical, but it could just be that I haven't worked things
out to my own satisfaction. Compared to the Hamiltonian cycle, at
least.

But a wide class of problems are essentially equivalent to the
Hamiltonian cycle problem, as Hal and many others are well aware of
(that's what "NP-complete" means...solve one of 'em and you've
basically solved 'em _all_). Circuits, satisfiability of constraints,
etc., are one such NP-complete problem, so it's _conceivable_ the
"obfuscation compiler" works this way, if it is not urban legend.

Someone asked where to read more on this stuff. As Norm Hardy noted,
Bruce Schneier's book has a section on it. On NP-completeness in
general, Garey and Johnson's "Computers and Intractability: A Guide to
the Theory of NP-Completeness," 1979, is the standard reference. More
readable accounts may be found elsewhere. I especially like Harel's
"Algorithmics: The Spirit of Computing."

Also, a few folks have asked me to send them my article on zero
knowledge I posted in 1992 to this List. I will dig this (or maybe
"these") up from my mail archives and post them here.

In my not-so-humble opinion, the "juicy" stuff is sometimes not
discussed here very often because too few folks are reading the
background material enough to contribute. (I'm guilty of this, too, so
I'm not throwing stones...). We end up in banal--and
repetitive--debates about the NSA, about TEMPEST (it's about time for
a new thread on this :-} ), and about things like that.

Ray Cromwell wrote a very long, detailed, and important artcle on
remailers which has not been discussed nearly enough. Black Unicorn
wrote a long piece on legal and social implications, which has also
been discussed little. And of course Hal Finney has written many long
pieces on important topics. 

I urge you all to become knowledgeable about some aspect of our
many-fold interests and then to write articles educating the rest of
us. And respond to what others have written.

Off my soapbox now.

--Tim May

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."