Preuves sans connaissance : un exemple illustré. Protocole de preuve sans connaissance pour les informations sensibles

La preuve à connaissance nulle est un protocole cryptographique qui permet à l'une des parties (le vérificateur, partie B) de vérifier que l'autre partie (le prouveur, partie A) connaît une déclaration, tandis que le vérificateur ne reçoit aucune autre information sur la déclaration. lui-même. En d’autres termes, A prouve la connaissance du secret sans révéler le secret lui-même.

L'utilisation de preuves sans connaissance pour prouver l'identité a été proposée pour la première fois par Uriel Fieg, Amos Fiat et Adi Shamir. Dans ce cas, l'utilisateur prouve qu'il connaît sa clé privée, qui fait ici office de secret, sans la révéler. De cette façon, il prouve son identité.

La preuve sans connaissance a trois propriétés principales :
1. Complétude. Si le prouveur connaît la déclaration, il sera alors en mesure d’en convaincre le vérificateur.
2. Exactitude. Si le prouveur ne connaît pas la déclaration, il ne peut alors tromper le vérificateur qu'avec une probabilité négligeable.
3. Zéro connaissance. Le vérificateur, même s'il se comporte de manière malhonnête, n'apprendra rien d'autre que le fait même que la déclaration est connue du prouveur.

La preuve prend la forme d'un protocole interactif. Cela signifie que la partie B pose une série de questions au prouveur qui, s'il connaît le secret, répondra correctement à toutes les questions. Si le secret est inconnu de la partie A, mais qu'elle souhaite convaincre l'examinateur du contraire, elle a une certaine probabilité (peut-être 50 %, comme dans les exemples de cette rubrique) de répondre correctement à la question. Cependant, après un certain nombre de questions (10 à 20), le vérificateur est convaincu avec une probabilité assez élevée que le prouveur ne connaît pas le secret. Cependant, aucune des réponses ne donne d’informations sur le secret lui-même.

Grotte du savoir zéro

La preuve de la connaissance nulle est bien expliquée par Jean-Jacques Quiskater et Louis Guilloux à partir de l'histoire de la caverne d'Ali Baba (voir figure). Pour traverser la grotte, vous devez ouvrir la porte entre C et D. La porte ne s'ouvre que lorsque quelqu'un prononce les mots magiques. Faites connaître à Peggy les mots magiques et souhaitez le prouver à Victor sans révéler les mots eux-mêmes.

Voici comment fonctionne une preuve sans connaissance dans ce cas :
1. Victor est au point A.
2. Peggy traverse la grotte jusqu'à la porte, soit par le passage C, soit par le passage D. Victor ne voit pas dans quelle direction Peggy est allée. Après que Peggy ait disparu dans la grotte, Victor se déplace vers le point B.
3. Victor crie à Peggy de sortir de la grotte soit par le passage de gauche, soit par le passage de droite.
4. Peggy, utilisant des mots magiques pour déverrouiller la porte si nécessaire, sort de la grotte par le passage par lequel Victor lui a demandé de sortir.
5. Peggy et Victor répètent les étapes 1 à 4 plusieurs fois.

Dans le cas où Peggy ne connaît pas le secret, alors elle ne pourra pas tromper Victor si les étapes de preuve (accréditation) sont répétées plusieurs fois de suite. Puisqu'elle ne peut sortir que par le passage dans lequel elle est entrée, à chaque tour du protocole il y a 50 % de chances de deviner de quel côté Victor lui demandera de sortir. En conséquence, sa probabilité de tromper Victor est également de 50 %. Cependant, la probabilité de le tromper en deux tours est déjà de 25 %, et en n tours elle n'a qu'une chance sur 2^n. Victor peut supposer avec confiance que si tous les n (n=10-20) tours de preuve de Peggy sont corrects, alors elle connaît effectivement les mots secrets qui ouvrent la porte entre les points C et D.

