Paul Christiano writes (source):

I’ll assume that we have some 256 bit cryptographic hash function F [...] The first important observation is that a 256-bit shared secret allows Alice and Bob to talk for as long as they want, by just using their secret to create a new pseudorandom pad for each message. That is, if Alice and Bob share a secret s, then Alice can send a message m by picking k at random, and sending the pair (k, F(sk) ⊕ m). It’s easy to confirm that Bob can still get the message, and if F is random then this is secure.

This is confusing to me. I was under the impression that there is no way of using a one time pad based on a shared secret of $n$ bits to transmit securely more than $n$ bits but this seems to imply it is possible by sending messages with $k=1,2,\dots$

What am I misunderstanding?


This is called a stream cipher. It is a practical instantiation of the one-time pad model, where we encrypt a message $m$ with a single-use pad $p$ by using the ciphertext $c = m \oplus p$.

When $p$ is generated from a short key $k$ by $p = F(k)$, obviously $c$ and $m$ are not technically independent—we can't say of the probabilities that $P(m \mid c) = P(m)$, because obviously some pads are impossible—but the advantage the adversary has at breaking the cryptography knowing that we used $F(k)$ is limited by their advantage at distinguishing $F(k)$ from a uniform random bit string.

If $k$ is uniform random and $F$ is, e.g., ChaCha or SHA-256, the adversary has no hope of doing this without a breakthrough in cryptanalysis.


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