Cryptography Reference
In-Depth Information
yield simple constructions of private-key encryption schemes, and this observation is
often used in practice (usually implicitly).
Although the term “pseudorandom generators” is commonly used in practice , both in
the context of cryptography and in the much wider context of probabilistic procedures,
it is seldom associated with a precise meaning. We believe that using a term without
clearly stating what it means is dangerous in general and particularly so in a tricky
business such as cryptography. Hence, a precise treatment of pseudorandom generators
is central to cryptography.
Loosely speaking, a pseudorandom generator is a deterministic algorithm that ex-
pands short random seeds into much longer bit sequences that appear to be “random”
(although they are not). In other words, although the output of a pseudorandom generator
is not really random, it is infeasible to tell the difference. It turns out that pseudoran-
domness and computational difficulty are linked in an even more fundamental manner,
as pseudorandom generators can be constructed based on various intractability assump-
tions. Furthermore, the main result in this area asserts that pseudorandom generators
exist if and only if one-way functions exist.
Chapter 3, devoted to pseudorandom generators, starts with a treatment of the con-
cept of computational indistinguishability. Pseudorandom generators are defined next
and are constructed using special types of one-way functions (defined in Chapter 2).
Pseudorandom functions are defined and constructed as well. The latter offer a host of
additional applications.
1.1.3. Digital Signatures
A notion that did not exist in the pre-computerized world is that of a “digital signature.”
The need to discuss digital signatures arose with the introduction of computer commu-
nication in the business environment in which parties need to commit themselves to
proposals and/or declarations they make. Discussions of “unforgeable signatures” also
took place in previous centuries, but the objects of discussion were handwritten signa-
tures, not digital ones, and the discussion was not perceived as related to cryptography.
Relations between encryption and signature methods became possible with the
“digitalization” of both and the introduction of the computational-complexity approach
to security. Loosely speaking, a scheme for unforgeable signatures requires
that each user be able to efficiently generate his or her own signature on documents of
his or her choice,
that each user be able to efficiently verify whether or not a given string is a signature of
another (specific) user on a specific document, and
that no one be able to efficiently produce the signatures of other users to documents that
those users did not sign.
We stress that the formulation of unforgeable digital signatures also provides a clear
statement of the essential ingredients of handwritten signatures. Indeed, the ingre-
dients are each person's ability to sign for himself or herself, a universally agreed
verification procedure, and the belief (or assertion) that it is infeasible (or at least
Search WWH ::




Custom Search