Si Victor enregistre tout ce qui se passe sur une caméra vidéo, cet enregistrement vidéo ne constitue pas une preuve pour un tiers. Peggy et Victor auraient pu convenir à l'avance de l'endroit où Victor lui demanderait de partir. Puis elle quittera à chaque fois le lieu indiqué par Victor, sans connaître les mots magiques. D'un autre côté, Victor peut simuler l'enregistrement vidéo, n'y laissant que les tentatives réussies de Peggy, supprimant tout le reste.

Il convient de noter que l’analogie avec la grotte n’est pas tout à fait correcte. Puisque, pour prouver sa connaissance des mots, Peggy peut simplement entrer par un côté, tandis que Victor voit par où elle est allée, et sortir par l'autre. Cependant, ce protocole décrit parfaitement une preuve à connaissance nulle d’un point de vue mathématique.

Protocole Fiat-Shamir

L'un des protocoles les plus connus d'identification personnelle par preuve à connaissance nulle est le protocole proposé par Amos Fiat et Adi Shamir, dont la force repose sur la difficulté d'extraire la racine carrée modulo d'un nombre composé n suffisamment grand dont la factorisation est inconnu.

Auparavant, avant la preuve elle-même, le centre de confiance T sélectionne et publie un module d'un nombre n = p*q suffisamment grand, difficile à factoriser. Dans ce cas, p, q sont des nombres premiers et sont gardés secrets. Chaque utilisateur A choisit un secret s dans l'intervalle (1, n−1) premier à n. Ensuite, la clé publique v = s^2 (mod n) est calculée.

Le v résultant est enregistré par le centre de confiance en tant que clé publique de l'utilisateur A, et la valeur s est le secret de A. C'est la connaissance de ce secret s que A doit prouver à la partie B sans le divulguer lors des t tours. Chaque accréditation comprend les étapes suivantes :
1. A sélectionne un r aléatoire dans l'intervalle (1, n−1) et envoie x = r^2 (mod n) au correspondant B.
2. B sélectionne au hasard le bit e (0 ou 1) et l'envoie à A.
3. A calcule y = r*s^e (mod n) et le renvoie à B.
4. Le côté B vérifie l'égalité y^2 ≡ x*v^e (mod n). Si c'est vrai, alors le passage au prochain tour du protocole a lieu, sinon la preuve n'est pas acceptée.

Choisir e dans l'ensemble implique que si la partie A connaît vraiment le secret, alors elle sera toujours en mesure de répondre correctement, quel que soit le e choisi. Disons que A veut tromper B, choisit un r aléatoire et envoie x = r^2 / v, alors si e = 0, alors A renvoie avec succès B y = r, dans le cas de e = 1, A ne sera pas capable de répondre correctement, t .To. ne connaît pas s, et extraire la racine carrée de v modulo n est assez difficile.

La probabilité que l'utilisateur A ne connaisse pas le secret s, mais convainc l'inspecteur B du contraire sera estimée par la probabilité égale à p = =2^(–t), où t est le nombre d'accréditations. Pour obtenir une fiabilité élevée, il est choisi suffisamment grand (t = 20 − 40). Ainsi, B est certifié pour connaître A si et seulement si tous les t tours sont réussis.

Pour que ce protocole s'exécute correctement, la partie A ne doit jamais réutiliser la valeur de x. Si A faisait cela et que B, dans une autre boucle, envoyait à A un autre bit aléatoire r à l'étape 2, alors B aurait les deux réponses de A. B pourrait alors calculer la valeur de s et connaîtrait la clé secrète d'Alice.

Conclusion

Pour des implémentations telles que les cartes à puce, le protocole Fiat-Shamir décrit n'est pas très adapté, car les échanges avec le monde extérieur prennent du temps, et le stockage des données pour chaque accréditation peut rapidement épuiser les capacités limitées de la carte. Par conséquent, Gillu et Kiskatr ont développé un algorithme d’identification à connaissance nulle plus adapté à de telles applications. Les échanges entre Peggy et Victor, ainsi que les accréditations parallèles dans chaque échange, sont réduits au strict minimum : pour chaque preuve il n'y a qu'un seul échange, dans lequel il n'y a qu'une seule accréditation. Il existe également un système Schnorr, qui constitue une alternative aux systèmes Gillu-Kiskatra et Fiat-Shamir. Si le sujet vous plaît, j'en parlerai dans mon prochain sujet.

