Computer-Aided Security Proofs for the Working Cryptographer

Advances in Cryptology, CRYPTO 2011 |

Published by Springer

Best Paper Award

Publication | Publication

We present an automated tool for elaborating machine-checkable security proofs from proof sketches—compact, formal representations of the essence of a proof as a sequence of games and hints. Proof sketches are checked automatically using off-the-shelf SMT solvers and automated theorem provers, and then compiled into verifiable proofs in the CertiCrypt framework. The tool supports most commonly used reasoning patterns, is significantly easier to use than its prede- cessors, and is a plausible candidate for adoption by working cryptographers. We illustrate its application to proofs of the Cramer-Shoup cryptosystem and Hashed ElGamal encryption.