Protocole de preuve sans connaissance. Preuve de connaissance nulle. D'accord, alors qu'est-ce que tout cela signifie ?

Supposons qu'Alice connaisse la preuve d'un certain théorème et veuille convaincre Bob que ce théorème est vrai. Bien sûr, Alice peut simplement transmettre la preuve à Bob pour vérification. Mais Bob pourra ensuite prouver lui-même ce théorème à des tiers, sans l’aide d’Alice. Alice pourra-t-elle convaincre Bob sans qu'il reçoive aucune information qui l'aiderait à reconstituer la preuve du théorème ? Ces deux exigences apparemment mutuellement exclusives sont satisfaites par des protocoles de preuve avec zéro connaissance. Ce dernier concept a été introduit par Goldwasser, Micali et Rakoff en 1985.

Le modèle de protocole suivant est considéré. Alice et Bob disposent respectivement de machines probabilistes de Turing. Les ressources de calcul qu'Alice peut utiliser sont illimitées, tandis que la machine V fonctionne en temps polynomial. Les machines disposent d'un flux de communication commun pour échanger des messages. Après avoir enregistré un message sur la bande de communication, la machine entre dans un état de veille et en sort dès qu'un message de réponse est enregistré sur la bande. Les machines disposent également d'une bande d'entrée commune sur laquelle est écrit le mot d'entrée x. La déclaration qu'Alice prouve est qu'il existe un langage fixe (connu à la fois par Alice et Bob). Pour éviter toute trivialité, le langage doit être dur (par exemple, NP-complet), sinon Bob sera capable de le vérifier de manière indépendante. Essentiellement, le protocole de preuve est que Bob, en utilisant le hasard, sélectionne certaines questions, les pose à Alice et. vérifie l'exactitude des réponses. Le protocole se termine lorsque la machine V s'arrête, et il renvoie 1 si la preuve est acceptée et 0 sinon.

Supposons qu'il y ait deux machines de Turing interactives, c'est-à-dire interagissant via une bande de communication commune, probabilistes. Through désigne une variable aléatoire - le mot de sortie de la machine A, lorsque A et B travaillent sur le mot d'entrée x. La longueur du mot x est notée.

Définition 4. Une preuve interactive pour un langage est une paire de machines de Turing interactives telles que les deux conditions suivantes sont satisfaites.

1. (Exhaustivité). Pour tout le monde

2. (Exactité). Pour toute machine de Turing pour tout polynôme et pour tout de longueur suffisamment grande

L'exhaustivité signifie que si le mot saisi appartient à la langue et qu'Alice et Bob suivent tous deux le protocole, alors la preuve sera toujours acceptée. L'exigence d'exactitude protège Bob de la malhonnête Alice, qui tente de le tromper en « prouvant » une fausse déclaration. Dans ce cas, Alice peut s'écarter de quelque manière que ce soit des actions prescrites par le protocole, c'est-à-dire utiliser n'importe quelle autre machine au lieu de la machine de Turing. Il est nécessaire que la probabilité de tromperie soit dans tous les cas négligeable.

Définition 5. Un protocole de preuve interactive pour un langage est appelé une preuve à connaissance absolument nulle si, en plus des conditions 1 et 2, la condition suivante est également satisfaite.

3. (Propriété Zéro Connaissance). Pour toute machine de Turing probabiliste polynomiale V, il existe une machine de Turing probabiliste fonctionnant en temps polynomial en moyenne, et telle que pour tout

La machine est appelée machine de simulation car on suppose que l'espérance mathématique de son temps de fonctionnement est limitée par un polynôme de longueur x. Cela signifie qu'en principe, en fonction des valeurs que prennent les variables aléatoires utilisées dans son travail, il peut fonctionner assez longtemps. Mais la probabilité que sa durée de fonctionnement dépasse une certaine limite polynomiale est faible. Pour chaque machine V, sa propre machine à modéliser est construite ; ce dernier peut utiliser V comme sous-programme. Through désigne une variable aléatoire - le mot de sortie de la machine lorsqu'elle reçoit le mot x en entrée.

