Are there any ways better than peer review to validate a security proof? Are there any ways to make your security proof easier to validate; using a simulator based proof instead of a game based proof?

Can we "reduce" a security proof to something validate-able in code?

  • 8
    $\begingroup$ There are tools and languages for computer-aided proving. If these are used then you can run the program yourself to convince yourself that the proof is correct (the program is also proven correct). For the majority of crypto proofs though peer review is the best we have (and even then things may slip as they e.g. did with the original GCM proof). $\endgroup$ – SEJPM Jul 16 '19 at 12:35
  • 1
    $\begingroup$ Everything you can codify, you can check automatically. But you always have the problem, that a proof based on wrong / missing assumptions might be useless. If you codify assumptions, you need assumptions about assumptions. So the problem remains, if those are correct and make sense. $\endgroup$ – tylo Jul 16 '19 at 15:15
  • 3
    $\begingroup$ Well, cryptography is math really, and since mankind has defined math pretty well, a few things can be proven conclusively within the existing frameworks. Unfortunately that isn't the case for most cryptography. So e.g. when proving a mode of operation to be secure, we have to assume that the underlying block cipher is secure, and that's one of those things that cannot be proven (just giving one example here, and trying to avoid a discussion on what can be proven and what cannot). $\endgroup$ – Maarten Bodewes Jul 17 '19 at 12:49
  • 1
    $\begingroup$ @SEJPM And the proof of RSA-OAEP, and the proof of PACE (for which I explicitly said that the proof wasn't conclusive and relied on assumptions - sigh)... Often the proof needs to be adjusted later on. With a bit of luck the initial requirements and properties of the studied algorithm are kept within usable bounds when that happens. $\endgroup$ – Maarten Bodewes Jul 17 '19 at 12:52

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.