1
$\begingroup$

While reading Katz & Lindell's textbook (2nd edition) if found three main security definitions: ING-EAV-Security, ING-CPA-Security and ING-CCA-Security. (From this forum I know there are more, but these are the most basic ones). I also read, that ING-CPA-Security implies ING-EAV-Security and that ING-EAV-Security is weaker than ING-CPA-Security which is weaker than ING-CCA-Security.

My question: Does ING-CCA-Security also implie ING-CPA-Security?

$\endgroup$
3
  • 1
    $\begingroup$ Hint: How do the CCA definition(s) compare to the CPA ones, in particular the things an adversary can do? $\endgroup$
    – SEJPM
    Mar 9, 2021 at 14:01
  • $\begingroup$ I know what you mean: The CPA Experiment is included in the CCA experiment, therefore CCA should implie CPA, but because I couldn't find it in the book, I was/am unsure about it $\endgroup$
    – Titanlord
    Mar 9, 2021 at 14:06
  • 1
    $\begingroup$ In that case, could you perhaps find a proof yourself? That is, a reduction that if an adversary wins the CPA experiment against a scheme, it will also win the CCA one? $\endgroup$
    – SEJPM
    Mar 9, 2021 at 14:11

1 Answer 1

3
$\begingroup$

My Sketch on the reduction proof:

  1. Basic Assumption: I got a Cryptosystem #1 that is CCA secure

  2. Based on this Cryptosystem I can build a CPA secure Cryptosystem #2, and I assume, that an adversary can break it with non negligible probability

  3. Therefore I can build a Reduction: R can simulate the CPA game with A and just gives the messages of A to his challenger and the response back to A. R then outputs the result of A.

  4. Because A has a non negligible probability in breaking #2, R also has a non negligible probability in breaking #1, which gives a contradiction to the basic assumption

  5. Therefore CCA implies CPA

I hope the basic idea is correct.

$\endgroup$
1
  • 1
    $\begingroup$ And, a good exercise is to write it in a more formal way. $\endgroup$
    – kelalaka
    Mar 9, 2021 at 18:13

Your Answer

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

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