Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Fonction à sens unique
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.