Cryptography Reference
In-Depth Information
to prove that there exists a signature scheme that can resist “forgery,” even under a
“chosen message attack.”
To summarize, the basic concepts of cryptography are indeed very natural, but they
are
not
self-evident nor well understood. Hence, we do not yet understand these concepts
well enough to be able to discuss them
correctly
without using precise definitions and
rigorously justifying every statement made.
1.4.2. Practical Consequences of the Rigorous Treatment
As customary in complexity theory, our treatment is presented in terms of asymptotic
analysis of algorithms. (Actually, it would be more precise to use the term “functional
analysis of running time.”) This makes the treatment less cumbersome, but it is
not
es-
sential to the underlying ideas. In particular, the definitional approach taken in this topic
(e.g., the definitions of one-way functions, pseudorandom generators, zero-knowledge
proofs, secure encryption schemes, unforgeable signature schemes, and secure proto-
cols) is based on general paradigms that remain valid in any reasonable computational
model. In particular, the definitions, although stated in an “abstract manner,” lend
themselves to concrete interpolations. The same holds with respect to the results that
typically relate several such definitions. To clarify the foregoing, we shall consider, as
an example, the statement of a generic result as presented in this topic.
A typical result presented in this topic relates two computational problems. The
first problem is a simple computational problem that is assumed to be intractable (e.g.,
intractability of factoring), whereas the second problem consists of “breaking” a specific
implementation of a useful cryptographic primitive (e.g., a specific encryption scheme).
The abstract statement may assert that if integer factoring cannot be performed in
polynomial time, then the encryption scheme is secure in the sense that it cannot be
“broken” in polynomial time. Typically, the statement is proved by a fixed polynomial-
time reduction of integer factorization to the problem of breaking the encryption scheme.
Hence, what is actually being proved is that if one can break the scheme in time
T
(
n
),
where
n
is the security parameter (e.g., key length), then one can factor integers of length
m
in time
T
(
m
)
=
f
(
m
,
T
(
g
(
m
))), where
f
and
g
are fixed polynomials that are at
least implicit in the proof. In order to determine the practicality of the result, one should
first determine these polynomials (
f
and
g
). For most of the basic results presented
in this topic, these polynomials are reasonably small, in the sense that instantiating
a scheme with a reasonable security parameter and making reasonable intractability
assumptions (e.g., regarding factoring) will yield a scheme that it is infeasible to break
in practice. (In the exceptional cases, we say so explicitly and view these results as
merely claims of the plausibility of relating the two notions.) We actually distinguish
three types of results:
1.
Plausibility results:
Here we refer to results that are aimed either at establishing a con-
nection between two notions or at providing a generic way of solving a class of problems.
A result of the first type says that, in principle, X (e.g., a specific tool) can be used
in order to construct Y (e.g., a useful utility), but the specific construction provided in
the proof may be impractical. Still, such a result may be useful in practice because it
suggests that one may be able to use
specific
implementations of X in order to provide a