Nous avons déjà examiné ce qu'est un protocole Zk-SNARK ou Zero Knowledge Proof en termes simples, mais dans cet article, nous aimerions approfondir davantage la partie technique de ce phénomène.

Protocole Zero-Knowledge Proof : Comment ça marche ?

Ainsi, pour rappel, la preuve de nullité d'accord permet de prouver que vous êtes propriétaire de certaines informations sans en divulguer le contenu. Pour mettre en œuvre ce concept, il faudra introduire 3 algorithmes à la fois, que nous désignerons par GK, P et V. Considérons leur objectif :

• GK est un générateur de clé qui accepte les entrées α et le programme C, générant deux clés : une clé de vérification pour le vérificateur PK et une clé de vérification pour la vérification VK. Ces clés sont publiques pour toutes les parties impliquées dans la preuve.
• P est un utilisateur qui doit utiliser 3 types de données d'entrée pour preuve : 1) clé de vérification PK ; 2) entrée aléatoire X, qui sera accessible au public aux parties ; 3) une affirmation qui doit être prouvée sans révéler sa signification - W. L'algorithme P lui-même génère une preuve Preuve, qui satisfera aux conditions suivantes : Preuve = P (PK ; X ; W).
• V est un algorithme de vérification qui renvoie une variable booléenne. Il peut être représenté par deux valeurs : TRUE (vrai) ou FALS (faux). Ainsi, le vérificateur prend les données d'entrée suivantes V(VK; X; Preuve), sur la base desquelles il détermine si elles sont vraies ou fausses.

C’est ainsi que fonctionne un protocole de preuve sans connaissance. La seule chose dont je voudrais parler séparément est le sens α, mentionné dans le paragraphe sur GK. Le fait est que ce paramètre complique considérablement l'utilisation de Zk-SNARK dans des applications réelles, car quiconque le possède peut créer une fausse preuve, à laquelle le système reviendra True. Les développeurs de ZCash, une crypto-monnaie qui utilise une technologie zéro-proof, sont aux prises avec ce problème depuis très longtemps.

L’utilisation d’une preuve de connaissance nulle d’informations sensibles peut être illustrée par un exemple spécifique. Supposons qu'il y ait une grotte. L'entrée de la grotte se trouve au point A, et au point B, la grotte se divise en deux moitiés - C et D. La grotte a un secret : seuls ceux qui connaissent les mots magiques peuvent ouvrir la porte située entre C et D.

Anton connaît les mots magiques, pas Boris. Anton veut prouver à Boris qu'il connaît les mots magiques, mais de telle manière que Boris reste toujours dans l'ignorance de ces mots. Anton peut alors utiliser le protocole suivant :

1. Boris se trouve au point A.

2. A son choix, Anton s'approche de la porte soit par le point C,

ou du point D.

3. Boris se déplace au point B.

4. Boris ordonne à Anton d'apparaître soit par le passage de gauche jusqu'à la porte,

ou par le bon.

5. Anton obéit aux ordres de Boris, si nécessaire en utilisant

des mots magiques pour passer la porte.

6. Les étapes 1 à 5 sont répétées n fois, où n est le paramètre de protocole.

Supposons que Boris dispose d’une caméra vidéo avec laquelle il enregistre toutes les disparitions d’Anton dans les profondeurs de la grotte et toutes ses apparitions ultérieures. Si Boris montre les enregistrements de toutes les n expériences qu'il a réalisées avec Anton, ces enregistrements peuvent-ils servir de preuve qu'Anton connaît des mots magiques pour une autre personne (par exemple, pour Vladimir) ?

À peine. Vladimir ne pourra jamais s'assurer qu'Anton n'a pas informé Boris à l'avance de ses intentions à chaque fois, de sorte que Boris lui ordonnerait alors de sortir exactement du côté de la porte par laquelle Anton est entré. Ou que toutes les expériences infructueuses au cours desquelles Anton n’a pas pu exécuter les ordres de Boris n’ont pas été supprimées de l’enregistrement vidéo réalisé.

