Cryptography Reference
In-Depth Information
Exercise 4.1
Check the binary analogues of the above-mentioned information units
and compute the approximate number of
yobibytes
that would be required to store a
random permutation of
128
.
{
0
,
1
}
As happens with the one-time pad, true randomness makes the system unman-
ageable and, indeed, even more so in this case. However, as we have also seen,
complexity theory can be used to make randomness more manageable just by replac-
ing it by pseudo-randomness. Now we are dealing with (random) functions instead
of bits but we can use the same intuitions that lead to the definition of PRGs. A
block cipher
F
t
n
n
:{
0
,
1
}
×{
0
,
1
}
→{
0
,
1
}
induces a probability distribution on
n
t
and the asso-
the symmetric group
S
(
{
0
,
1
}
)
by choosing a random key
k
∈{
0
,
1
}
n
ciated permutation
F
k
∈
. The idea is then to call
F
pseudo-random if the
permutation
F
k
corresponding to a randomly chosen
k
S
(
{
0
,
1
}
)
t
is indistinguishable
to a PPT distinguisher
D
from a permutation
f
chosen uniformly at random from
S
∈{
0
,
1
}
n
. The distinguisher
D
is a PPT algorithm and hence it cannot have access
to a full description of a random permutation, which has size exponential in
n
. Thus
D
is given oracle access to the function it is trying to distinguish (which can be either
F
k
or
f
). The oracle is like a black box that will answer
D
's queries without giving
any additional information.
D
can ask only a polynomial number of queries (since
it is a PPT algorithm) and each query is about the value that the function takes at a
point
x
(
{
0
,
1
}
)
n
that is chosen by
D
. Moreover,
D
can ask these queries adaptively,
i.e.,
D
may choose each query as a function of the earlier oracle answers. We do
not need to know how the oracle works but we can imagine how an oracle could
efficiently answer
D
's queries even in case they are about a random permutation. In
this case, if queried about
x
∈{
,
}
0
1
n
, the oracle would choose a random element
∈{
0
,
1
}
n
as its answer and would record in a table the input/output pair
.
In each subsequent query, the oracle would check first whether the queried input is
already the first component of a table entry and, if so, it would give the same answer
as in the preceding query (to ensure that it is implementing a function); otherwise,
it would choose its answer at random among all elements of
y
←{
0
,
1
}
(
x
,
y
)
n
which do not
appear as the second component of a table entry (to ensure that it is implementing
a permutation). Then, after answering the query, it would record the corresponding
input/output pair in the table.
The block cipher uses a fixed value of
n
but, in order to give a precise definition
of when
F
is pseudo-random we have to use the asymptotic concept of negligi-
ble function and, to make it meaningful, we may let
n
vary by considering, more
generally, a
keyed function F
, namely a function
F
{
0
,
1
}
}
∗
(where the first input is called the key) which is length-preserving, i.e., such that
len
}
∗
×{
}
∗
:{
0
,
1
0
,
1
→{
0
,
1
}
∗
(thus we assume, for simplicity,
that the length of the key is the same as the length of the input
x
and the length
of the output
F
(
k
)
=
len
(
x
)
=
len
(
F
(
k
,
x
))
for all
x
∈{
0
,
1
n
,
F
(
k
,
x
)
, although this is not essential). Then, for each
k
∈{
0
,
1
}
n
n
given by
F
k
(
:{
,
}
→{
,
}
)
=
(
,
)
defines a function
F
k
0
1
0
1
x
F
k
x
. If, moreover,
n
, we say that
F
is a
keyed permutation
. Also, in what follows we will always assume that
F
is an effi-
n
{
,
}
∈{
,
}
the function
F
k
is a permutation of
0
1
for each
k
0
1
