Ê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
Hypothèse calculatoire
Résumé
En cryptographie, une hypothèse de difficulté calculatoire est une hypothèse qui sert à évaluer et à démontrer la robustesse des primitives cryptographiques.
Dans certains cas, la sécurité est dite inconditionnelle si elle ne repose sur aucune hypothèse de difficulté calculatoire ; un exemple courant est la technique dite du masque jetable, où le masque est aussi grand que le message. Cependant, il est souvent impossible d'atteindre une forme de sécurité aussi forte ; dans de tels cas, les cryptographes doivent s'en remettre à une forme de sécurité dite « calculatoire ». En première approximation, cela signifie que ces systèmes sont sûrs en supposant que tous les adversaires disposent d'une capacité de calcul limitée, comme tous les protagonistes en disposent en pratique.
Déterminer la difficulté de résolution d'un problème n’est pas une question facile, et le cryptosystème de Merkle-Hellman a supposé par exemple la difficulté du problème du sac à dos à poids super-croissant, qui s'est révélée vulnérable face à un algorithme glouton. L'évaluation de la difficulté des hypothèses calculatoires est étudiée par la cryptanalyse.
Il existe de nombreuses conjecture de difficulté cryptographiques. Si la difficulté de résolution du problème sous-jacent n'est pas connue pour de bon, on connaît certaines propriétés de difficultés de ces problèmes relativement à la difficulté de résolution d'autres de ces problèmes.
Lorsque l’on dit que la conjecture A est plus forte que la conjecture B, cela signifie que la résolution de B se réduit polynomialement à la résolution de A – ce qui signifie que si A est résoluble en temps polynomial, B l'est forcément aussi, mais que la réciproque n'est pas forcément vraie. Ainsi le problème A est plus difficile que le problème B, et donc si on suppose la difficulté de B, cela implique la difficulté de A.
Pour démontrer la robustesse des protocoles cryptographiques, on espère démontrer la difficulté de la plus faible de ces conjectures (car la difficulté des hypothèses plus fortes en suivrait).
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.