Modèle standard (cryptologie)

En cryptologie, dans le contexte des preuves de sécurité, le modèle standard^{[Note 1]} désigne un cadre conceptuel dans lequel on s'interdit de considérer des modèles idéalisés (modèles de l'oracle aléatoire, du chiffre idéal, du groupe générique, etc.) des objets mathématiques en jeu^[1]. Une preuve dans le modèle standard est considérée beaucoup plus solide qu'une preuve dans un modèle idéal^[2], ce qui est appuyé par l'existence de constructions sûres dans ces modèles idéaux mais cassés dans toute implémentation concrète^{[Note 2]}.

Toutefois, de telles preuves sont notoirement difficiles à construire^[1],[3],[4] et parfois même impossibles^[5],[6],[7]. Ainsi de nombreuses constructions sont seulement analysées en dehors de ce modèle^{[Note 3],[8]}.

Définition

Une construction cryptographique est considérée sûre dans modèle standard lorsque l'adversaire n'est limité que par ses capacités calculatoires^[1],[2] ; autrement dit les seules hypothèses faites portent sur la complexité algorithmique de certains problèmes. Cela fait contraste avec les preuves reposant sur une simplification des primitives (par exemple le modèle du groupe générique, faisant abstraction d'un groupe particulier) ou sur des hypothèses de confiance (par exemple le modèle de la chaîne de référence, qui fait abstraction d'une étape préliminaire de négociation entre participants).

Pour certains auteurs^[2],[9], les hypothèses calculatoires elles-mêmes doivent être « standard » pour que la preuve soit considérée valide dans ce modèle. Concrètement, cette contrainte additionnelle élimine les variantes paramétrisées (dites « q-type »), les variantes fortes (comme le problème RSA fort), et les variantes ad hoc (telles que les hypothèses de séparation DDH-CDH dans les groupes bilinéaires) ^{[Note 4],[10]}. Sans que la liste soit exhaustive, les hypothèses suivantes sont généralement considérées standard^[11] : le problème du logarithme discret, le problème de Diffie-Hellman, la factorisation, le problème RSA, le problème de la résiduosité quadratique, et les problèmes équivalents à ceux-ci.

Constructions sûres dans le modèle standard

Peu de constructions connues sont sûres dans le modèle standard. Le premier cryptosystème à clé publique prouvé sûr^{[Note 5]} dans le modèle standard est le cryptosystème de Cramer-Shoup en 1998^[12]. Les fonctions de hachage caméléon ont été introduites la même année par Hugo Krawczyk et Tal Rabin^{[13],[Note 6],[14]}. Le premier schéma basé sur l'identité et la première signature prouvée sûre^{[Note 7]} reposant dans le modèle standard sur le problème de Diffie-Hellman sont dus à Brent Waters en 2005^[15]. En 2009, Hohenberger et Waters produisent le premier schéma de signature prouvé sûr reposant sur le problème RSA dans le modèle standard^[9]. Le premier échange de clé authentifié et le premier mécanisme d'encapsulation de clé prouvés sûrs dans le modèle standard sont dus à Tatsuaki Okamoto en 2007^[16], et un protocole en un tour a été proposé en 2015^[17].