Score:0

Why do we need to use PRGs to generate random numbers for a one-time-pad?

fr flag

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?

kelalaka avatar
in flag
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?](https://crypto.stackexchange.com/q/59/18298)
Score:2
ru flag

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.

fgrieu avatar
ng flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.