Re: Best definition of cryptography

From: An Metet (anmetet_at_freedom.gmsociety.org)
Date: 04/30/04 

Date: Fri, 30 Apr 2004 04:11:30 -0400

NOTE: This message was sent thru a mail2news gateway.
No effort was made to verify the identity of the sender.
--------------------------------------------------------

You're right that there is an element of adversarial behavior in the
analysis. When you look at how much information each party gains during
the cryptographic procedure, you need to consider the possibility that
the parties are taking the best advantage possible of the opportunities
they have to cheat.

However, you don't necessarily have to look at it that way.
The information you gain from a ZK proof is valid regardless of what
your assumptions are about the other party's motivations. It is true
that if he is adversarial, that is something of a worst case, and this
will constrain your conclusions. But you get the same answer without
necessarily having to assume adversarial behavior, because it follows
logically from the simple question of how much you can reliably conclude
from your view of the protocol.

It is instructive to consider as an alternative a normal mathematical
proof, like Andrew Wiles' proof of Fermat's Last Theorem. In a way, there
is an adversarial element in mathematical proofs. A valid mathematical
proof must be so strong as to be convincing even to a verifier who does
not want to accept it, and likewise a dishonest prover cannot create a
convincing proof.

If we compare a regular mathematical proof with a zero knowledge proof,
both have elements of adversarial analysis, and both constrain the
behavior of the participants so as to limit the conclusions that can
be drawn. Yet only one is considered cryptography.

I would suggest that the difference is because the crypto case puts limits
on the information transfer, and more to the point, the cryptography
is all about the limits. The regular proof basically transfers all
the relevant information, without limit. The crypto proof only allows
certain types of information to flow: the ZK proof convinces the verifier
but cannot be transfered.

An intermediate case would be probabilistically checkable proofs.
PCPs let a verifier interact with a prover and make a limited number
of queries to gain a probabilistic degree of confidence in the proof.
Are PCPs cryptography? Many cryptographers have worked on them, and
they are used in some crypto protocols. They do satisfy my definition
of cryptography as dealing with limitations on information transfer,
so I'd suggest that PCPs should be considered crypto.