Cryptography Reference
In-Depth Information
}
n
∈
N
is pseudorandom, as defined in Definition 3.2.8. (If G
is
a pseudorandom generator, then it satisfies both conditions, but the converse is not
true.)
Prove that the generalized function ensemble
G
(U
n
)
the ensemble
{
d(
|
s
|
)
r(
|
s
|
)
{
f
s
:
{
0, 1
}
→{
0, 1
}
}
s
∈{
0,1
}
∗
,
defined by f
s
(x)
def
G
(f
s
(x)), is pseudorandom.
Guideline:
See proof of Theorem 3.6.11.
=
Exercise 30:
Speeding up pseudorandom function constructions (suggested by
Leonid Levin): For some d, r :
N
→
N
, consider a generalized pseudorandom function
ensemble
F
def
d(
|
s
|
)
r(
|
s
|
)
=
{
f
s
:
{
0, 1
}
→{
0, 1
}
}
s
∈{
0,1
}
∗
as in Definition 3.6.9. Let Primes
m
denote the set of primes in the interval (2
m
−
1
,2
m
).
For any d
: N
→
N, consider a new function ensemble,
F
def
d
(
|
s
|
)
f
s, p
:
r(
|
s
|
)
=
{
{
0, 1
}
→{
0, 1
}
}
s
∈{
0,1
}
∗
, p
∈
Primes
d(
|
s
|
)
such that f
s, p
(x)
def
d
(
|
s
|
)
and
d(
|
s
|
)
are associated with
f
s
(x mod p), where
{
0, 1
}
{
0, 1
}
=
0,...,2
d
(
|
s
|
)
0,...,2
d(
|
s
|
)
{
, respectively.
The point is that the functions in F
are computable in time related to the time-
complexity of F. Whenever d
(n)
−
1
}
and
{
−
1
}
log
n
n), this yields
a speedup in the time-complexity of F
(when compared with Construction 3.6.10).
1.
Prove that if d(n)
d(n) (e.g., d
(n)
n
2
and d(n)
=
=
(log n), then F
is pseudorandom.
2.
Show that, on the other hand, if d(n)
=
ω
O(log n) (and d
(n)
>
d(n)), then F
is not
=
pseudorandom.
Note that, in general, the “pseudorandomness” of F
(as quantified with respect to the
running time sufficient to see evidence that F
is not random) depends on d : N
→
N.
Specifically, evidence that F
is not random can be found in time exponential in d.
Guideline (Part 2):
Going over all possible p's, try to gather evidence that the target func-
tion indeed uses reduction modulo p. (Hint: For fixed p, any two distinct x, y
∈{
0, 1
}
d
(
|
s
|
)
such that x
≡
y (mod p) yield such evidence.)
Guideline (Part 1):
Consider applying the foregoing construction to the uniform function
ensemble H, rather than to the pseudorandom ensemble F. The main issue is to show
that the resulting ensemble H
is pseudorandom. (F
is indistinguishable from H
, or else
we can distinguish F from H.)
Guideline (Part 1, extra hints):
We refer to the function ensemble H
=
{
H
n
}
n
∈
N
, where
H
n
is defined by uniformly selecting a function h:
{
0, 1
}
r(n)
and p
∈
Prime
d(n)
and letting H
n
=
h
p
such that h
p
(x)
=
h(x mod p). If the distinct queries x
1
,...,x
t
∈
{
0, 1
}
d(n)
→{
0, 1
}
d
(n)
have distinct residues mod p, then the answers obtained from h
p
are indepen-
dently and uniformly distributed in
{
0, 1
}
r(n)
. Thus, essentially, we need to lower-bound
the probability of the former event for a uniformly selected p
∈
Prime
d(n)
. We upper-bound
the probability of the complementary event (i.e.,
i
=
j s.t. x
i
≡
x
j
(mod p)). For dis-
∃
d
(n)
, it holds that x
tinct x, y
∈{
0, 1
}
≡
y
(mod p) iff p divides x
−
y. At this stage
the argument is simplified by the fact that p is prime:
12
The probability that a uniformly
12
What if the construction were to be modified so that
p
was uniformly selected among all integers in
{
2
d
(
n
)
−
1
,...,
2
d
(
n
)
−
1
}
?
