L'équivalence de deux définitions d'exhaustivité et de solidité dans les systèmes de preuve interactifs

11

L'exhaustivité et la solidité des systèmes de preuve interactifs sont définies de manière informelle comme:

  • Exhaustivité: Si une déclaration est vrai, l' honnête prouveur peut convaincre l' honnête vérificateur de ce fait PVT .

  • Solidité: si une déclaration est fausse, le prouveur de fraude ne peut pas convaincre le vérificateur honnête (de la validité de la fausse déclaration) whp

Le terme «whp» est interprété comme «avec une probabilité supérieure à (disons) 2/3» ou «avec une probabilité supérieure à l'inverse de tout polynôme». Il ne semble pas pertinent pour la discussion suivante de savoir quelle interprétation de "whp" choisir.

La partie la plus délicate est la façon dont la probabilité est calculée: Dans certaines sources, la probabilité est prise en charge des pièces au hasard des deux prouveur et le vérificateur. Dans d'autres sources, la probabilité n'est calculée que sur les pièces aléatoires du vérificateur. Ce dernier est généralement justifié comme suit: "quelles que soient les pièces aléatoires du prouveur, le vérificateur prend la bonne décision."

Pour moi, les deux définitions de la probabilité semblent équivalentes; pourtant je ne peux pas le prouver. Ai-je raison? Pouvez-vous prouver leur équivalence?

cc.complexity-theory interactive-proofs Incroyable
la source
2
vous devez également considérer si vous faites référence à des pièces "publiques" ou "privées". Dans le cadre des pièces publiques, le prouveur et le vérificateur connaissent les résultats des choix aléatoires, et pour les pièces privées, le prouveur ne connaît pas les choix aléatoires du vérificateur. Dans ce dernier cas, vous ne vous souciez que de ce que le vérificateur fait sans regarder le prouveur parce que le prouveur ne connaît tout simplement pas les lancers aléatoires.
Marcos Villagra
@Marcos: Jetez un œil à la définition originale des preuves interactives, qui est de nature "privée". La dernière phrase de la première colonne de la page 293, qui est soulignée, déclare que "les probabilités ne sont prises que sur les lancers de pièces de B". (Ici, B est le vérificateur.) D'un autre côté, la version journal de l'article susmentionné permet de prendre les probabilités sur les lancers de pièces des deux parties. Cela pourrait être la source de confusion, non?
MS Dousti
@Sadeq: Je vois, je ne connaissais pas cette différence entre le journal et les versions de la conférence. Pourtant, pour les pièces privées, je ne vois pas l'intérêt de prendre en compte les lancers de pièces du prouveur, car il pourrait décider de ne pas en parler au vérificateur. Le vérificateur est celui chargé de décider de l'acceptation ou du rejet, et il peut ne pas savoir ce que fait le prouveur.
Marcos Villagra
1
@Marcos: Vous avez raison, mais le même raisonnement vaut pour les épreuves de pièces publiques; car dans ces systèmes, les lancers de pièces du prouveur sont toujours privés (seules les pièces du vérificateur sont publiques). En général, on peut considérer un prouveur déterministe: le prouveur étant tout-puissant, il n'a pas besoin de hasard et peut choisir la réponse optimale de façon déterministe. Pourtant, ce type de raisonnement ne fonctionne pas si nous considérons les systèmes à connaissance zéro, dans lesquels la stratégie du prouveur devrait être probabiliste (sinon, ses connaissances fuiraient).
MS Dousti
2
(Suite) Si le prouveur est randomisé, alors je pense que la bonne formulation est de calculer la probabilité sur les deux lancers de pièces du prouveur et du vérificateur: alors que, comme l'a dit Marcos, le vérificateur est en charge de la décision finale, sa décision est fait (entre autres) sur la base des messages provenant du prouveur. Étant donné que le prouveur est aléatoire, ses lancers de pièces affectent certainement les messages qu'il envoie. Par conséquent, les lancers de pièces du prouveur affectent la probabilité d'acceptation. Ai-je raison?
MS Dousti

Réponses:

6

Le prouveur est «tout-puissant et possède des ressources de calcul illimitées», il n'a donc pas besoin de bits aléatoires. Ainsi, le seul caractère aléatoire est le caractère aléatoire du vérificateur.

Si le prouveur utilise des bits aléatoires, il doit les remplacer par la chaîne de bits aléatoires qui est la plus susceptible de faire accepter le vérificateur (cela est vrai pour le prouveur honnête et pour tout prouveur malhonnête). De plus, le prouveur peut déterminer cette chaîne de bits optimale car le prouveur est "tout-puissant".

Tyson Williams
la source
1
Comme je l'ai dit dans un commentaire ci-dessus, cela n'est vrai que si l'on considère les preuves interactives seules. Cependant, les choses sont très différentes si vous tenez compte d'autres propriétés, telles que la "connaissance zéro" qui est naturellement liée aux preuves interactives.
MS Dousti
1
Suite: Oren a prouvé ce qui suit: "... selon la définition d'entrée auxiliaire de la connaissance zéro, le caractère aléatoire du prouveur est essentiel à la non-banalité des systèmes à l'épreuve de la connaissance zéro. En d'autres termes, toute langue qui possède un système de preuve de connaissance zéro à entrée auxiliaire dans lequel le prouveur est déterministe pour BPP. " (Voir la section 4.5 d' Oren pour plus d'informations.) Par conséquent, vous ne pouvez pas toujours supposer que P est déterministe.
MS Dousti