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."