Système de preuve interactif

En théorie de la complexité computationnelle , un système de preuve interactif est une machine abstraite qui modélise le calcul comme un échange de messages entre deux parties : un démonstrateur et un vérificateur . Les parties interagissent en échangeant des messages afin de déterminer si une chaîne donnée appartient ou non à un langage . Le démonstrateur possède des ressources de calcul illimitées mais ne peut pas être fiable, tandis que le vérificateur a une puissance de calcul limitée mais est supposé toujours honnête. Des messages sont envoyés entre le vérificateur et le démonstrateur jusqu'à ce que le vérificateur ait une réponse au problème et se soit « convaincu » qu'elle est correcte.

Tous les systèmes de preuve interactifs ont deux exigences :

• Exhaustivité : si l’énoncé est vrai, le démonstrateur honnête (c’est-à-dire celui qui suit correctement le protocole) peut convaincre le vérificateur honnête qu’il est effectivement vrai.
• Solidité : si l'affirmation est fausse, aucun démonstrateur, même s'il ne suit pas le protocole, ne peut convaincre le vérificateur honnête qu'elle est vraie, sauf avec une faible probabilité .

La nature spécifique du système, et donc la classe de complexité des langages qu'il peut reconnaître, dépend du type de limites imposées au vérificateur, ainsi que des capacités qui lui sont attribuées. Par exemple, la plupart des systèmes de preuve interactifs dépendent essentiellement de la capacité du vérificateur à faire des choix aléatoires. Cela dépend également de la nature des messages échangés, c'est-à-dire de leur nombre et de leur contenu. Il a été constaté que les systèmes de preuve interactifs ont des implications importantes pour les classes de complexité traditionnelles définies à l'aide d'une seule machine. Les principales classes de complexité décrivant les systèmes de preuve interactifs sont AM et IP .

Chaque système de preuve interactif définit un langage formel de chaînes de caractères . La solidité du système de preuve fait référence à la propriété selon laquelle aucun démonstrateur ne peut faire accepter au vérificateur une déclaration erronée, sauf avec une faible probabilité. La limite supérieure de cette probabilité est appelée l' erreur de solidité d'un système de preuve. Plus formellement, pour chaque démonstrateur et chaque :

