Preuve de sécurité
security proof
La notion de sécurité est une notion complexe à définir. Une première définition due à Claude Shannon concerne la notion de sécurité parfaite. Si on met une probabilité sur l'ensemble des textes clairs et sur l'ensemble des clés, on peut définir la sécurité parfaite de la façon suivante : un système est à sécurité parfaite si la probabilité d'un texte clair connaissant son chiffré avec la clé de chiffrement (probabilité conditionnelle) est la même que celle du texte clair. Autrement dit, la connaissance du chiffré n'apporte aucune information sur le texte clair. Hélas, cette notion est bien trop forte pour pouvoir être réalisée dans des systèmes concrets facilement utilisables par des applications ouvertes à un large public. Dans le cas de la sécurité parfaite, la puissance de l'adversaire importe peu puisque on ne lui apporte strictement aucune information supplémentaire par la donnée du chiffré. En réalité on est amené pour une utilisation réaliste à remplacer « aucune information » par « aucune information en pratique ». C'est-à-dire que la connaissance du chiffré apporte bien une information à l'adversaire, mais que cette information ne lui permet pas de faire un calcul réalisable en pratique qui lui donnerait une information concrète sur le texte clair. On remplace donc la notion de sécurité parfaite par la notion de sécurité calculatoire. Avec cette nouvelle vision des choses, la puissance de l'adversaire importe. On va donc définir des notions de sécurité qui vont être relatives à deux notions : d'une part le type de sécurité qu'on veut assurer (que veut on imposer d'infaisable en pratique à l'adversaire), d'autre part la puissance de l'adversaire. En croisant ces deux notions on voit qu'on va pouvoir définir plusieurs notions de sécurité. Ceci se complique encore par le fait que la sécurité va s'adresser à des systèmes cryptographiques qui assurent des fonctionnalités différentes : chiffrement à clé secrète, chiffrement à clé publique, signature, authentification, voire des protocoles complexes. En outre par le fait qu'il s'agit de sécurité calculatoire, la taille des systèmes est primordiale. Telle chose qu'on ne sait pas en pratique réaliser sur 1024 bits est très facile sur 150 bits! Et la taille peut donner lieu à diverses formulations des notions de sécurité : une formulation asymptotique, une formulation avec des bornes concrètes. Une fois que le problème est bien défini (à savoir qu'on a dit quelle notion de sécurité on voulait prouver, et sous quelle forme) il convient de faire une preuve de sécurité. Il n'existe à l'heure actuelle aucune preuve absolue de sécurité. Les preuves sont du type : si le système dont je veux prouver la sécurité n'était pas sûr (au sens voulu) contre une attaque (c'est-à-dire un algorithme) d'un adversaire (ayant la puissance imposée) alors je pourrais construire un algorithme faisable en pratique qui résoudrait un problème dont tout le monde admet qu'il est inextricable (pour les tailles concernées). Ce sont des preuves dites par réduction (on réduit un algorithme à un autre). On montrera par exemple que si tel système est cassé par une attaque réalisable en pratique alors cela donne un moyen de factoriser un entier de grande taille. Notons une notion importante dans ces preuves par réduction, c'est le coût de la réduction : la réduction consiste à montrer que si on sait casser un système (dont on veut prouver la sécurité) de taille t, alors on sait résoudre un problème réputé inextricable de taille f(t); le passage de la taille t à la taille f(t) conditionne bien entendu les tailles pour lesquelles la sécurité est prouvée. Ce passage de t à f(t) constitue le coût de la réduction. On essaie évidemment d'avoir un coût le plus petit possible.
Enfin il est à noter que de nombreuses preuves sont faites en admettant que les protagonistes ont le droit de faire appel à une suite aléatoire (parfaite). Ont dit que ces preuves sont faites dans le modèle de l'oracle aléatoire. Dans le cas contraire elles sont faites dans le modèle standard.