Cela signifie que Boris est incapable de convaincre Vladimir, qui n'était pas personnellement présent lors des expériences dans la grotte, qu'Anton a réellement confirmé sa connaissance du secret. Cela signifie que le protocole de preuve utilisé par Anton se caractérise précisément par l'absence de divulgation d'informations confidentielles. Si Anton ne connaît pas les mots magiques qui ouvrent la porte de la grotte, alors en observant Anton, Boris ne pourra rien découvrir. Si Anton connaît les mots magiques, alors même un enregistrement vidéo détaillé des expériences réalisées n'aidera pas Boris. D’abord parce qu’en le regardant, Boris ne verra que ce qu’il a déjà vu en direct. Et deuxièmement, parce qu'il est presque impossible de distinguer l'enregistrement vidéo falsifié par Boris de l'authentique.

Le protocole de preuve sans connaissance fonctionne du fait que sans connaître les mots magiques, Anton ne peut sortir que du côté par lequel il est entré. Par conséquent, ce n'est que dans 50 % des cas qu'Anton pourra tromper Boris en devinant de quel côté il lui demandera de partir. Si le nombre d'expériences est n, Anton ne réussira tous les tests que dans un cas sur 2 n. En pratique, vous pouvez vous limiter à n=16. Si Anton exécute correctement les ordres de Boris dans les 16 cas, alors il connaît vraiment le secret des mots magiques.

L’exemple de la grotte est illustratif, mais présente un défaut important. Il est beaucoup plus facile pour Boris de voir comment, au point B, Anton tourne dans une direction puis apparaît du côté opposé. Un protocole de preuve sans connaissance n’est tout simplement pas nécessaire ici.

Par conséquent, supposons qu’Anton ne connaisse pas certains mots magiques, comme « Open Sesame ». Non, Anton a des informations plus intéressantes - il a été le premier à trouver une solution à ce problème difficile. Pour prouver ce fait à Boris, Anton n'a pas besoin de démontrer sa décision à tout le monde. Tout ce qu'il a à faire est d'appliquer le protocole de preuve de connaissance zéro suivant pour les informations confidentielles :

1. Anton utilise les informations dont il dispose et les informations générées

un nombre aléatoire pour réduire un problème difficile à un autre problème difficile isomorphe au problème d'origine. Anton résout alors ce nouveau problème.

2. Anton utilise le protocole de prédiction de bits pour le bit trouvé sur

étape 1 de la décision, de sorte que plus tard, si Boris a besoin de se familiariser avec cette décision, Boris puisse vérifier de manière fiable que la décision présentée par Anton a bien été reçue par lui à l'étape 1.

3. Anton montre un nouveau problème difficile à Boris,

4. Boris demande à Anton de prouver que deux problèmes difficiles

(ancien et nouveau) sont isomorphes, ou fournissent la solution qu'Anton aurait dû trouver à l'étape 1 et prouvent qu'il s'agit bien d'une solution au problème auquel Anton a réduit le problème original dans la même étape.

5. Anton répond à la demande de Boris.

6. Anton et Boris répètent les étapes 1 à 6 n fois, où n est un paramètre

protocole.

Les problèmes difficiles à résoudre, la méthode de réduction d'un problème à un autre, ainsi que les nombres aléatoires doivent, si possible, être choisis de manière à ce que Boris n'ait aucune information sur la solution du problème d'origine même après avoir répété les étapes du protocole.

Tous les problèmes difficiles à résoudre ne peuvent pas être utilisés dans des preuves d'informations confidentielles sans connaissance, mais la plupart d'entre eux sont tout à fait adaptés à de telles fins. Les exemples incluent la recherche d'un cycle de Hamilton (un chemin fermé passant par tous les sommets du graphe une seule fois) dans un graphe connecté et la détermination de l'isomorphisme du graphe (deux graphes sont isomorphes s'ils ne diffèrent que par les noms de leurs sommets).