4
$\begingroup$

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?

$\endgroup$
4
  • 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, 2019 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, 2019 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, 2019 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, 2019 at 12:52

1 Answer 1

1
$\begingroup$

Are there any ways better than peer review to validate a security proof?

Peer review is and will always be (in my opinion) some of the best methods to verify a claim in general. However formal verification has started to gain ground on critical components, see for example in critical code components used in the software used in airplanes. However I doubt this trend has landed in the math field, not to mention crypto field.

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

I didn't understand exactly the question.

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

There is this framework called certicrypt which was first published here and you can find their code here. It is written in Coq, so the proof itself has to be written in Coq. It has been is used to verify game based proofs, for example ElGamal, HashedElGamal, OAEP, FDH, and some ZKP protocols. A lot of examples can be found here.

$\endgroup$

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.