Confusing terminology about stream ciphers

Question

In their book, Understanding Cryptography, on page 37, Christof Paar and Jan Pelzel write:

Definition 2.2.2 One-Time Pad (OTP)

A stream cipher for which

1. the key stream s0,s1,s2,... is generated by a true random number 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

I have a problem with the third statement. Perhaps I am confused because of the way it is expressed in the English language.

It says every bit s[i] has to be used once. How come: s[i] is either 0 or 1? So, as soon as I use value 0 for s[12], does it mean I can't use value 0 anymore?

I am confused as to what the authors mean.

Furthermore, they also say:

Key stream bits cannot be re-used. This implies that we need one key bit for every bit of plaintext

Why does it imply that we need one bit for every plain text ?

Answer 1

If you used the randomly generated keystream bit $k[i]$ twice (think of it as a random variable, uniformly and independently generated at time $i$) at positions $i,i+\tau,$ then you'd have $$ c[i]=p[i] \oplus k[i] $$ and $$ c[i+\tau]=p[i+\tau] \oplus k[i], $$ then adding the ciphertext bits would yield the plaintext bit "difference" $$ p[i+\tau]\oplus p[i], $$ destroying the property that $$ c[i]\oplus c[i+\tau], $$ is independent and uniformly distributed, and making the conditional distribution of $c[i+\tau]$ given $c[i]$ dependent on the plaintext difference $p[i+\tau]\oplus p[i],$ which need not be uniform.

Thus the ciphertext sequence is no longer purely random (independent and uniformly distributed) which destroys the perfect secrecy property of the OTP system, since the ciphertext distribution is no longer independent of the plaintext distribution.

Answer 2

No. It simply means that any bit at position $i$ in the stream is only used once. So what ever value bit $i$ is in the key, it's xored with the equivalent positional bit in the plain text to create the cipher text. As: c[i] = p[i] XOR k[i]. On a computer, you'd be using octets rather than bits. Your 2nd part is explained then knowing this. And yes to confirm, you need at least as many bits (made truly randomly) as there are in the plain text. Thus the size of the key >= size of plain text.

You're absolutely right, it's simply terminology.