Cryptography Reference
In-Depth Information
Solving a cryptographic problem (or addressing a security concern)
is a two-stage process consisting of a
definitional stage
and a
construc-
tional stage
. First, in the definitional stage, the functionality underlying
the natural concern is to be identified, and an adequate cryptographic
problem has to be defined. Trying to list all undesired situations is
infeasible and prone to error. Instead, one should define the function-
ality in terms of operation in an imaginary ideal model, and require a
candidate solution to emulate this operation in the real, clearly defined,
model (which specifies the adversary's abilities). Once the definitional
stage is completed, one proceeds to construct a system that satisfies
the definition. Such a construction may use some simpler tools, and its
security is proved relying on the features of these tools. In practice, of
course, such a scheme may need to satisfy also some
specific
eciency
requirements.
This primer focuses on several archetypical cryptographic problems
(e.g., encryption and signature schemes) and on several central tools
(e.g., computational diculty, pseudorandomness, and zero-knowledge
proofs). For each of these problems (resp., tools), we start by presenting
the natural concern underlying it (resp., its intuitive objective), then
define the problem (resp., tool), and finally demonstrate that the prob-
lem may be solved (resp., the tool can be constructed). In the latter
step, our focus is on demonstrating the feasibility of solving the prob-
lem, not on providing a practical solution. As a secondary concern, we
typically discuss the level of practicality (or impracticality) of the given
(or known) solution.
Computational diculty
The aforementioned tools and applications (e.g., secure encryption)
exist only if some sort of computational hardness exists. Specifically,
all these problems and tools require (either explicitly or implicitly) the
ability to generate instances of hard problems. Such ability is captured
in the definition of one-way functions. Thus, one-way functions are the
very minimum needed for doing most natural tasks of cryptography. (It
turns out, as we shall see, that this necessary condition is “essentially”
sucient; that is, the existence of one-way functions (or augmentations
