From: tcmay@got.net (Timothy C. May)
Date: Sat, 16 Sep 95 09:50:13 PDT
To: cypherpunks@toad.com
Subject: Re: Explaining Zero Knowledge to your children
Message-ID: <ac804c8a14021004bc1f@[205.199.118.202]>
MIME-Version: 1.0
Content-Type: text/plain


At 3:10 AM 9/15/95, hallam@w3.org wrote:
>The cave analogy sucks.
>
>The way I tried to explain Zero Knowledge is this:
>
>
>Imagine that you have a duplicator device which you want to sell, you don't
>want to explain why it works to the buyer however since then they would
>just make their own (patents have been abolished by this time). You also don't
>want the buyer to be able to prove to anyone else that you have a duplicator.
>
>So what you do is you play the "what hand is it in game" and you do this
>with a
>10$ bill provided by the buyer and who records its serial number. You hold the
>original article in one hand and the duplicate in the other. The buyer choses
>one hand, you show the article in that hand. The buyer knows you had a 50:50
>chance of a lucky guess so you do it again, each time the probability of
>getting
>it right by a lucky guess halves. After 10 tries or so it is virtually certain
>that you were not faking.
>
>
>Any better ideas...

Clever, but I think it's missing an important element of zero knowledge
interactive proof systems. For example, why not simply open _both_ hands?

By opening both hands one shows immediately that one has a duplicator, but
does not show how the duplicator works. The same results are obtained with
perfect certainty in _one_ round that the ZKIPS approach takes N rounds (as
N gets large).

Granted, this fails the " don't want the buyer to be able to prove to
anyone else that you have a duplicator" test, but I don't think that is
central to ZKIPS. I think a more important test is "don't show others how
to make matter duplicators."

Matter duplicators are "self-demonstrating" without revealing how they
work, so they don't fit the model of (or create a need for) software-based
ZKIPS.

For example, in the Hamiltonian cycle example, the Prover demonstrates to
the Skeptic either the set of nodes, with the nodes labelled, or a
Hamiltonian cycle, with the nodes unlabelled. If he shows _both_ the set of
nodes _and_ a Hamiltonian cycle, then he's given the Skeptic the whole
shebang. In Phill's example, he's just taught the Skeptic "how to make a
matter duplicator."


But I applaud the creation of new and simpler examples, and maybe I'm wrong
and Phill's example captures the essence of zero knowledge interactive
proofs. I'll think about it some more.

Comments?

--Tim May

---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
Corralitos, CA              | knowledge, reputations, information markets,
Higher Power: 2^756839      | black markets, collapse of governments.
"National borders are just speed bumps on the information superhighway."