Système de preuve interactive
- Système de preuve interactive
-
En théorie de la complexité des algorithmes, un système de preuve interactive est une machine abstraite qui modélise un échange de messages entre deux protagonistes : un prouveur et un vérificateur ; ceux-ci communiquent afin que le prouveur convainque le vérificateur de l'appartenance ou de la non-appartenance d'une chaîne de caractères à un langage formel donné. Le prouveur a des ressources de calcul illimitées tandis que le vérificateur a des ressources limitées. Les deux protagonistes interagissent aussi longtemps qu'il est nécessaire au vérificateur pour trouver une réponse au problème et être convaincu qu'elle est la bonne.
Deux propriétés doivent être satisfaites :
- complétude : si le fournisseur de preuve et le vérificateur suivent le protocole alors le vérificateur doit toujours accepter la preuve,
- correction : si la proposition est fausse, la probabilité qu'un fournisseur de preuve malicieux puisse convaincre un vérificateur que la proposition est vraie est infime.
NP
Protocoles de Arthur-Merlin et de Merlin-Arthur
Pile ou face public ou privé
IP
MIP
PCP
Voir aussi
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Système de preuve interactive de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Systeme de preuve interactive — Système de preuve interactive En théorie de la complexité des algorithmes, un système de preuve interactive est une machine abstraite qui modélise un échange de messages entre deux protagonistes: un prouveur et un vérificateur; ceux ci… … Wikipédia en Français
Preuve a divulgation nulle de connaissance — Preuve à divulgation nulle de connaissance Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel … Wikipédia en Français
Preuve de connaissance sans apport d'information — Preuve à divulgation nulle de connaissance Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel … Wikipédia en Français
Preuve zero-knowledge — Preuve à divulgation nulle de connaissance Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel … Wikipédia en Français
Preuve à divulgation nulle de connaissance — Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel une entité nommée « fournisseur de… … Wikipédia en Français
ZKIP — Preuve à divulgation nulle de connaissance Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel … Wikipédia en Français
Zero-knowledge — Preuve à divulgation nulle de connaissance Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel … Wikipédia en Français
Zero knowledge — Preuve à divulgation nulle de connaissance Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel … Wikipédia en Français
Alice Et Bob — Les personnages Alice et Bob sont des figures classiques en cryptologie. Ces noms sont utilisés au lieu de « personne A » et « personne B » ; Alice et Bob cherchent dans la plupart des cas à communiquer de manière… … Wikipédia en Français
Alice Oscar Bob — Alice et Bob Les personnages Alice et Bob sont des figures classiques en cryptologie. Ces noms sont utilisés au lieu de « personne A » et « personne B » ; Alice et Bob cherchent dans la plupart des cas à communiquer de… … Wikipédia en Français