pour certains . Tant que l'erreur de solidité est limitée par une fraction polynomiale du temps d'exécution potentiel du vérificateur (c'est-à-dire ), il est toujours possible d'amplifier la solidité jusqu'à ce que l'erreur de solidité devienne une fonction négligeable par rapport au temps d'exécution du vérificateur. Ceci est réalisé en répétant la preuve et en acceptant seulement si toutes les preuves sont vérifiées. Après répétitions, une erreur de solidité sera réduite à .

La classe de complexité NP peut être considérée comme un système de preuve très simple. Dans ce système, le vérificateur est une machine à temps polynomial déterministe (une machine P ). Le protocole est le suivant :

• Le démonstrateur examine l’entrée et calcule la solution en utilisant sa puissance illimitée et renvoie un certificat de preuve de taille polynomiale.
• Le vérificateur vérifie que le certificat est valide en temps polynomial déterministe. S'il est valide, il l'accepte ; sinon, il le rejette.

Dans le cas où il existe un certificat de preuve valide, le prouveur est toujours en mesure de faire accepter le vérificateur en lui fournissant ce certificat. En revanche, dans le cas où il n'existe pas de certificat de preuve valide, l'entrée n'est pas dans la langue, et aucun prouveur, aussi malveillant soit-il, ne peut convaincre le vérificateur du contraire, car tout certificat de preuve sera rejeté.

Bien que la théorie des probabilités puisse être considérée comme utilisant l'interaction, ce n'est qu'en 1985 que le concept de calcul par interaction a été conçu (dans le contexte de la théorie de la complexité) par deux groupes de chercheurs indépendants. Une approche, celle de László Babai , qui a publié « Trading group theory for randomness », a défini la hiérarchie de classes Arthur-Merlin ( AM ). Dans cette présentation, Arthur (le vérificateur) est une machine à temps polynomial probabiliste , tandis que Merlin (le démonstrateur) dispose de ressources illimitées.

La classe MA en particulier est une simple généralisation de l'interaction NP ci-dessus dans laquelle le vérificateur est probabiliste au lieu d'être déterministe. De plus, au lieu d'exiger que le vérificateur accepte toujours les certificats valides et rejette les certificats non valides, il est plus indulgent :

• Exhaustivité : si la chaîne est dans la langue, le prouveur doit pouvoir donner un certificat tel que le vérificateur l'acceptera avec une probabilité d'au moins 2/3 (selon les choix aléatoires du vérificateur).
• Solidité : si la chaîne n'est pas dans le langage, aucun démonstrateur, aussi malveillant soit-il, ne pourra convaincre le vérificateur d'accepter la chaîne avec une probabilité supérieure à 1/3.

Cette machine est potentiellement plus puissante qu'un protocole d'interaction NP ordinaire , et les certificats ne sont pas moins pratiques à vérifier, puisque les algorithmes BPP sont considérés comme faisant abstraction du calcul pratique (voir BPP ).

Dans un protocole de monnaie publique , les choix aléatoires effectués par le vérificateur sont rendus publics. Ils restent privés dans un protocole de monnaie privée.

Dans la même conférence où Babai a défini son système de preuve pour MA , Shafi Goldwasser , Silvio Micali et Charles Rackoff ont publié un article définissant le système de preuve interactif IP [ f ( n )]. Celui-ci possède les mêmes machines que le protocole MA , sauf que f ( n ) tours sont autorisés pour une entrée de taille n . À chaque tour, le vérificateur effectue un calcul et transmet un message au démonstrateur, et le démonstrateur effectue un calcul et renvoie des informations au vérificateur. À la fin, le vérificateur doit prendre sa décision. Par exemple, dans un protocole IP [3], la séquence serait VPVPVPV, où V est le tour du vérificateur et P est le tour du démonstrateur.

Dans les protocoles Arthur-Merlin, Babai a défini une classe similaire AM [ f ( n )] qui autorisait f ( n ) tours, mais il a posé une condition supplémentaire à la machine : le vérificateur doit montrer au démonstrateur tous les bits aléatoires qu'il utilise dans son calcul. Le résultat est que le vérificateur ne peut rien « cacher » au démonstrateur, car ce dernier est suffisamment puissant pour simuler tout ce que fait le vérificateur s'il sait quels bits aléatoires il a utilisés. On parle alors de protocole de pièce publique , car les bits aléatoires (« lancers de pièce ») sont visibles par les deux machines. L' approche IP est quant à elle appelée protocole de pièce privée .

Le problème essentiel des monnaies publiques est que si le démonstrateur souhaite convaincre de manière malveillante le vérificateur d'accepter une chaîne qui n'est pas dans le langage, il semble que le vérificateur puisse contrecarrer ses plans s'il peut lui cacher son état interne. C'était l'une des principales motivations lors de la définition des systèmes de preuve IP .

En 1986, Goldwasser et Sipser ont montré, de manière peut-être surprenante, que la capacité du vérificateur à cacher les lancers de pièces au prouveur ne lui sert pas à grand-chose, dans la mesure où un protocole de pièce publique Arthur-Merlin avec seulement deux tours supplémentaires peut reconnaître tous les mêmes langages. Le résultat est que les protocoles de pièce publique et de pièce privée sont à peu près équivalents. En fait, comme le montre Babai en 1988, AM [ k ] = AM pour toute constante k , donc les IP [ k ] n'ont aucun avantage sur AM .

Pour démontrer la puissance de ces classes, considérons le problème d'isomorphisme de graphes , le problème de déterminer s'il est possible de permuter les sommets d'un graphe de sorte qu'il soit identique à un autre graphe. Ce problème est en NP , puisque le certificat de preuve est la permutation qui rend les graphes égaux. Il s'avère que le problème du complément d'isomorphisme de graphes, un problème co- NP dont on ne sait pas qu'il est en NP , a un algorithme AM et la meilleure façon de le voir est via un algorithme de pièces privées.

Les pièces privées ne sont peut-être pas utiles, mais davantage de cycles d'interaction sont utiles. Si nous permettons à la machine vérificatrice probabiliste et au démonstrateur tout-puissant d'interagir pendant un nombre polynomial de cycles, nous obtenons la classe de problèmes appelée IP . En 1992, Adi Shamir a révélé dans l'un des résultats centraux de la théorie de la complexité que IP est égal à PSPACE , la classe de problèmes résolubles par une machine de Turing déterministe ordinaire dans l'espace polynomial.

Si nous permettons aux éléments du système d'utiliser le calcul quantique , le système est appelé système de preuve interactif quantique et la classe de complexité correspondante est appelée QIP . Une série de résultats a abouti à une percée en 2010 selon laquelle QIP = PSPACE .

Non seulement les systèmes de preuve interactifs peuvent résoudre des problèmes qui ne sont pas considérés comme appartenant à NP , mais sous l'hypothèse de l'existence de fonctions à sens unique , un démonstrateur peut convaincre le vérificateur de la solution sans jamais lui donner d'informations sur la solution. Ceci est important lorsque le vérificateur ne peut pas être fiable avec la solution complète. Au premier abord, il semble impossible que le vérificateur puisse être convaincu qu'il existe une solution alors qu'il n'a pas vu de certificat, mais de telles preuves, connues sous le nom de preuves à connaissance nulle, sont en fait censées exister pour tous les problèmes de NP et sont précieuses en cryptographie . Les preuves à connaissance nulle ont été mentionnées pour la première fois dans l'article original de 1985 sur IP par Goldwasser, Micali et Rackoff pour des langages de théorie des nombres spécifiques. L'étendue de leur puissance a cependant été montrée par Oded Goldreich , Silvio Micali et Avi Wigderson . pour l'ensemble de NP , et cela a été étendu pour la première fois par Russell Impagliazzo et Moti Yung à tous les IP .

L'un des objectifs des concepteurs d'IP était de créer le système de preuve interactif le plus puissant possible, et à première vue, il semble impossible de le rendre plus puissant sans rendre le vérificateur plus puissant et donc peu pratique. Goldwasser et al. ont surmonté cela dans leur ouvrage de 1988 « Multi prover interactive proofs: How to remove intractability hypothesiss », qui définit une variante d' IP appelée MIP dans laquelle il y a deux prouveurs indépendants. Les deux prouveurs ne peuvent pas communiquer une fois que le vérificateur a commencé à leur envoyer des messages. Tout comme il est plus facile de savoir si un criminel ment si lui et son partenaire sont interrogés dans des pièces séparées, il est considérablement plus facile de détecter un prouveur malveillant essayant de tromper le vérificateur en lui faisant accepter une chaîne qui n'est pas dans la langue s'il existe un autre prouveur avec lequel il peut effectuer une double vérification.

En fait, cela est si utile que Babai, Fortnow et Lund ont pu montrer que MIP = NEXPTIME , la classe de tous les problèmes résolubles par une machine non déterministe en temps exponentiel , une classe très grande. NEXPTIME contient PSPACE, et on pense qu'il contient strictement PSPACE. L'ajout d'un nombre constant de démonstrateurs supplémentaires au-delà de deux ne permet pas la reconnaissance d'autres langages. Ce résultat a ouvert la voie au célèbre théorème PCP , qui peut être considéré comme une version « réduite » de ce théorème.

MIP a également la propriété utile que les preuves à connaissance nulle pour chaque langage dans NP peuvent être décrites sans l'hypothèse de fonctions à sens unique que IP doit créer. Cela a une incidence sur la conception d'algorithmes cryptographiques prouvables incassables. De plus, un protocole MIP peut reconnaître tous les langages dans IP en seulement un nombre constant de tours, et si un troisième prouveur est ajouté, il peut reconnaître tous les langages dans NEXPTIME en un nombre constant de tours, montrant à nouveau sa puissance sur IP .

Il est connu que pour toute constante k , un système MIP avec k démonstrateurs et un nombre polynomial de tours peut être transformé en un système équivalent avec seulement 2 démonstrateurs et un nombre constant de tours.

Tandis que les concepteurs d' IP envisageaient des généralisations des systèmes de preuve interactifs de Babai, d'autres envisageaient des restrictions. Un système de preuve interactif très utile est PCP ( f ( n ), g ( n )), qui est une restriction de MA où Arthur ne peut utiliser que f ( n ) bits aléatoires et ne peut examiner que g ( n ) bits du certificat de preuve envoyé par Merlin (essentiellement en utilisant un accès aléatoire ).

Il existe un certain nombre de résultats faciles à prouver sur diverses classes PCP . ⁠ ⁠ , la classe des machines à temps polynomial sans caractère aléatoire mais ayant accès à un certificat, est simplement NP . ⁠ ⁠ , la classe des machines à temps polynomial avec accès à un nombre polynomial de bits aléatoires est co- RP . Le premier résultat majeur d'Arora et Safra était que ⁠ ⁠ ; en d'autres termes, si le vérificateur du protocole NP est contraint de choisir uniquement ⁠ ⁠ bits du certificat de preuve à examiner, cela ne fera aucune différence tant qu'il aura ⁠ ⁠ bits aléatoires à utiliser.

De plus, le théorème PCP affirme que le nombre d'accès à la preuve peut être ramené à une constante. C'est-à-dire ⁠ ⁠ . Ils ont utilisé cette précieuse caractérisation de NP pour prouver que les algorithmes d'approximation n'existent pas pour les versions d'optimisation de certains problèmes NP-complets à moins que P = NP . De tels problèmes sont maintenant étudiés dans le domaine connu sous le nom de dureté de l'approximation .