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