Preuve de sécurité

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, concept qui a été défini pour la première fois par Chaum et van Heyst en 1991. 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, 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.