Cryptography Reference
In-Depth Information
The bits produced are unbiased because if the probability that the coin lands heads
up is
p
(where
p
≤
−
p
, then
the probability of obtaining a '10' pair is the same as the one of obtaining a '01' pair,
namely
p
1) and hence the probability that it lands tails up is 1
. The only problem might be efficiency as, on average, we will have
to toss the coin a number of times
(
1
−
p
)
≥
4
n
to obtain
n
bits.
Exercise 3.9
Assuming that the probability that the coin lands heads up is
p
, com-
pute the average number of coin flips that it takes to generate a bit using Von Neu-
mann's trick.
The classical techniques to produce pseudo-random numbers useful for Monte
Carlo simulations—for example, linear feedback shift registers and linear congruen-
tial generators—do not yield PRGs in the sense of Definition 3.4 and hence are not
suitable for cryptographic use. The classical methods to evaluate pseudo-randomness
rely on the use of statistical tests that check whether the string of bits generated has
the expected number of patterns (for example, the number of times that a specific
substring should appear, see [115]). But they are completely inadequate to pin down
generators suitable for cryptographic use, which have to satisfy the stronger require-
ment that the output bit string must look random to
every
PPT algorithm. However, it
is not necessary to consider all PPT algorithms because there is a much smaller sub-
class of algorithms that suffices to guarantee that we have a PRG. These algorithms
check an obvious requirement that the PRG must fulfill to be secure: an adversary
(a PPT algorithm) that sees a portion of the generator's output must be unable to
efficiently predict other unseen bits. Otherwise, an adversary that sees a ciphertext
from the scheme in Definition 3.5 might guess a portion of the message and hence a
portion of
G
, it would
also be able to decrypt other portions of the message. These special PPT algorithms
are defined as follows:
(
k
)
and, if it could then efficiently compute other bits of
G
(
k
)
}
∗
→{
}
∗
be a polynomial-time computable function
Definition 3.6
Let
G
:{
0
,
1
0
,
1
with stretch
: N → N
.A
predictor
for
G
is a PPT algorithm
A
which, for every
n
, with
G
y
(
n
)
, takes as input 1
n
and
randomly chosen seed
s
∈{
0
,
1
}
(
s
)
=
y
1
y
2
...
a prefix
y
1
y
2
...
y
i
of
G
(
s
)
(with
i
<(
n
)
randomly chosen) and outputs a bit
b
(we
think of
b
as a guess made by
A
trying to predict the next bit
y
i
+
1
). In other words,
1
n
b
←
A(
,
y
1
y
2
...
y
i
)
(here we use the
←
notation to emphasize that the algorithm
is probabilistic).
Remark 3.4
The input 1
n
is the representation of
n
in
unary notation
where
n
is
given as a string of
n
ones. The predictor
must run in time polynomial on the size
of
n
which, if
n
were given in positional notation, would be the binary length len
A
(
n
)
.
However, in this case,
n
is given in unary and so its size is
n
itself, not len
. Thus
the unary notation means that the algorithm's running time must be a polynomial
function of
n
and not of its binary length len
(
n
)
(
n
)
.
Using predictors, we define a special class of tests that suffice to check whether
a polynomial-time computable function is a PRG:
