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.

Sommaire

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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”