La propriété de connaissance nulle protège Alice d'un Bob malhonnête qui, en s'écartant arbitrairement des actions prescrites par le protocole (en utilisant V au lieu de V), tente de profiter de son exécution. Informations Complémentaires. La condition 3 signifie que Bob ne peut obtenir que des informations qu'il pourrait calculer indépendamment en exécutant le protocole) en temps polynomial.

Prenons un exemple de protocole de preuve de connaissance absolument nulle pour un langage tiré des travaux de Goldreich, Micali et Wigderson. Le mot d'entrée est une paire de graphiques et Voici un ensemble de sommets, qui peuvent être identifiés avec l'ensemble des nombres naturels, un ensemble d'arêtes telles que les graphiques sont appelés isomorphes s'il y a une permutation sur l'ensemble telle que si et seulement if (indiqué par le problème de reconnaissance de l'isomorphisme des graphes est une tâche mathématique bien connue pour laquelle à l'heure actuelle aucun algorithme polynomial n'est connu. D’un autre côté, on ne sait pas si ce problème est NP-complet, même s’il y a de bonnes raisons de supposer qu’il ne l’est pas.

Protocole IG

Supposons que l'isomorphisme entre les quatre étapes suivantes soit effectué une fois en boucle, à chaque fois avec des variables aléatoires indépendantes.

1. P sélectionne une permutation aléatoire sur l'ensemble, calcule et envoie ce graphique

2. V sélectionne un bit aléatoire et l'envoie

3. Si alors envoie V permutation, sinon - permutation o

4. Si la permutation obtenue par V n'est pas un isomorphisme entre alors V arrête et rejette la preuve. Sinon, l'exécution du protocole continue.

Si les contrôles de l'étape 4 ont donné résultat positif dans tous les cycles, alors V accepte la preuve.

Notez que si dans le protocole IG la machine reçoit un isomorphisme comme mot d'entrée supplémentaire, alors elle n'a pas besoin de ressources informatiques illimitées pour exécuter le protocole. De plus, dans ce cas, il peut y avoir une machine de Turing probabiliste polynomiale.

Théorème 2 (). Le protocole IG est une preuve absolument nulle pour le langage GRAPH ISOMORPHISM.

L'exhaustivité du protocole IG est évidente.

Pour prouver l'exactitude, il suffit de noter que le bit a, que V sélectionne à l'étape 2, indique pour lequel des graphiques - ou il faut démontrer l'isomorphisme avec le graphique. S'il n'est pas isomorphe, alors il peut être isomorphe, en. meilleur scénario, l'un d'eux. Par conséquent, vérifier l’étape 4 donnera un résultat positif avec une probabilité de 1/2 dans un cycle et avec une probabilité dans tous les cycles.

Prouver la propriété de connaissance nulle est beaucoup plus difficile. Nous reproduisons donc uniquement l’idée principale. Tout d’abord, notons que la tâche principale de la machine V est d’obtenir le maximum informations possiblesà propos de l'isomorphisme entre Il est naturel de supposer que, contrairement à V, il produira comme mot de sortie non pas un bit, mais toutes les informations obtenues à la suite de l'exécution du protocole, y compris le contenu de sa bande aléatoire, les graphiques et les permutations obtenues dans étapes 1 et 3, respectivement protocole IG. La machine à modéliser doit être capable de construire la même chose chaînes aléatoires, graphiques et permutations, sans connaître l'isomorphisme. Il essaie donc de deviner le bit a qui sera la requête de la machine V à l'étape 2. Pour ce faire, sélectionnez un bit aléatoire, une permutation aléatoire, et calculez ensuite. il se souvient de l'état de la machine V (y compris le contenu de la bande aléatoire) et l'appelle comme sous-programme, le graphique l'a alimenté en entrée. La réponse de la machine V sera un peu a. Si alors la modélisation dans ce cycle terminé avec succès car il peut démontrer l’isomorphisme requis. If puis restaure l'état précédemment enregistré de la machine V et réessaye.

Si dans la définition de la propriété de connaissance nulle on remplace l'égalité variables aléatoires en exigeant que leurs distributions de probabilité soient « presque les mêmes », nous obtenons alors un autre type de preuve : une preuve avec une connaissance statistique nulle.

Un autre type est celui des preuves informatiques sans connaissance. Dans ce cas, le simulateur doit produire une distribution de probabilité qui ne se distingue pas de tout algorithme de probabilité polynomiale (l'indiscernabilité est définie ici de la même manière que dans la définition d'un générateur pseudo-aléatoire).

