CPA and pseudorandom generator

Question

Just started learning about Cryptography and Network Security in general, and I can't seem to grasp the understanding of the following question. Please correct me if I am misunderstanding anything.

Imagine that there exists a Pseudorandom Generator that simply doubles all key length, G(n) = {0,1}^n -> {0,1}^2n. If I have a key k and send it over to G, I now have an encrypted G(k) = k', and k' is twice the length of k. If I have a message m, encrypt it with k' with m XOR k', is it CPA secure or not?

I understand that with a CPA attack, the attacker can send any plaintext into the encryption mechanism and receive a ciphertext out of it.

My confusion is that, in the case above, what exactly is the attacking sending the plaintext into? Is it the Pseudorandom generator? Does the attacker know what type of pseudorandom generator it is? But since the attacker doesn't even have the original cipher-text or the original key, what use is it for the attacker to keep on sending his own plain-texts and get back his own cipher-texts?

Sorry if this is very confusing, but I really want to understand this before moving onto more advance topics.

Answer 1

I want to make this clear: You're defining $E_K(m):\{0,1\}^{2n}\times \{0,1\}^n\rightarrow \{0,1\}^{2n}$ as $E_K(m):=G(K)\oplus m$. This construction is well-known in the literature. It can't be CPA secure because it is a deterministic algorithm. However as discussed in Katz' and Lindell's book Introduction to Modern Cryptography it is secure against passive eavesdroppers only observing a single messages.

As for your questions:

What exactly is the attacker sending the plaintext into?

He sends the plaintext into the encryption function and gets the ciphertext in return. He doesn't learn $K$ at any point but learns encryptions using $K$. The process of acquiring the ciphertext to a given plain text is called "querying the encryption oracle for X"

Does the attacker know what type of pseudorandom generator it is?

Yes, the attacker may know which primitive is used to instantiate the PRG and in a good system usually does. But this won't help him breaking the scheme as the security fully relies on the key(s) as per Kerckhoff's principles.

But since the attacker doesn't even have the original cipher-text or the original key, what use is it for the attacker to keep on sending his own plain-texts and get back his own cipher-texts?

The usual CPA scenario indeed hands a challenge cipher text over to the adversary which he has to decrypt. (It's a little different but being able to decrypt always counts as a break).

---

Here's a quick outline on how to break the scheme:

Suppose you want to decrypt a cipher text $c$. You query your encryption oracle for a random message $r$. You'll get $c'=G(K)\oplus r$ in return. You are now able to compute $G(K)=r\oplus c'$. As $c=G(K)\oplus m$, you can obtain $m$ as $m=G(K)\oplus c=r\oplus c' \oplus c$.