En cryptographie, une preuve de sécurité est la preuve qu'un ensemble d’algorithmes cryptographiques (aussi appelé schéma) respecte les définitions de sécurité qui leur sont requises. Ces définitions de sécurité sont données dans les descriptions de classes de schémas appelées primitive cryptographique. Certains travaux en cryptologie consistent à définir des primitives afin d’uniformiser ces définitions, comme ceux de Bellare, Micciancio et Warinschi pour la signature de groupe en 2003^[1], concept qui a été défini pour la première fois par Chaum et van Heyst en 1991^[2].

Une des premières preuves de sécurité est la sécurité au sens de la théorie de l’information du masque jetable. Cette notion est introduite par Claude Shannon, dans son article Communication theory of secrecy systems paru en 1949^[3], et la sécurité du masque jetable a été démontrée dans cet article. Le masque jetable étant un schéma de chiffrement, la notion de sécurité requise est l'indistingabilité vis-à-vis de l’uniforme. Autrement dit, l’objectif est qu’aucun adversaire ne puisse dire si un message chiffré est une chaîne de bits aléatoires ou bien cachent un message. Informellement cela correspond à répondre à une question par oui ou non sur le message, on dit alors qu’on a dérivé un bit d’information sur le message. Si cela est impossible à réaliser, alors il est impossible de déduire quoi que ce soit sur le message initial.

Comme il est difficile d'atteindre la sécurité au sens de la théorie de l’information, les preuves cryptographiques reposent souvent sur des hypothèses calculatoires, où la notion de sécurité se ramène alors à la complexité supposée de ces hypothèses. La cryptanalyse d’un ensemble de schémas reposant sur une hypothèse commune est alors ramenée à l'étude de la difficulté de cette hypothèse. On parle parfois de réduction de sécurité, en référence à la réduction polynomiale en théorie de la complexité.

Le domaine de la cryptographie où les schémas sont prouvés sûrs est appelé la sécurité prouvable.

Les approches vis-à-vis de la sécurité sont historiquement différentes entre la cryptographie symétrique et la cryptographie asymétrique.

Même s'il existe des schémas prouvés en cryptographie à clef secrète, comme le générateur pseudo-aléatoire de Blum Blum Shub qui est sûr sous le problème de la résiduosité quadratique, il a souvent été préféré dans les utilisations pratiques les schémas qui résistaient aux techniques de cryptanalyses connues pour des raisons d'efficacité. Le NIST avait alors recommandé SHA-1 et SHA-2 sur cette base. Mais en 2012, Keccak devient le nouveau standard en termes de fonction de hachage cryptographique^[4], est prouvé sûr sous des hypothèses sur les fonctions éponges.

En cryptographie asymétrique en revanche, on a longtemps considéré les schémas prouvés sous des hypothèses calculatoires. La nécessité d'avoir des schémas très rapides étant couverte par la cryptographie à clef privée, et l'utilisation de la cryptographie asymétrique étant souvent faite par le biais de la cryptographie hybride. Par exemple le cryptosystème de ElGamal est prouvé sous l'hypothèse du problème de décision de Diffie-Hellman (en), qui implique la difficulté du problème du logarithme discret, qui est un problème d'arithmétique modulaire. La preuve du sécurité du cryptosystème de ElGamal est faite par réduction, autrement dit pour prouver que la notion de sécurité résiste, on prouve que cette notion dans le schéma est au moins aussi difficile que les hypothèses de sécurité^[5] à un facteur polynomial près. On se retrouve donc, moyennant un surcoût considéré comme négligeable, à résoudre un problème supposément difficile.

Une manière d’effectuer une réduction de sécurité consiste à effectuer une réduction polynomiale des hypothèses de difficulté vers les notions de sécurité à prouver. C’est le cas par exemple de la preuve du cryptosystème d'ElGamal, ou du cryptosystème de Goldwasser-Micali.

En sécurité prouvable, on mesure la qualité d’un attaquant par son avantage, c'est-à-dire la probabilité qu’il réussisse à casser une propriété de sécurité (par exemple produire un faux pour les signatures numériques). Lors d’une réduction de sécurité on part d’un attaquant contre la propriété de sécurité, ayant donc un avantage supposé, et l’on arrive à un attaquant contre une hypothèse de sécurité, avec un avantage polynomialement plus faible. C'est l'étude de ce polynôme qui est importante, puisque dans un système pluri-utilisateur, il se peut que la réduction dépende du nombre d’utilisateurs, une méthode générique classique étant par exemple de deviner quel utilisateur va être attaqué par l’adversaire pluri-utilisateur avant d’appliquer la sécurité du système à utilisateur unique sur cet utilisateur cible. Cela donne pour un avantage supposé ε pour le système à utilisateur unique un avantage de ${\displaystyle \varepsilon /|{\text{utilisateurs}}|}$^[6], ce qui signifie que pour le réseau internet, il y a en 2016 une perte de sécurité de l’ordre de 2⁴¹^[7], ce qui fait que pour une sécurité multi-utilisateur de 80 bits, il faut une sécurité simple utilisateur de 121 bits, ce qui fait grandir la taille des clefs en conséquence (par exemple la taille des nombres premiers choisis pour la Signature RSA, et par conséquent la taille de la signature).

