Cryptography Reference
In-Depth Information
believed assumptions (without which most of modern cryptography col-
lapses anyhow). To summarize, not all assumptions are equal, and so
reducing a complex, new and doubtful assumption to a widely-believed
simple (or even merely simpler) assumption is of great value. Further-
more, reducing the solution of a new task to the assumed security of
a well-known primitive typically means providing a construction that,
using the known primitive, solves the new task. This means that we do
not only know (or assume) that the new task is solvable but we also
have a solution based on a primitive that, being well-known, typically
has several candidate implementations.
Prerequisites and structure
Our aim is to present the basic concepts, techniques and results in
cryptography. As stated above, our emphasis is on the clarification of
fundamental concepts and the relationship among them. This is done
in a way independent of the particularities of some popular number
theoretic examples. These particular examples played a central role in
the development of the field and still offer the most practical imple-
mentations of all cryptographic primitives, but this does not mean
that the presentation has to be linked to them. On the contrary, we
believe that concepts are best clarified when presented at an abstract
level, decoupled from specific implementations. Thus, the most relevant
background for this primer is provided by basic knowledge of algorithms
(including randomized ones), computability and elementary probability
theory.
The primer is organized in two main parts, which are preceded by
preliminaries (regarding ecient and feasible computations). The two
parts are
Part I - Basic Tools
and
Part II - Basic Applications
. The basic
tools consist of computational di
culty (one-way functions), pseudo-
randomness and zero-knowledge proofs. These basic tools are used for
the basic applications, which in turn consist of Encryption Schemes,
Signature Schemes, and General Cryptographic Protocols.
In order to give some feeling of the flavor of the area, we have
included in this primer a few proof sketches, which some readers may
find too terse. We stress that following these proof sketches is
not
