From: tcmay@netcom.com (Timothy C. May)
Date: Sun, 10 Apr 94 12:26:36 PDT
To: cypherpunks@toad.com
Subject: Zero Knowledge, Hamiltonian Cycles, and Passwords
Message-ID: <199404101927.MAA07698@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Matt Thomlinson asked me in private e-mail about some of my old posts
on zero knowledge interactive proof systems (ZKIPS), especially with
regard to finding Hamiltonian cycles in graphs. (A graph is a set of
nodes with some set of links between the nodes. Like a bunch of cities
connected in some way with highways. A Hamiltonian cycle is a path
(subgraph) that visits each node once and only once. Try a few
examples with n = 5, say, and you'll see that not all graphs have
Hamiltonian cycles, and that finding them is done by exhaustively
drawing all possible paths until a Hamiltonian cycle is found. Try
increasing n to 10 and you'll see the problem get real hard, real
fast. By the time n is 100, no computer that will ever be built will
ever solve this, assuming "P" is not equal to "NP" (what Steve Smale
has called the most important math and computer science problem of the
past 50 years, the P =? NP problem).

The Hamiltonian cycle problem for a general graph is NP-complete. (For
any specific graph, it is of course solvable, by exhaustion. Not
necessarily practical to solve, but solvable).

Zero knowledge interactive proof systems were invented in the mid-80s
(notably by Goldwasser, Rackhoff, Micali, etc.). They allow the
paradoxical-seeming ability to *prove one has knowledge of something
without showing what one knows*. That is, Alice can establish with
arbitrarily high confidence level (to her skeptics or doubter) that
she knows some proof, or some fact, without actually giving them any
knowledge of the proof or fact!

And it was proved in 1988, at the very Crypto Conference I attended,
that anything provable in "ordinary" logic (FOL) is provable in a
ZKIPS logic system. (I can't find my Crypto-88 Proceedings this
minute, so this informal statement will have to do for now.)

A potential use for such systems is for passwords--one can prove one
has the knowledge without actually producing it (by typing in a
password, for example). I don't know that anyone is actually
exploring this application, yet, but I expect it'll come.

The Hamiltonian cycle problem is a good example of this. Alice claims
she knows the Hamiltonian cycle of a graph. But instead of producing
it--which would of course "use up" her further use of this--she goes
through a process of proving she "almost certainly" knows a
Hamiltonian cycle without actually producing it.

If this whets your appetite, I can dig up and post my article to this
list (first posted to the Extropians list) that I did about a year and
half ago. In this article I explain the "cut and choose" probabalistic
algorithm central to ZKIPS.

Anyway, here is some more stuff I wrote to Matt this morning. I've
deleted his questions and comments, as it was private mail, so this
answer picks up after he'd asked some questions about the process:

As they say, "anything provable in first order logic is provable in a
ZKIPS system." I'm not sure what it means to "prove" you know a method
of factoring numbers (faster than the "normal" methods, presumably)
except by actually factoring them. And factoring a 5,000-digit number
is 17 milliseconds would certainly show something significant. And,
trivially, it would presumably give zero knowledge about the method
used, so in that sense it is trivially zero knowledge.

[Matt asks about "construction" of the Hamiltonian cycle]

Give a graph, to find a Hamiltonian cycle is generally "hard." With 5
nodes, easy, by exhaustion--can be done on a napkin. With 15 nodes,
much harder. With 25 nodes, almost impossible. With 50 nodes,
intractable.

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). She can use
this as her "password," saying: "This is my graph and I know a
Hamiltonian cycle for it." Others are skeptical, since nobody knows
how to find a H. for such a large graph, but she proves who she is by
producing the H. cycle. (The idea is that Alice "registers" or
"publishes" the graph....nobody has yet done this, to my knowledge, so
the mechanics of "graph servers" are not worked out.)

Of course, by producing her Hamiltonian cycle, she's just used up her
only chance to use it, since she's shown others, and they can now
claim to be her. The trick is for her to show she knows the H.C.
without actually producing it.

And that's where the "cut and choose" probabalistic algorithm comes in.
The one I described in those old postings you are presumably looking
at.

--Tim



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


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