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