Cryptography Reference
In-Depth Information
d
(n)
/
d(n)
|
chosen d(n)-bit-long prime divides a d
(n)-bit-long integer is at most
, which is
Prime
d(n)
|
(d
(n)
·
2
−
d(n)
).
Exercise 31:
An alternative construction for Exercise 30: Let F and let d
be as
in Exercise 30, and let S
d(n)
d
(n)
be a hashing family (as defined in Section 3.5.1.1).
S
d(
|
s
|
)
}
∗
and h
d
(
|
s
|
)
, define f
s,h
such that f
s,h
(x)
For every s
∈{
0, 1
∈
f
s
(h(x)), and let
=
def
=
{
F
f
s,h
:
d
(
|
s
|
)
r(
|
s
|
)
{
0, 1
}
→{
0, 1
}
}
s
∈{
0,1
}
∗
,h
∈
S
d(
|
s
|
)
d
(
|
s
|
)
(This construction requires longer seeds than the one in Exercise 30; however, one can
use much smaller families of functions that approximate the desired features.)
1.
Prove that if d(n)
=
ω
(log n), then F
is pseudorandom.
2.
On the other hand, show that if d(n)
=
O(log n) and r(n)
>
d(n), then F
is not pseudo-
random.
Guideline (Part 2):
For any distinct x, y
∈{
0, 1
}
d
(n)
and a uniformly selected function
mapping d
(n)-bit-long strings to r(n)-bit-long string, the probability that x and y are
mapped to the same image is 2
−
r(n)
. However, the probability that xand yare mapped to
the same image under a uniformly selected f
s,h
is lower-bounded by Pr[h(x)
=
h(y)]
=
2
−
d(n)
.
Exercise 32:
Analternativedefinitionofpseudorandomfunctions: For the sake of sim-
plicity, this exercise is stated in terms of ensembles of Boolean functions (analogously
to Definition 3.6.9, with d(n)
nand r(n)
1). That is, we consider a Boolean-function
=
=
}
|
s
|
→{
ensemble
{
f
s
:
{
0, 1
0, 1
}}
s
∈{
0,1
}
∗
and let F
n
be uniformly distributed over the
multi-set
F
n
}
n
∈
N
is unpredictable if
for every probabilistic polynomial-time oracle machine M, for every polynomial p(
{
f
s
}
s
∈{
0,1
}
n
. We say that the function ensemble
{
·
), and
for all sufficiently large n's,
Pr
corr
F
n
M
F
n
(1
n
)
<
1
2
+
1
p(n)
where M
F
n
(1
n
) assumes values of the form (x,
n
σ
)
∈{
0, 1
}
×{
0, 1
}
such that x is
not a query appearing in the computation M
F
n
(1
n
), and corr
f
(x,
σ
) is defined as the
predicate “f(x)
”. Intuitively, after getting the values of f on points of its choice, the
machine M outputs a new point (i.e., x) along with a guess (i.e.,
=
σ
σ
) for the value of
f on this point. The value of corr
f
(x,
σ
) represents whether or not M is correct in its
guess.
Assuming that F
=
{
F
n
}
n
∈
N
is efficiently computable, prove that F is pseudorandom
if and only if F is unpredictable.
Guideline:
The proof is analogous to the proof of Theorem 3.3.7
Exercise 33:
A mistaken “alternative” definition of pseudorandom functions: Again,
we consider ensembles of Boolean functions, as in Exercise 32. Consider the following
definition of weakunpredictability of function ensembles. The predicting oracle machine
M is given a uniformly chosen x
n
as input and should output a guess for f(x),
after querying the oracle f on polynomially many other (than x) points of its choice. We
require that for every probabilistic polynomial-time oracle machine Mthat doesnotquery
∈{
0, 1
}
