Cryptography Reference
In-Depth Information
foregoing ideas in conjunction with additional ideas not presented here. The proof of
the validity of this construction is even more complex and is not suitable for a topic of
this nature. Thus we merely state the result obtained.
Theorem 3.5.12:
If there exist one-way functions, then pseudorandom generators
exist as well.
We conclude by mentioning that a non-uniform complexity analogue of Theorem 3.5.12
holds, and in fact is considerably easier to establish:
Theorem 3.5.13:
Suppose there exist non-uniformly one-way functions (as per
Definition 2.2.6). Then there exist pseudorandom generators. Furthermore, the
output ensemble of these generators is indistinguishable from the uniform ensem-
ble by polynomial-size circuits (as per Definition 3.2.7).
3.6. Pseudorandom Functions
In this section we present definitions and constructions for pseudorandom functions
(using any pseudorandom generator as a building block). Pseudorandom functions will
be instrumental for some constructions to be presented in Chapters 5 and 6 of Volume 2.
Motivation.
Recall that pseudorandom generators enable us to generate, exchange, and
share a large number of pseudorandom values at the cost of a much smaller number of
random bits. Specifically, poly(
n
) pseudorandom bits can be generated, exchanged, and
shared at the cost of
n
(uniformly chosen bits). Because any efficient application uses
only a polynomial number of random values, providing access to polynomially many
pseudorandom entries might seem sufficient for any such application. But that conclu-
sion is too hasty, because it assumes implicitly that these entries (i.e., the addresses
to be accessed) are fixed beforehand. In some natural applications, one may need to
access addresses that are determined “dynamically” by the application. For example,
we may want to assign random values to (poly(
n
)-many)
n
-bit-long strings, produced
throughout the application, so that these values can be retrieved at a later time. Using
pseudorandom generators, that task can be achieved at the cost of generating
n
random
bits and storing poly(
n
)-many values. The challenge, met in this section, is to carry
out that task at the cost of generating only
n
random bits
and storing only n bits
. The
key to the solution is the notion of pseudorandom functions. Intuitively, a pseudoran-
dom function shared by a group of users gives them a function that appears random to
adversaries (outside of the group).
3.6.1. Definitions
Loosely speaking, pseudorandom functions are functions that cannot be distinguished
from truly random functions by any efficient procedure that can get the values of
the functions at arguments of its choice. Hence, the distinguishing procedure may
148
