F is a length preserving PRP.
Encryption scheme $\Pi$ for messages of n/2 bits where:
Enc: Select a random string $r\in\{0,1\}^{n/2}$ and output $c\leftarrow F_k(r||m)$

Prove: If this scheme is CPA secure or not.

My approach so far has been to Prove this using reduction by designing an Attacker $A$ who can break this scheme with non negligible probability, Using that attacker I am trying to break PRP with non negligible probability but that would give a contradiction and hence this scheme is CPA Secure. Am I going wrong somewhere?

Also can we ever say with 100% certainty that a scheme is secure by this approach?

Also, my understanding to prove these kind of things is :

  • To prove that a give scheme is insecure design an attacker for the given scheme
  • To prove that a given scheme is COA/CPA secure design an attacker who can break the scheme with non negligible probability and reach a contradiction somewhere
  • Am I missing something here?

    Is the above scheme CPA secure? How to prove it?

    • $\begingroup$ They will be different since we have a random string $r$ which will get padded with the message every time. $\endgroup$ – vik-y Mar 7 '16 at 1:58
    • $\begingroup$ Oh, yeah, I missed that part. ​ I think the idea will be showing that PRPs with large domain are also PRFs. ​ ​ ​ ​ $\endgroup$ – user991 Mar 7 '16 at 2:00
    • $\begingroup$ I think that part is obvious right? PRPs are a special case of PRF. What do you think about CPA security of this scheme? Will reduction be a right approach? $\endgroup$ – vik-y Mar 7 '16 at 2:03
    • $\begingroup$ PRPs with small domain are not PRFs. ​ ​ ​ I think the flag bad should be set if and only if the random function is called more than once on ​ r || challenge_plaintext . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Mar 7 '16 at 2:13
    • $\begingroup$ This one is straightforward: the PRP distinguisher uses its internal oracle to emulate $\Pi$, and uses the assumed CPA adversary to distinguish messages produced by F from random ones. $\endgroup$ – fkraiem Mar 7 '16 at 4:59

    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.