Provable Security

FJW and Lukas

Modern cryptography is based on security-proofs. We will demonstrate how these work, why they are desirable and what their limitations are.

Even the use of secure primitives like AES or RSA does not guarantee that the end-result is secure as well. In recent years breaks of modern primitives have in fact become exceedingly rare, yet stories like the KRACK-attack or ROBOT keep appearing.

The obvious answer to these problems would be to proof that our protocols are secure. While that may sound great in theory, there are many issues as well:

• Proving (almost) anything secure, would require to solve a millennium-problem.


• Given the above, assumptions are required; but which assumptions are reasonable?


• The word “secure” may seem intuitive, but can we formally define it? And can something be too secure?


• Idealizing primitives can solve many problems, but what about over-idealizations?


• Can backdoors be necessary to prove security?


• A proof can only show the absence of attacks in a certain model. What about attacks outside those models?