NP : Nondeterministic Polynomial time
Cryptographie
NP : Nondeterministic Polynomial time. « Temps polynomial non déterministe », par analogie avec la grille de sudoku : pénible à remplir, mais une solution proposée se vérifie en un coup d'œil.
Définition : NP rassemble les problèmes de décision dont une solution candidate se vérifie en temps polynomial. P, la classe des problèmes qu'on sait résoudre en temps polynomial, y est incluse ; savoir si P égale NP reste la plus célèbre question ouverte de l'informatique.
NP-complet : Un problème NP-complet est au moins aussi dur que tous ceux de NP : en résoudre un efficacement ferait tomber toute la classe. Des générations de chercheurs s'y sont essayées, ce qui constitue soit un indice de difficulté, soit la preuve d'une remarquable constance dans l'échec.
Ce que la crypto en retient : La cryptographie ne repose pas sur la NP-complétude : la factorisation et le logarithme discret ne sont pas connus pour être NP-complets. Elle a besoin de problèmes durs en moyenne, sur des instances tirées au hasard, pas seulement dans le pire cas.
Ce qui arrive si on s'en passe
Ignorer ce que NP dit, et surtout ce qu'il ne dit pas, conduit à bâtir un schéma cryptographique sur un problème NP-complet en croyant tenir une garantie : la NP-complétude ne concerne que le pire cas, et un problème difficile sur certaines instances peut se révéler facile sur celles que le schéma tire au hasard. La cryptographie a besoin de problèmes durs en moyenne. Des systèmes fondés sur le problème du sac à dos, pourtant NP-complet, ont ainsi été cassés sans que personne ait eu besoin de trancher la grande question. Une garantie qui ne porte que sur le pire cas rassure surtout ceux qui ne rencontrent jamais le cas moyen, c'est-à-dire personne.
Explication de la marmotte
Certains problèmes sont très longs à résoudre, mais très rapides à contrôler une fois qu'on a la réponse. Un sudoku en est l'exemple parfait : le remplir peut prendre une heure, vérifier une grille terminée prend une minute. Les informaticiens rangent dans une même famille tous les problèmes qui ont cette propriété de vérification rapide. La grande question, jamais tranchée, est de savoir si tout ce qui se vérifie vite peut aussi se résoudre vite. Si la réponse était oui, beaucoup de techniques de protection des secrets s'effondreraient ; personne ne l'a démontré, dans un sens comme dans l'autre.
Où ce terme est utilisé
- Les problèmes difficiles qui rendent la clé publique possible (6 occurrences)
- Lire une garantie sans la surinterpréter (1 occurrence)