Travailler à avoir une meilleure estimation de la perte de sécurité permet ainsi d’améliorer notre connaissance de la sécurité des systèmes cryptographiques, et dans le meilleur cas (une perte de sécurité constante), les cryptologues disent que la preuve est fine^[8].

Une preuve par jeu est parfois utilisée lorsque la définition de sécurité est donnée par un jeu cryptographique que doit gagner l’adversaire. C’est le cas par exemple de la sécurité sémantique des schémas de chiffrements. Le but étant de passer étapes par étapes du jeu originel que doit gagner l’attaquant, de le transformer étape par étape en un jeu que l’adversaire ne peut pas gagner, par exemple parce qu’il revient à résoudre un problème difficile ou parce qu’il n’y a plus d’informations sur le message initial. Le passage d’une étape à la suivante ne peut changer l’avantage et le point de vue de l’adversaire que de manière négligeable par rapport au jeu précédent. De telle manière qu’en appliquant les différentes transformations, on se retrouve avec un jeu que l’adversaire est incapable de gagner, à une distance négligeable de la notion de sécurité que l’on souhaite démontrer.

L’avantage de telles preuves est qu’elles sont faciles à vérifier, étant donné que les passages d’une étape à la suivante sont explicitées, et l’argument peut donc être vérifié pas à pas.On peut de plus étapes par étapes borner l’avantage de l’adversaire pour évaluer avec précision le facteur d’approximation de la réduction^[9].

On peut ainsi reformuler la preuve du cryptosystème d’ElGamal par des jeux cryptographiques.

Dans ce qui suit, la relation « ${\displaystyle \approx }$ » signifie que deux distributions sont statistiquement ou calculatoirement proches ; et Adv_i désigne l’avantage de l’adversaire. Pour la sécurité sémantique il s’agit de la quantité ${\displaystyle Adv=\left|{\frac {1}{2}}-\Pr[{\mathcal {A}}{\mbox{ gagne}}]\right|}$.

• Jeu 0: La sécurité sémantique du schéma. Le challenger commence par générer la paire de clefs et envoie pk = (G, q, g, h=g^a) à l’attaquant. L’attaquant renvoie alors deux message m₀ et m₁. Le challenger tire alors un bit σ à pile ou face et renvoie à l'attaquant un chiffré de m_σ : ${\displaystyle C=(m_{\sigma }\cdot h^{b},g^{b})}$. L’adversaire renvoie alors un bit σ’ et gagne si et seulement si σ = σ’.
• Jeu 1: Comme le choix de σ est indépendant de la vue de l’attaquant, on change ici le challenger pour qu’il tire le bit σ avant d’avoir vu les messages. Rien n’a changé, Adv₀ = Adv₁.
• Jeu 2: En utilisant l'hypothèse de décision de Diffie-Hellman qui dit que ${\displaystyle (g,g^{a},g^{b},g^{ab})\approx (g,g^{a},g^{b},g^{c})}$ pour a, b, c tirés uniformément dans ℤ_q, on peut remplacer le chiffré C par ${\displaystyle (m_{\sigma }\cdot g^{c},g^{b})}$. On a utilisé l’hypothèse de sécurité du problème de décision de Diffie-Hellman, ici ${\displaystyle \scriptstyle |Adv_{2}-Adv_{1}|\ \leq \ Adv^{DDH}}$.
• Jeu 3 Désormais g^c est indépendant de la clef publique, et cache donc complètement le message. Sans aucune autre hypothèse, on peut donc remarquer que ${\displaystyle m_{\sigma }\cdot g^{c}\approx g_{r}}$ pour ${\displaystyle g_{r}}$ suivant une distribution uniforme dans G. On peut donc remplacer C par ${\displaystyle (g_{r},g^{b})}$, qui constitue un chiffré complètement aléatoire et indépendant du bit σ. Dans ce jeu encore, la distribution des chiffrés par rapport au jeu précédent reste inchangée : Adv₃ = Adv₂.

Finalement on remarque que le jeu 3 ne peut pas être gagné par aucun adversaire avec une probabilité différente de 1/2. De plus la seule transformation faisant varier cette probabilité est le Jeu 2, où on utilise l’argument calculatoire de décision de Diffie-Hellman. Ce qui signifie qu’au total l’avantage d’un adversaire contre ce schéma est borné par l’avantage d’un adversaire face à DDH ; en effet

${\displaystyle {\begin{aligned}Adv_{0}&=|Adv_{3}-Adv_{0}|\\&=|Adv_{3}-Adv_{2}+Adv_{2}-Adv_{1}+Adv_{1}-Adv_{0}|\\&\leq |Adv_{3}-Adv_{2}|+|Adv_{2}-Adv_{1}|+|Adv_{1}-Adv_{0}|\\&=0+Adv^{DDH}+0=Adv^{DDH}\end{aligned}}}$

