Cryptography Reference
In-Depth Information
Definition 3.5
(Pseudo-random one-time pad)
}
(
n
)
for some positive integer
n
and
n
.
•
M
=
C
={
0
,
1
K
={
0
,
1
}
n
.
•
Gen
chooses a key uniformly at random in
{
0
,
1
}
•
If
k
∈
K
,
m
∈
M
and
c
∈
C
, then
Enc
k
(
m
)
=
G
(
k
)
⊕
m
and
Dec
k
(
c
)
=
G
(
k
)
⊕
c
.
Remark 3.3
Although we have not yet formally defined the concept of computa-
tionally secure encryption, we can give an intuitive argument that shows that this
scheme is secure in the sense that a PPT adversary
, given a ciphertext, cannot
guess one bit of plaintext with probability significantly (i.e., non-negligibly) greater
than 1
A
is random (for,
in that case, we are dealing with the one-time pad which is perfectly secret) and,
since
G
is a pseudo-random generator by hypothesis,
/
2. Indeed, we know that this guess is impossible when
G
(
k
)
A
cannot distinguish between
a truly random string of length
(
n
)
and
G
(
k
)
so the guess is also impossible for
G
. We shall make this a little more precise once we formally define the notion of
computational security.
(
k
)
We are going to implement this scheme in Maple, assuming an external source
of true randomness. We need a (candidate) pseudo-random generator to reduce
the number of truly random bits required but these random bits are still neces-
sary for the seed. Random bits are very difficult to obtain and a physical source
is needed to generate them. Some of these sources can be: elapsed time between
particle emission during radioactive decay, thermal noise from semiconductors, fluc-
tuations in disk drive read latency times, etc. Less reliable sources are the system
clock, elapsed time between keystrokes or mouse movement, content of input/output
buffers, etc., but, by combining several of them, acceptable results can be obtained
in practice. Operating systems have tools to generate random bits such as Linux's
/dev/random
device that uses data taken from keyboard, mouse, network, and
disc activities or Windows' function
CryptGenRandom
that provides similar
functionality.
There is a simpler source which, at the cost of being very inefficient, can produce
bits that are random for all practical purposes: coin tossing (the physics of (fair)
coin tossing is discussed in [66], whose last sentence is: “The classical assumptions
of independence with probability 1
2 are pretty solid.”). Thus we will assume that
the bits produced by successive coin tosses are uncorrelated (this can probably be
achieved with some care) but, on the other hand, these bits might well be biased since
the coin might not be fair. There is, however, a simple trick due to Von Neumann that
produces unbiased bits from a biased coin (or, more generally, unbiased uncorrelated
bits from a source of biased but uncorrelated bits):
3
Von Neumann's coin flipping trick
. We toss the coin an even number of times
and group the obtained bits in pairs. Each '00' or '11' pair is discarded, each '10'
pair replaced by a '1' bit and each '01' pair replaced by a '0' bit.
/
3
There are also methods to produce uncorrelated bits from correlated bit sources but they are more
complicated and we shall not study them here.
