skip to main content

Formal certification of game-based cryptographic proofs

Zanella Béguelin, Santiago José (1981-....) ; Barthe, Gilles (1967-....) ; Institut national de recherche en informatique et en automatique Unité de recherche France Sophia Antipolis, Alpes-Maritimes ; École nationale supérieure des mines Paris

Paris : MINES ParisTech, 2011

Accessible en ligne. Accessible en version papier

  • Titre:
    Formal certification of game-based cryptographic proofs
  • Auteur: Zanella Béguelin, Santiago José (1981-....)
  • Autre(s) auteur(s): Barthe, Gilles (1967-....) ;
    Institut national de recherche en informatique et en automatique Unité de recherche France Sophia Antipolis, Alpes-Maritimes ;
    École nationale supérieure des mines Paris
  • Sujets: Jeux vidéo -- Thèses et écrits académiques ;
    Langages de programmation -- Thèses et écrits académiques ;
    Probabilités -- Thèses et écrits académiques ;
    Cryptographie -- Thèses et écrits académiques
  • Description: Thèse de doctorat
    Les séquences de jeux sont une méthodologie établie pour structurer les preuves cryptographiques. De telles preuves peuvent être formalisées rigoureusement en regardant les jeux comme des programmes probabilistes et en utilisant des méthodes de vérification de programmes. Cette thèse décrit CertiCrypt, un outil permettant la construction et vérification automatique de preuves basées sur les jeux. CertiCrypt est implémenté dans l'assistant à la preuve Coq, et repose sur de nombreux domaines, en particulier les probabilités, la complexité, l'algèbre, et la sémantique des langages de programmation. CertiCrypt fournit des outils certifiés pour raisonner sur l'équivalence de programmes probabilistes, en particulier une logique de Hoare relationnelle, une théorie équationnelle pour l'équivalence observationnelle, une bibliothèque de transformations de programme, et des techniques propres aux preuves cryptographiques, permettant de raisonner sur les évènements. Nous validons l'outil en formalisant les preuves de sécurité de plusieurs exemples emblématiques, notamment le schéma de chiffrement OAEP et le schéma de signature FDH.
    The game-based approach is a popular methodology for structuring cryptographic proofs as sequences of games. Game-based proofs can be rigorously formalized by taking a code-centric view of games as probabilistic programs and relying on programming language techniques to justify proof steps. In this dissertation we present CertiCrypt, a framework that enables the machine-checked construction and verification of game-based cryptographic proofs. CertiCrypt is built upon the general-purpose proof assistant Coq, from which it inherits the ability to provide independently verifiable evidence that proofs are correct, and draws on many areas, including probability and complexity theory, algebra, and semantics of programming languages. The framework provides certified tools to reason about the equivalence of probabilistic programs, including a relational Hoare logic, a theory of observational equivalence, verified program transformations, and ad-hoc programming language techniques of particular interest in cryptographic proofs, such as reasoning about failure events. We validate our framework through the formalization of several significant case studies, including proofs of security of the Optimal Asymmetric Encryption Padding scheme against adaptive chosen-ciphertext attacks, and of existential unforgeability of Full-Domain Hash signatures.
  • Éditeur: Paris : MINES ParisTech
  • Date de publication: 2011
  • Format: Adobe Acrobat
  • Langue: Anglais
  • Source: Mines ParisTech (catalogue)

Recherche dans les bases de données distantes en cours. Merci de patienter.

  • Recherche
  • dansscope:(33PSL-CNSAD),scope:(33PSL-EHESS),scope:(33PSL-PSL_OMEKA),scope:(33PSL-MINES),scope:(33PSL-EFEO),scope:(33PSL-CNSMDP),scope:(33PSL-CHIMIE),scope:(33PSL),scope:("DAU"),scope:(33PSL-CDF),scope:(33PSL-ENS),scope:("33PSL-OBSERV"),scope:("33PSL-ESPCI"),scope:(33PSL-CURIE),scope:(33PSL-ENSBA),scope:("33PSL-ENC"),scope:(33PSL-PSL_STAR),scope:(33PSL-PSL_SFX),scope:("33PSL-EPHE"),scope:(33PSL-ENSAD),primo_central_multiple_fe
  • Afficher ce qui a déjà été récupéré