Mais que doit-on appeler difficile ? Une réponse à cette question est apportée par la théorie de la complexité à laquelle on emprunte entre autres le concept de réduction entre problèmes. Cette théorie cherche à classifier les problèmes en fonction du temps de calcul nécessaire pour les résoudre, et définit des classes de « difficulté ». En l'occurrence, la classe qui nous intéresse est celle dite non déterministe polynomiale (NP). Ce sont les problèmes dont une solution, donnée, est « facile » à vérifier (se vérifie en temps polynomial), mais risque en revanche d'être difficile (potentiellement en temps non polynomial) à trouver.

L'appartenance d'un problème à la classe NP ne signifie pas que celui-ci n'est pas résoluble en temps polynomial. En effet, tous les problèmes de P sont dans NP, et le fait de savoir si au contraire il existe des problèmes de NP qui ne sont pas dans P appelé Problème P = NP est l'une des grandes questions ouvertes en mathématiques.

En cryptographie théorique, d'autres classes de complexités sont étudiées pour déterminer ce qui est considéré difficile ou non^[10], comme AC⁰ ou NC¹ pour savoir ce qu'il resterait dans l'éventualité d'un effondrement de la hierarchie polynomiale, on sait par exemple que si les fonctions à sens unique existent, alors P ≠ NP, ce qui invaliderait un pan de la cryptographie reposant sur cette hypothèse de travail dans le cas d'un effondrement.

Les problèmes utilisés par la cryptographie sont tous dans NP : il est « facile » de coder un message, ou de décoder un message quand on en possède la clé. En revanche, en l'état actuel des connaissances, toutes les méthodes existantes pour casser ces codes sont exponentielles en la taille de la clé. C'est la disproportion pratique entre le temps de codage ou décodage avec clé d'une part, et de cassage d'autre part, qui rend les méthodes utiles.

Il n'y a pour l'instant pas d'objection théorique à l'existence d'algorithmes polynomiaux de cassage des codes utilisés actuellement, mais juste le constat pratique que ces problèmes résistent aux efforts soutenus de la communauté depuis suffisamment longtemps. Notons par ailleurs que les ordinateurs quantiques, si on arrive à en construire de « taille » (nombre de qbits) suffisante, permettraient de casser des systèmes comme RSA via l’algorithme de Shor.

Enfin, il est important de noter que les preuves de sécurité sont à prendre avec précaution^[11]. Par exemple, un système que l'on doit à Ajtai et Dwork, accompagné d'une preuve de sécurité théorique supposant un certain problème difficile, s'est retrouvé cassé en pratique par Phong Nguyen et Jacques Stern^[12].

• [Bellare, Micciancio et Warinschi 2003] (en) Mihir Bellare, Daniele Micciancio et Bogdan Warinschi, « Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions », Eurocrypt,‎ 2003, p. 614–629 (DOI 10.1007/3-540-39200-9_38)
• [Chatterjee, Menezes et Sarkar 2012] Sanjit Chatterjee, Alfred Menezes et Palash Sarkar, « Another Look at Tightness », Selected Area in Cryptography (SAC),‎ 2012 (DOI 10.1007/978-3-642-28496-0_18, lire en ligne)
• [Chaum et van Heyst 1991] (en) David Chaum et Eugène van Heyst, « Group Signatures », Eurocrypt,‎ 1991, p. 257–265 (DOI 10.1007/3-540-46416-6_22)
• [Degwekar, Vaikuntanathan et Vasudevan 2016] Akshay Degwekar, Vinod Vaikuntanathan et Prashant Nalini Vasudevan, « Fine-grained Cryptography », Crypto,‎ 2016 (DOI 10.1007/978-3-662-53015-3_19, lire en ligne)
• [Galbraith, Malone-Lee et Smart 2002] Steven Galbraith, James Malone-Lee et Nigel P. Smart, « Public key signatures in the multi-user setting », Information Processing Letters,‎ 2002 (DOI 10.1016/S0020-0190(01)00338-6)
• [Koblitz et Menezes 2004] (en) Neal Koblitz et Alfred Menezes, « Another Look at “Provable Security” », iacr ePrint reports,‎ 2004 (lire en ligne)
• [Lamport 1979] (en) Leslie Lamport, « Constructing digital signatures from a one-way function », Technical Report CSL-98,‎ 1979 (lire en ligne)
• [Nguyen et Stern 1998] (en) Phong Nguyen et Jacques Stern, « Cryptanalysis of the Ajtai-Dwork cryptosystem », Crypto,‎ 1998 (DOI 10.1007/BFb0055731)
• [Shannon 1949] (en) Claude Shannon, « Communication theory of secrecy systems », Bell System Technical Journal,‎ 1949 (lire en ligne)
• [Shoup 2006] (en) Victor Shoup, « Sequences of games: a tool for taming complexity in security proofs », iacr ePrint report,‎ 2006 (lire en ligne)

• Cryptanalyse
• Argument hybride

• Portail de la cryptologie
• Portail de l'informatique théorique