Prove that the given scheme is CPA secure or not

Given:

F is a length preserving PRP.
Encryption scheme $\Pi$ for messages of n/2 bits where:
$m\in\{0,1\}^{n/2}$
$k\in\{0,1\}^n$
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?

• They will be different since we have a random string $r$ which will get padded with the message every time. – vik-y Mar 7 '16 at 1:58
• Oh, yeah, I missed that part. ​ I think the idea will be showing that PRPs with large domain are also PRFs. ​ ​ ​ ​ – user991 Mar 7 '16 at 2:00
• 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? – vik-y Mar 7 '16 at 2:03
• 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 . ​ ​ ​ ​ ​ ​ ​ ​ – user991 Mar 7 '16 at 2:13
• 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. – fkraiem Mar 7 '16 at 4:59