# Confusing terminology about stream ciphers

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 ?

• @Patriot you confused the edit, the last question was vice versa: key stream bits can't be reused --> why it implies that we need one bit for every plain text. You have put it in reverse now. – user71089 Aug 9 '19 at 14:31
• OK, I will undo it. – Patriot Aug 9 '19 at 14:57

## 2 Answers

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.

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.

• " It simply means that any bit at position i in the stream is only used once"-> how come if at position 7 I use bit 0, then how can I use a different bit on position 7 again? during second encryption? Can you elaborate I am confused now – user71072 Aug 8 '19 at 16:03
• @user71072 it's not about the individual bit symbols (1 or 0), and it's not about where you've previously used individual bit symbols. It's about that each individual bit stream needs to be generated independently - knowing one bit stream should not reveal anything about what the values of the next one will be. – Natanael Aug 8 '19 at 20:04