Cryptography Reference
In-Depth Information
•
In the secret-communication problem (solved by use of encryption schemes), one wishes
to reduce, as much as possible, the information that a potential wire-tapper can extract
from the communication between two designated users. In this case, the designated
system consists of the two communicating parties, and the wire-tapper is considered as
an external (“dishonest”) party.
•
In the message-authentication problem, one aims at prohibiting any (external) wire-
tapper from modifying the communication between two (designated) users.
•
In the signature problem, one aims at providing all users of a system a way of making
self-binding statements and of ensuring that one user cannot make statements that would
bind another user. In this case, the designated system consists of the set of all users, and
a potential forger is considered as an internal yet dishonest user.
Hence, in the wide sense,
cryptography is concerned with any problem in which one
wishes to limit the effects of dishonest users
. A general treatment of such problems is
captured by the treatment of “fault-tolerant” (or cryptographic) protocols.
1.1.4. Fault-Tolerant Protocols and Zero-Knowledge Proofs
A discussion of signature schemes naturally leads to a discussion of cryptographic pro-
tocols, because it is a natural concern to ask under what circumstances one party should
provide its signature to another party. In particular, problems like mutual simultaneous
commitment (e.g., contract signing) arise naturally. Another type of problem, motivated
by the use of computer communication in the business environment, consists of “secure
implementation” of protocols (e.g., implementing secret and incorruptible voting).
Simultaneity Problems
A typical example of a simultaneity problem is that of simultaneous exchange of secrets,
of which contract signing is a special case. The setting for a simultaneous exchange
of secrets consists of two parties, each holding a “secret.” The goal is to execute a
protocol such that if both parties follow it correctly, then at termination each will hold
its counterpart's secret, and in any case (even if one party cheats) the first party will
hold the second party's secret if and only if the second party holds the first party's
secret. Perfectly simultaneous exchange of secrets can be achieved only if we assume
the existence of third parties that are trusted to some extent. In fact, simultaneous
exchange of secrets can easily be achieved using the active participation of a trusted
third party: Each party sends its secret to the trusted third party (using a secure channel).
The third party, on receiving both secrets, sends the first party's secret to the second
party and the second party's secret to the first party. There are two problems with this
solution:
1.
The solution requires the
active
participation of an “external” party in all cases (i.e., also
in case both parties are honest). We note that other solutions requiring milder forms of
participation of external parties do exist.
2.
The solution requires the existence of a
totally trusted
third entity. In some applications,
such an entity does not exist. Nevertheless, in the sequel we shall discuss the problem
