I am stuck on a question involving a security proof. Any Hints on how to approach this is helpful and greatly appreciated.

Question is:

State whether the following scheme has indistinguishable encryptions in the presence of an eavesdropper and whether it is CPA-secure: In this case, the key is random $k\in \{0,1\}^n$.

To encrypt $m\in \{0,1\}^{n+1}$, pick a random $r\in \{0,1\}^n$, and send $\langle r, G(r)\oplus m\rangle$, where $G$ is a PRG with expansion factor $n+1$.

I think it is CPA- secure, but am having a hard time proving it. My rough idea is, given a PPT adversary A, construct an algorithm D, takes input $w\in \{0,1\}^{n+1}$, with no oracles. But how would D answer queries? Its not like the case where a PRF is used in place of $G$, when D can use its oracle to distinguish a random function from a pseudorandom function.

  • 1
    $\begingroup$ Hint: tell me where the encryption/ decryption algorithms use the secret key. $\endgroup$ – Mikero Feb 15 '17 at 0:17
  • $\begingroup$ It does not use the key at all. How does that help at all though? $\endgroup$ – hlcrypto123 Feb 15 '17 at 0:18
  • $\begingroup$ The key is what allows a legitimate recipient to decrypt but not an eavesdropper. $\endgroup$ – fkraiem Feb 15 '17 at 7:58
  • $\begingroup$ It's clearly not. given $C = (r',C')$ you can compute $m=C' \xor G(r')$. Notice that $G$ is public and known by everyone. $\endgroup$ – AntonioFa Feb 16 '17 at 8:43
  • $\begingroup$ Oh Yes if $G$ was known publicly then this question is easy, but that was one of the things I was not sure about. $\endgroup$ – hlcrypto123 Feb 17 '17 at 21:50

Your Answer

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

Browse other questions tagged or ask your own question.