I know for proving a scheme is not IND-CPA or not IND-CCA you can construct an Adversary which has an unfair advantage in an experiment/game, but how would you prove a scheme is IND-CPA or IND-CCA?

  • 2
    $\begingroup$ usually? by constructing an algorithm that - given the ability to break IND-CCA / IND-CPA - can break the assumed hard problem in polynomial time which proofs there can be no such algorithm because the assumption is that the problem is hard. $\endgroup$ – SEJPM May 8 '16 at 13:25
  • $\begingroup$ As @SEJPM said: one proceeds by contrapositive, one suppose that such adversary with unfair advantage exists and proves that that adversary can be used to break a well known assumption, e.g.: one Adversary breaking some scheme can be used to factorise a composite integer (as defined in RSA). As today, after a huge effort and time spent on the factorisation problem, we dont have any efficient algorithm to factorise, that proves that the adversary do no extist, so the scheme is IND-CPA or IND-CCA secure. $\endgroup$ – ddddavidee May 10 '16 at 8:34

As SEJPM said in his comment: one proceeds by contrapositive, first suppose that such an adversary with an unfair advantage exists and use that adversary to break a well known assumption, e.g.: the adversary can be used to factorise a large composite integer (as defined in RSA).

As of today, we have no efficient algorithm to factorise large composite integers, even after years of research spent trying to achieve this. So from this it is safe to assume that the problem is hard, and that no such adversary exists. The scheme is IND-CPA or IND-CCA secure, because if it was not, an adversary breaking the scheme will break this well known problem.

The next step is to proceed by transforming an instance of the well known problem (a composite integer to be factored) into an instance of the scheme, if the adversary is able to break the scheme with a non-negligible advantage, it will also inadvertently solve the hard problem, this is a contradiction as we have assumed the problem to be hard.


Your Answer

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

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