Tous les systèmes de chiffrement à clé publique reposent sur la notion de fonction à sens unique. Intuitivement, une fonction à sens unique permet d'associer à un message le cryptogramme qui lui correspond. Cette opération de chiffrement doit être "facile" à calculer.

Inversement, en cryptographie, on requiert que l'inversion de cette fonction (l'opération de cryptanalyse qui à un cryptogramme associe un message qui lui corresponde) doit être "difficile".

Quand on cherche à formaliser la notion de "facile" et de "difficile", on est confronté à diverses notions de complexité des problèmes.

Nous proposons d'expliquer l'évolution des hypothèses de complexité qui permettent d'assurer la sécurité calculatoire des systèmes de chiffrement à clef publique.