4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Ilmari Karonen Dec 13 '17 at 17:45
  • $\begingroup$ @IlmariKaronen I appreciate your help, it looks nicer now. Also, yes, I'm going to add those notations. Thanks! $\endgroup$ – ThomasWest Dec 13 '17 at 20:13
1
$\begingroup$

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?

| improve this answer | |
$\endgroup$
  • $\begingroup$ I see I guess it will not make it CCA-Secure anymore. Anyway, you didn't make a comment on the rest of them, does it mean that my thoughts are correct? $\endgroup$ – ThomasWest Dec 13 '17 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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