2
$\begingroup$

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?

    Improve this question
    $\endgroup$
    9
    • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 4:59

    0

    Reset to default

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

    Browse other questions tagged or ask your own question.