I am confused by how game-based proofs fit in the provable security paradigm. I understand reductions in the style of proving secrecy of RSA reducing it to integer factorization. However, when proving indistinguishability properties with game-based proofs, I cannot identify the underlying hard mathematical problem of the reduction.

  • 1
    $\begingroup$ Aren't game based proof a method of establishing that a problem reduces to a hard problem, rather than a hard problem by itself? Wouldn't it depend therefore on the problem being analyzed? $\endgroup$ – Maarten Bodewes Apr 25 '20 at 22:07
  • 1
    $\begingroup$ Yes, you're right: they are a method to find a reduction. So, I guess I'm looking for examples of hard problems to which a game-based proof shows a reduction for. $\endgroup$ – synack Apr 25 '20 at 23:47

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.