### Automated Security Proofs with Sequences of Games

Bruno Blanchet and David Pointcheval

##### Abstract

This paper presents the first automatic technique for proving not only protocols but also primitives in the exact security computational model. Automatic proofs of cryptographic protocols were up to now reserved to the Dolev-Yao model, which however makes quite strong assumptions on the primitives. On the other hand, with the proofs by reductions, in the complexity theoretic framework, more subtle security assumptions can be considered, but security analyses are manual. A process calculus is thus defined in order to take into account the probabilistic semantics of the computational model. It is already rich enough to describe all the usual security notions of both symmetric and asymmetric cryptography, as well as the basic computational assumptions. As an example, we illustrate the use of the new tool with the proof of a quite famous asymmetric primitive: unforgeability under chosen-message attacks (UF-CMA) of the Full-Domain Hash signature scheme under the (trapdoor)-one-wayness of some permutations.

Note: Fixes an error in Definition 1.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2006
DOI
10.1007/11818175_32
Keywords
security proofautomatic proofssequences of gamescomputationally sound
Contact author(s)
bruno blanchet @ inria fr
History
2020-12-03: last of 3 revisions
See all versions
Short URL
https://ia.cr/2006/069

CC BY

BibTeX

@misc{cryptoeprint:2006/069,
author = {Bruno Blanchet and David Pointcheval},
title = {Automated Security Proofs with Sequences of Games},
howpublished = {Cryptology ePrint Archive, Paper 2006/069},
year = {2006},
doi = {10.1007/11818175_32},
note = {\url{https://eprint.iacr.org/2006/069}},
url = {https://eprint.iacr.org/2006/069}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.