Fonction à sens unique

vignette|Panneau de signalisation routière de sens unique Une fonction à sens unique (ou one-way function en anglais) est une fonction qui peut être aisément calculée, mais qui est difficile à inverser — c'est-à-dire qu'étant donnée une , il est difficile de lui trouver un antécédent. Les fonctions à sens unique sont utilisées en cryptographie asymétrique et dans les fonctions de hachage cryptographiques. La théorie de la complexité des algorithmes est un élément central de la notion de fonction à sens unique. En effet, cette théorie donne un sens mathématique à la notion floue de difficulté à trouver un antécédent, et son existence implique l'inégalité entre les classes P et NP. Une fonction calculable en temps polynomial est dite à sens unique si pour tout algorithme polynomial probabiliste , il existe une fonction négligeable telle que pour tout on ait L’existence de fonctions à sens unique a de nombreuses implications en cryptographie, en particulier elles permettent de construire : des générateurs et fonctions pseudo-aléatoires, des schémas de signature numérique, des schémas de mise en gage... Comme l’existence des fonctions à sens unique implique la distinction entre les classes P et NP qui reste une option ouverte à laquelle la majorité des scientifiques adhèrent, on considère généralement que les solutions proposées sont tout à fait crédibles. Un exemple classique de fonction à sens unique est le problème du sac à dos : soit un ensemble de nombres et un sous-ensemble de , il est très facile de calculer la somme des éléments de . En revanche, et étant fixés, il est très difficile de trouver sous ensemble de tel que la somme des éléments de soit égale à . La théorie de la complexité montre d'ailleurs que le problème du sac à dos est NP-complet, c'est-à-dire qu'il existe des instances supposées très difficiles du point de vue du temps de calcul. Ce problème fut d'ailleurs à la base d'un des premiers algorithmes de cryptographie asymétrique, l'algorithme de Merkle-Hellman.