Re: Zero Knowledge, Hamiltonian Cycles, and Passwords

[Hal <hfinney@shell.portal.com>]

From: tcmay@netcom.com (Timothy C. May)
> And yet suppose Alice shows you one. In a textbook, for example. How
> did she "find" it? She likely didn't. Rather, she took 50 nodes, drew
> a path visiting each node once, stored this as her 'Hamiltonian cycle'
> and then proceeded to draw in 50 or 70 or whatever "other links,"
> which are "ringers," as it were (that is, they are never part of the
> Hamiltonian she "constructed").
> 
> The resulting complete graph--50 nodes with maybe 100 or 500 or whatever
> links--only she knows a valid Hamiltonian cycle for (there may be
> others, which neither she nor anyone else will ever find).

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,
etc.  The resulting circuit has your original circuit embedded in it, but
figuring out what the total circuit does can be computationally intractable.
Someone could build or emulate this circuit and get a result, but they would
not be able to figure out exactly what formula they were computing.

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.

Hal