Soulignons particulièrement que dans les trois définitions de la connaissance zéro, les conditions ne sont imposées aux actions de la machine à modeler que sur les mots qui appartiennent au langage.

Outre l’intérêt des preuves à connaissance nulle en tant qu’objet mathématique non trivial, elles sont également étudiées en lien avec des applications pratiques. Le type d'application le plus naturel et le plus important est celui des protocoles d'authentification (voir chapitre 3). Avec l'aide d'un tel protocole, Alice peut prouver son authenticité à Bob.

Supposons, par exemple, qu'Alice soit une personne intelligente carte bancaire, dans lequel l'algorithme est implémenté et Bob est l'ordinateur de la banque qui exécute le programme. Avant de commencer toute opération bancaire, la banque doit vérifier l'authenticité de la carte et identifier son propriétaire ou, en langage cryptographique, la carte doit être authentifiée. En principe, le protocole IG ci-dessus peut être utilisé à cette fin. Dans ce cas, en mémoire ordinateur bancaire une paire de graphiques associés à Alice est stockée, et carte à puce- la même paire de graphiques et d'isomorphisme On suppose qu'à l'exception d'Alice, personne ne connaît cet isomorphisme (sauf peut-être Bob) et donc, en utilisant le protocole IG, la carte prouve son authenticité. De plus, la propriété d'exhaustivité signifie que la carte prouvera certainement son authenticité. La propriété d'exactitude protège les intérêts de la banque contre un attaquant qui, n'étant pas client de la banque, tente de s'authentifier à l'aide d'une fausse carte. La propriété de connaissance nulle protège le client d'un attaquant qui, après avoir entendu une ou plusieurs exécutions du protocole d'authentification de la carte, tente de s'authentifier sous le nom d'Alice. Bien entendu, dans dans ce cas il est inutile de prouver qu'un couple de graphes appartient au langage GRAP ISOMORPHISM, puisqu'il est évidemment sélectionné dans ce langage. Au lieu de cela, Alice prouve qu'elle connaît l'isomorphisme. Les preuves interactives de ce type sont appelées preuves de connaissance.

Pour application pratique Très propriété importante Le protocole IG, comme les autres protocoles de preuve de connaissance, est que l'algorithme reçu comme entrée supplémentaire l'isomorphisme s'exécute en temps polynomial. Au lieu du protocole IG, vous pouvez généralement utiliser toute autre preuve à connaissance nulle dans laquelle l'algorithme possède cette propriété. Mais pour les applications réelles, le protocole IG, comme la plupart des protocoles similaires, n'est pas efficace : grand nombre boucles, messages trop longs, etc. La recherche de protocoles plus efficaces et dont la sécurité est prouvée est l'un des principaux axes de recherche dans ce domaine.

Soit un système de preuve interactif (P, V, S).
Dans la définition d'un système de preuve interactif, on ne supposait pas auparavant que V pouvait être un adversaire (seule la possibilité de l'existence d'un participant malhonnête P était supposée). Mais V peut s'avérer être un adversaire qui veut le découvrir). quelques nouvelles informations de P. informations utilesà propos de l'énoncé de S. Dans ce cas, P peut ne pas vouloir que cela se produise à la suite du travail
Protocole du système de preuves interactives. Donc
28 Zapechnikov S. V. Protocoles cryptographiques et leurs prédécesseurs
Nous arrivons ainsi à l’idée d’un protocole de preuve à connaissance nulle. La connaissance nulle implique que, grâce au protocole du système de preuve interactif, V n'augmentera pas sa connaissance de l'énoncé S ou, en d'autres termes, ne sera pas en mesure d'extraire aucune information sur la raison pour laquelle S est vrai.
Comme auparavant, le protocole formule au préalable une certaine déclaration S, par exemple, selon laquelle un objet w a la propriété L : we L. Pendant le protocole, P et V échangent des messages. Chacun d'eux peut générer nombres aléatoires et utilisez-les dans vos calculs. À la fin du protocole, V doit prendre sa décision finale quant à savoir si S est vrai ou faux.
Le but de P est toujours de convaincre V que S est vrai, que ce soit vrai ou non, c'est-à-dire que P peut être un adversaire actif, et le travail de V est de tester les arguments de P. Le but du participant V est de juger si S. est vrai ou faux. Comme auparavant, V a des capacités de calcul polynomialement limitées, à savoir que son temps de fonctionnement est limité par un polynôme dans
longueur de l'énoncé à prouver : Considérons maintenant des exemples de protocoles de preuve avec connaissance nulle.
1. « Le problème de la caverne d’Ali Baba. » Il y a une grotte dont le plan est montré sur la Fig. 1.2. La grotte a une porte secrète entre les points C et D. Quiconque connaît mots magiques, peut ouvrir cette porte et passer de C à D ou vice versa. Pour tous les autres, les deux passages de la grotte mènent à une impasse.
Faites connaître à R le secret de la grotte. Il veut prouver à V sa connaissance de ce secret sans divulguer les mots magiques. Voici le protocole de leur communication :
V est au point A ;
P entre dans la grotte et arrive soit au point C, soit au point D\
Après que P ait disparu dans la grotte, V arrive au point B, sans savoir dans quelle direction P est allé.
V appelle R et lui demande de sortir par le couloir gauche ou droit de la grotte selon les souhaits de V ;
R le fait, ouvrant la porte si nécessaire, si, bien sûr, il connaît les mots magiques ;
P et V répètent les étapes (1) à (5) n fois.

