I'm looking at the following idea for using a symmetric key to encrypt multiple messages (back & forth communication between Alice & Bob). It can be summarized as follows:

  • Both sides agree upon a key
  • Both sides generate $2^n$ bits using a PRG (which I believe is seeded with the key). Since PRGs are deterministic, both sides have the same $2^n$ bits.
  • When one side wants to encrypt the message, they choose k random indices, where k is the length of the message, & xor the message with the bits at those k indices. They transmit the message & the indices.
    • The attacker doesn't know the underlying bits, so having the indices are useless
  • The other side receives the indices / message & performs the reverse process as above

visualization of scheme

What I'm confused about is the need for the PRG at all. For example: Why don't both sides just agree to repeat the key (which is secret from the attacker) for $\frac{2^n}{k}$ times where k is the length of the key.

Given that the attacker doesn't know the key, this should still be secure, no?

Theoretically: Both sides could just agree to make {1, 2, 3, 4 ... $2^n$} the "random" bits since if they have the ability to negotiate on a shared secret key, they should also have the ability to negotiate on a way to generate the buffer, right?

  • $\begingroup$ This is not really one-time-pad where the key is uniform random. Actually, the $2^n$ bits are the output of PRG to reduce the communication. I did not like the idea, instead, they can have a stream cipher and the index is the IV, and the key is fixed so that no need to store the PRG's output. Your question is essentially dupe of Taking advantage of one-time pad key reuse? $\endgroup$
    – kelalaka
    Commented Dec 22, 2021 at 20:48

1 Answer 1


It is called One Time Pad for a reason: you are only supposed to use it once. If you repeat the same key in two different portions of the plaintext, this is effectively as if you were reusing the key, which leads to problems. More precisely, if you have two messages $m_1$ and $m_2$ encrypted with the same key $k$ as $m_1\oplus k$ and $m_2\oplus k$, an attacker can XOR these two encryptions together to cancel out the key and get $m_1\oplus m_2$, which, although it does not reveal $m_1$ nor $m_2$ directly, is enough to learn something about these values.

An alternative is not to reuse the key, but to use a key that is as long as the message. However, this would be very expensive, so we use a PRG to be able to "bootstrap" a shorter key into a new key that is indistinguishable from random and simultaneously is as long as the message.

  • 4
    $\begingroup$ Addition: and when we use a PRG "to generate random numbers for a One-Time-Pad", this is no longer a true One Time Pad. It becomes a stream cipher, and is no longer information-theoretically secure. $\endgroup$
    – fgrieu
    Commented Dec 22, 2021 at 20:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.