Stream Ciphers - Understanding Cryptography - page 36

there are “only” about 2 266 atoms in the known universe.) The cipher would merely
be computationally secure but not unconditionally.
All this said, we now show a way to build an unconditionally secure cipher that
is quite simple. This cipher is called the One-Time Pad.

Definition 2.2.2 One-Time Pad (OTP)
A stream cipher for which

1. the key stream s 0 , s 1 , s 2 ,... is generated by a true random num-
ber generator, and
2. the key stream is only known to the legitimate communicating
parties, and
3. every key stream bit s i is only used once
is called a one-time pad. The one-time pad is unconditionally se-
cure.

It is easy to show why the OTP is unconditionally secure. Here is a sketch of a
proof. For every ciphertext bit we get an equation of this form:

y 0 ≡ x 0 + s 0 mod 2

y 1 ≡ x 1 + s 1 mod 2

.

Each individual relation is a linear equation modulo 2 with two unknowns. They
are impossible to solve. If the attacker knows the value for y 0 (0 or 1), he cannot
determine the value of x 0 . In fact, the solutions x 0 = 0 and x 0 = 1 are exactly equally
likely if s 0 stems from a truly random source and there is 50% chance that it has the
value 0 and 1. The situation is identical for the second equation and all subsequent
ones. Note that the situation is different if the values s i are not truly random. In this
case, there is some functional relationship between them, and the equations shown
above are not independent. Even though it might still be hard to solve the system of
equations, it is not provably secure!
So, now we have a simple cipher which is perfectly secure. There are rumors
that the red telephone between the White House and the Kremlin was encrypted
using an OTP during the Cold War. Obviously there must be a catch since OTPs are
not used for Web browsers, e-mail encryption, smart cards, mobile phones, or other
important applications. Let's look at the implications of the three requirements in
Defintion 2.2.2. The first requirement means that we need a TRNG. That means we
need a device, e.g., based on white noise of a semiconductor, that generates truly
random bits. Since standard PCs do not have TRNG, this requirement might not be
that convenient but can certainly be met. The second requirement means that Alice
has to get the random bits securely to Bob. In practice that could mean that Alice
burns the true random bits on a CD ROM and sends them securely, e.g., with a
trusted courier, to Bob. Still doable, but not great. The third requirement is probably