Après n tours du protocole, la probabilité sera réduite à 1/2".
2. Preuve de l'isomorphisme des graphes. P veut prouver l'isomorphisme V des graphes Go et Gb Soit G, = (p(G0):G0 = G, où φ est la transformation de l'isomorphisme ; m est la cardinalité de l'ensemble N des sommets des graphes. Le tableau 1.4 montre le protocole pour prouver cette déclaration en attente.
Expliquons la structure de ce protocole. A l'étape (1), le participant P crée un graphe aléatoire H, isomorphe à G\. A l'étape (2), le participant V, choisissant un bit aléatoire a = (0D), demande ainsi de prouver que
Н ~G0 ou que Н « Gj. A l'étape (3), le participant P envoie au participant V la transformation \|/, qu'il construit de telle sorte que pour a = 1, suite à l'application de cette transformation au graphe Gu, le graphe F1 = TtG, = H est obtenu et pour a = 0, en appliquant cette transformation au graphe Ga, on obtient le graphe F0 =
Zo Zapechnikov S.V. Protocoles cryptographiques et leur application
= 7i((p(G0))~7iG] = #, À l'étape (4), le participant V, en effectuant une vérification d'égalité graphique, détermine ainsi si la condition est satisfaite
N = Fa. Les étapes (1) à (4) sont répétées t fois. Si dans tous les m tours de ce protocole le résultat du test est positif, V accepte la preuve.
Tableau 1.4. Protocole de preuve de l'isomorphisme des graphes P V 1% - permutation aléatoire des sommets, calcule H = nGl 2 f n, si (a -1),
V = 1 / h 1 l o f if (a = 0) -> m times 4 Calcule le graphe \j/Ga et compare : H =\jfGa 5 Accepte la preuve si et seulement si pour Vm
Ce protocole est véritablement un protocole à connaissance nulle, puisque dans le cas d'isomorphes G0 ~ Gx, le participant V ne reçoit aucune information hormis les isomorphismes des graphes G0 et G\ avec quelques renumérotations aléatoires de ceux-ci, qu'il aurait pu recevoir et indépendamment , en choisissant un bit aléatoire a et en renumérotant aléatoirement le graphe Ga.
3. Preuve de connaissance du logarithme discret x du nombre X. Avant de démarrer le protocole, des grandeurs ouvertes sont précisées : p,
q- nombres premiers, tel que q\(p -1), élément g e Z*, nombre X. Do-]. Protocoles cryptographiques de base 31
la personne qui appelle P connaît la valeur secrète x\xTableau 1.5. Protocole de preuve de connaissance du logarithme discret P V I r&RZ
M = g (mod p) 2 A. Preuve de connaissance de la représentation du nombre y dans la base (preuve de connaissance nulle de la représentation y). Avant le début du protocole, des quantités ouvertes sont spécifiées et connues de tous les participants : nombres premiers p, q, éléments y, gvg2,..., gk Є Gq. Le prouveur P connaît les quantités secrètes ara 2,...,ake ZQ : y =
= 8і" " 8г1""> connaissance dont il doit prouver à V sans divulguer lui-même ces quantités. Le protocole est présenté dans le tableau. 1.6.
Tableau 1.6. Protocole de preuve des connaissances de représentation
nombres dans la base P V 1 rl.r2,...,rk. ЄІ( Zq, 2 5. Preuve de connaissance de la représentation d'un ensemble de nombres dans les bases correspondantes (preuve de connaissance nulle de la connaissance de l'égalité de représentation de tous y(j) dans les bases respectives). Avant le début du protocole, les quantités ouvertes sont spécifiées, connues
W I >\
connu de tous les participants : nombres premiers p, q, éléments y, 82^є pour certains (/). Le prouveur P connaît les valeurs secrètes 0C[,a2,...,a,. є Zq, tel que pour V/ у^ =
= (і^) " 1 > connaissance dont il doit prouver V,
sans divulguer ces valeurs elles-mêmes. Dans le tableau 1.7 montre un protocole qui résout ce problème.
Tableau 1.7. Protocole pour prouver la connaissance d'un ensemble de nombres
dans les bases correspondantes P V 1 rvr21...lrkeR pour U/ 2 (AiP«iT-(lt-
6. Preuve de connaissance de la relation multiplicative entre les valeurs engagées. Élément X = gx d'un sous-groupe cyclique commande simple, dans laquelle le problème du logarithme discret est considéré comme complexe sur le plan informatique, est appelé valeur déposée (valeur engagée), représentant la valeur secrète x. Laisser
d est un élément inconnu tel que h = gd. Avant le début du protocole, des quantités ouvertes sont spécifiées : nombres premiers p, q, éléments A, B, C Є Gq. Le prouveur de P connaît les quantités secrètes
a, a, b, b, c, c, tels que c = ab, A = gah"\ B = gbhb, C = gche. Il doit en prouver la connaissance V, sans divulguer les valeurs elles-mêmes. Dans le tableau 1.8 , avec - un protocole de ces preuves a été conservé.
Tableau 1.8. Protocole pour prouver la connaissance de la relation multiplicative des quantités déposées P V 1 М=і">/Ї, j Mt = gx-h*\ ¦ M2= Bx ¦ h"1 2 =CK-M2
divulgation de connaissances
Tableau 1.9. Structure des protocoles de preuve avec zéro P S : x є L - l'énoncé à prouver, h - dp, paramètres et quantités publics, s - données secrètes du prouveur expliquant pourquoi S est vrai, r - nombre aléatoire V 1 rp - aléatoire, 2 rv - nombre aléatoire,
c = LM Généralisons les exemples considérés et formulons un certain nombre de définitions. DANS vue générale Le protocole de preuve interactive avec connaissance nulle (Tableau 1.9) comprend quatre étapes :
Fin de tableau. 1.9 P S : xe L est l'énoncé à prouver, h représente d'autres paramètres et quantités accessibles au public, s est les données secrètes du prouveur expliquant pourquoi S est vrai, r est un nombre aléatoire V 3 R = f3(C,x) 4
le prouveur transfère au vérificateur ce qu'on appelle la preuve (témoin -W) - le résultat du calcul d'une fonction unidirectionnelle de la valeur secrète, dont il prouve la connaissance ;
le critique lui envoie une demande aléatoire ;
le prouveur répond à cette requête, et la réponse dépend à la fois de la requête aléatoire et de la valeur secrète, mais il est informatiquement impossible d'obtenir de lui cette valeur secrète ;
recevant la réponse, V vérifie sa cohérence avec les « preuves » transmises lors de la première étape.
Considérons les principes de base de la construction de preuves avec une divulgation de connaissance nulle : ce qu'implique la propriété de connaissance nulle.
Dans la théorie de la preuve de connaissance nulle, les connaissances P et V sont traitées comme des « boîtes noires » (Fig. 1.3).
Soit \tr ), \)Py ) l'ensemble de tous les messages transmis de P à V (respectivement de V à P), dont chacun est une variable aléatoire, et donc (x,h,rv,(mp ),( mv)) = = viewpy, ϐϵ)