# Security properties of an encryption scheme built from a PRP and a PRG

Note: This was my in-class problem last week and potentially will be on the exam tomorrow. Thus, I want to reconfirm my thoughts so that I'll be ready to face this type of question (if appear) tomorrow.

Question:

Assume I have an encryption where the key is computed using a PRP $$P$$ and the message is computed using a PRG $$G$$ so that

$$E(k,m) = ( P(k,r) , G(r) \oplus m )$$

(also given) $$k \in K = X = Y = \{0,1\}^n$$ and $$m \in M = \{0,1\}^{2n}$$

$$P$$ is the PRP, $$G$$ is the PRG, and $$k$$ and $$m$$ are the key and the message belonging to the keyspace $$K$$ and message space $$M$$ respectively, and $$r$$ is a random bitstring.

My thoughts:

First, I say that $$E(k,m)$$ is not perfectly secure because $$|M| > |K|$$.

Second, I can argue that $$E(k,m)$$ is indistinguishable because the message is generated by a PRG (assuming that the seed is independent & uniformly distributed).

Third, I claim that $$E(k,m)$$ is CPA-Secure too because the PRG makes the message non-deterministic.

Fourth, I think $$E(k,m)$$ is CCA-Secure too, right?

Please feel free to correct me, I don't mind criticism. I think some of my thoughts are still wrong. I just want to feel ready for the exam.

• Hi, ThomasWest. I edited your question to format it a bit more nicely, but please check that I didn't introduce any mistakes while doing so. Also, could you please clarify your notation a bit? I assumed that $P$ is the PRP, $G$ is the PRG, and $k$ and $m$ are the key and the message belonging to the keyspace $K$ and message space $M$ respectively, and I would guess that $r$ is probably a random bitstring. But what are the sets $X$ and $Y$? Good luck with your exam! – Ilmari Karonen Dec 13 '17 at 17:45
• @IlmariKaronen I appreciate your help, it looks nicer now. Also, yes, I'm going to add those notations. Thanks! – ThomasWest Dec 13 '17 at 20:13

Fourth, I think $E(k,m)$ is CCA-Secure too, right?
Consider this: what if an attacker takes a valid ciphertext $E(k,m) = ( P(k,r) , G(r) \oplus m )$ and flips a bit, so that it is $P(k, r), G(r) \oplus m \oplus 1$. What would happen if you gave this altered ciphertext to the decryptor?