Pseudorandom Generators - Foundations of Cryptography: Basic Tools - page 172

have direct oracle access to the random function and does not obtain the description of
the pseudorandom function used in the latter implementation. We warn that, in contrast
to the methodology presented in Section 3.6.3, the Random Oracle Methodology is
heuristic. In particular, there exist encryption and signature schemes that are secure in
the Random Oracle Model, but do not have any secure implementation by a function
ensemble [46].

3.8.3. Open Problems

Although Hastad et al. [129] showed how to construct pseudorandom generators given
any one-way function , their construction is not practical, the reason being that the
“quality” of the generator on seeds of length n i s related to the hardness of inverting the
given function on inputs of length less than

√ n . We believe that presenting an efficient
transformation of arbitrary one-way functions to pseudorandom generators is one of the
most important open problems in this area and that doing so may require the discovery
of new important paradigms.
An open problem of more acute practical importance is to present even more efficient
pseudorandom generators based on the intractability of specific computational problems
like integer factorization. For further details, see Sections 3.4.3 and 2.7.3.

4

3.8.4. Exercises

Exercise 1: Computationalindistinguishability,trivialvariations: Prove that the follow-
ing trivial variations on Definition 3.2.2 are equivalent to it. In all versions we consider
the ensembles X def X n } n ∈ N and Y def

Y n } n ∈ N .
1. Ensembles X and Y are indistinguishable1 in polynomial time if for every probabilistic
polynomial-time

= { = {

algorithm D, every positive polynomial p( · ), and all sufficiently

large n's,

1
p(n)

| Pr [D(X n ,1 n ) = 1] − Pr [D(Y n ,1 n ) = 1] |≤

That is, the strict inequality is replaced by ≤ .
2. Ensembles X and Y are indistinguishable2 in polynomial time if for every probabilistic
polynomial-time algorithm D, every positive polynomial p( · ), and all sufficiently large n's,

1
p(n)

Pr [D(X n ,1 n ) = 1] − Pr [D(Y n ,1 n ) = 1] <

That is, the absolute value is dropped.
3. Suppose that | X n | = | Y n | = n. Ensembles X and Y are indistinguishable3 in polynomial
timeif for every probabilistic polynomial-time algorithm D, every positive polynomial p( · ),
and all sufficiently large n's,

1
p(n)

| Pr [D(X n ) = 1] − Pr [D(Y n ) = 1] | <

That is, the auxiliary input 1 n is omitted.