question on encryption of multiple distinct messages

Question

When I study symmetric encryption, it is quite straightforward to understand the following: in the presence of eavesdropper, simply using a PRG $G(k)$ and XORing multiple messages won't provide indistinguishability in the similar fashion as for a single message.

But what happens for multiple distinct messages? Will a simple PRG $G(k)$ provide indistinguishability?

I know there is discussion on deterministic CPA-secure schemes which could use synthetic IV, etc. But do we really need to go that far?

What is the difference? the distinct messages make the (key, message) pair distinct already? does it depend on how we define indistingushability?

Thanks!

Answer 1

It does not work either. There are a few counter examples:

Let $x=G(k)$ be the key stream, which I understand you want to use to encrypt multiple messages

1 $m_1=0^l$ and $m_2=r \in\{0,1\}^l$, once you encrypt $m_1$, the ciphertext $m_1\oplus x = x$ is exactly the key stream, that can be used to decrypt the ciphertext of $m_2\oplus x\oplus x=m_2$. Note $m_1$ and $m_2$ are distinct.

2 Let $m \in \{0,1\}^{l-1}$, $m_1=m||0$, $m_2=m||1$, $m_3 =r \in\{0,1\}^l$, then given the ciphertext of $m_1$, in a CPA game, the adversary can easily distinguish $m_2$ and $m_3$. All 3 messages are distinct.

The main problem is that distinct means the messages are not equal, but nothing more on their distributions. Therefore, it is insufficient to ensure the indistinguishability of ciphertexts.

When you use an iv, which is a long enough random string, the iv is used as input to $G$ (well I am abusing the syntax a little bit), so you have $G(k,iv)$ which produces a different and independent key stream per iv.

Answer 2

No, a PRG doesn't provide indistinguishability when encrypting multiple distinct messages.

Indistinguishability always refers to random. Can you distinguish if a given stream of bits is the output of some kind of encryption or is it "just random", i.e. obtained by repeating N times an experiment with uniform distribution?

K XOR m1 XOR K XOR m2 = m1 XOR m2, by the properties of the XOR.

m1 and m2 in general is not uniform at all. Take for example the English language. We know that the most common occurrences are E,T,A,N,O,I,R,S (not sure about the order), and so on. This means that the '1' bit occurs with probability p, '0' with probability 1-p.

Let z(X) be the number of zeros in the ASCII encoding of letter X.

The expected value of z (number of zeros) in an English message m is:

z(m)=p('E')z('E')+p('T')z('T')+p('A')z(A')+...

What about m1 XOR m2? The most common letters are E XOR E, T XOR T, A XOR A, and so on.

Therefore, the expected value of z in the sum of two English messages is:

z(m1 XOR m2)=p('E' XOR 'E')z('E' XOR 'E')+p('T' XOR 'T')z('T' XOR 'T')+...

which is not what you would expect if m1 xor m2 was really random.