Preuves sans connaissance : c'est comme par magie, mais je vais l'expliquer

Supposons que Peggy doive prouver à Victor qu'elle est en possession d'un secret sans le révéler. Pourra-t-elle le faire de manière à convaincre Victor qu'elle connaît vraiment le secret ? C’est la question au cœur de l’un des processus cryptographiques les plus puissants que nous puissions employer dans les systèmes d’identité : les preuves à connaissance nulle (ZKP) .

Supposons par exemple que Peggy possède un permis de conduire numérique et veuille prouver à Victor, le barman, qu'elle a plus de 21 ans sans simplement lui remettre son permis de conduire ni même lui montrer sa date de naissance. Les ZKP permettent à Peggy de prouver que son permis de conduire indique qu'elle a au moins 21 ans d'une manière qui convainc Victor sans que Peggy ait à révéler quoi que ce soit d'autre (c'est-à-dire qu'il n'y a aucune connaissance excessive ).

Ce problème a été exploré pour la première fois par les chercheurs du MIT Shafi Goldwasser, Silvio Micali et Charles Rackoff dans les années 1980 comme moyen de lutter contre les fuites d'informations. L’objectif est de réduire la quantité d’informations supplémentaires que le vérificateur, Victor, peut apprendre sur la prouveuse, Peggy.

Une façon de comprendre le fonctionnement des ZKP est l’histoire de la grotte d’Alibaba, publiée pour la première fois par les cryptographes Quisquater, Guillou et Berson1. Le diagramme suivant en fournit une illustration.

La grotte d'Alibaba comporte deux passages, étiquetés A et B, qui se séparent en un seul passage relié à l'entrée. Peggy possède un code secret qui lui permet de déverrouiller une porte reliant A et B. Victor veut acheter le code mais ne paiera pas tant qu'il ne sera pas sûr que Peggy le connaisse. Peggy ne le partagera pas avec Victor tant qu'il n'aura pas payé.

L'algorithme permettant à Peggy de prouver qu'elle connaît le code se déroule comme suit :

• Victor se tient à l'extérieur de la grotte pendant que Peggy entre et sélectionne l'un des passages. Victor n'est pas autorisé à voir quel chemin prend Peggy.
• Victor entre dans la grotte et crie « A » ou « B » au hasard.
• Peggy sort du bon passage car elle peut facilement déverrouiller la porte, quel que soit le choix qu'elle a fait en entrant.
• Bien sûr, Peggy aurait pu avoir de la chance et deviner correctement, alors Peggy et Victor répètent l'expérience plusieurs fois.

Si Peggy peut toujours revenir par le passage choisi par Victor, alors il y a de plus en plus de chances que Peggy connaisse vraiment le code. Après 20 essais, il y a moins d'une chance sur un million que Peggy devine simplement quelle lettre Victor appellera. Cela constitue une preuve probabiliste que Peggy connaît le secret.

Cet algorithme permet non seulement à Peggy de convaincre Victor qu'elle connaît le code, mais il le fait de manière à garantir que Victor ne puisse convaincre personne d'autre que Peggy connaît le code. Supposons que Victor enregistre l'intégralité de la transaction. La seule chose qu'un observateur voit, c'est Victor appelant des lettres et Peggy émergeant du tunnel de droite. L'observateur ne peut pas être sûr que Victor et Peggy ne se soient pas mis d'accord à l'avance sur une séquence de lettres pour tromper les observateurs.

Ainsi, même si Peggy ne peut pas nier à Victor qu'elle connaît le secret, elle peut nier qu'elle connaît le secret à d'autres tiers. Cela garantit que tout ce qu'elle prouve à Victor reste entre eux et que Victor ne peut pas le divulguer, du moins d'une manière cryptographique prouvant que cela vient de Peggy. Peggy garde le contrôle à la fois de son secret et du fait qu'elle le connaît.

Quand nous disons « zéro connaissance » et disons que Victor n’apprend rien au-delà de la proposition en question, ce n’est pas tout à fait vrai. Dans la grotte d'Alibaba, Peggy prouve en toute connaissance de cause qu'elle connaît le secret. Mais il y a bien d'autres choses que Victor apprend sur Peggy et pour lesquelles les ZKP ne peuvent rien faire. Par exemple, Victor sait que Peggy l’entend, parle sa langue, marche et est coopérative. Il pourrait également apprendre des choses sur la grotte, comme le temps qu'il faut pour déverrouiller la porte. Peggy apprend des choses similaires sur Victor. Donc, la réalité est que la preuve est une connaissance approximativement nulle et non une connaissance parfaitement nulle.

Systèmes ZKP

L'exemple de la Grotte d'Alibaba est une utilisation très spécifique des ZKP, ce qu'on appelle une preuve de connaissance à connaissance nulle . Peggy prouve qu'elle sait (ou possède quelque chose). Plus généralement, Peggy voudra peut-être prouver de nombreux faits à Victor. Ceux-ci pourraient inclure des phrases propositionnelles ou même des valeurs. Les ZKP peuvent également le faire.

Pour comprendre comment nous pouvons prouver des propositions en connaissance zéro, considérons un exemple différent, parfois appelé le problème du millionnaire socialiste . Supposons que Peggy et Victor veuillent savoir s'ils reçoivent un salaire équitable. Plus précisément, ils veulent savoir s'ils reçoivent le même montant, mais ne souhaitent pas divulguer leur taux horaire spécifique ni même à un tiers de confiance. Dans ce cas, Peggy ne prouve pas qu'elle connaît un secret, mais plutôt une proposition d'égalité (ou d'inégalité).

Pour plus de simplicité, supposons que Peggy et Victor reçoivent un salaire de 10 $, 20 $, 30 $ ou 40 $ de l'heure.

L'algorithme fonctionne comme ceci :

• Peggy achète quatre coffres-forts et les étiquette 10 $, 20 $, 30 $ et 40 $.
• Elle jette les clés de chaque boîte, sauf celle sur laquelle est inscrit son salaire.
• Peggy donne toutes les boîtes verrouillées à Victor qui met en privé un bout de papier avec un "+" dans la fente en haut de la boîte marquée de son salaire. Il met un bordereau avec un "-" dans toutes les autres cases.
• Victor rend les cartons à Peggy qui utilise sa clé en privé pour ouvrir le coffret avec son salaire dessus.
• Si elle trouve un « + » alors ils gagnent le même montant. Sinon, ils gagnent un montant différent. Elle peut utiliser cela pour prouver le fait à Victor.

C'est ce qu'on appelle un transfert inconscient et prouve la proposition VictorSalary = PeggySalary vraie ou fausse sans aucune connaissance (c'est-à-dire sans révéler aucune autre information).

Pour que cela fonctionne, Peggy et Victor doivent avoir confiance que l'autre se montrera disponible et indiquera son véritable salaire. Victor doit être sûr que Peggy jettera les trois autres clés. Peggy doit avoir confiance que Victor ne mettra qu'un seul feuillet avec un "+" dans les cases.

Tout comme les certificats numériques ont besoin d'une PKI pour établir une confiance au-delà de ce qui serait possible avec les seuls certificats auto-émis, les ZKP sont plus puissants dans un système qui permet à Peggy et Victor de prouver des faits à partir de ce que d'autres disent à leur sujet, et pas seulement de ce qu'ils disent. eux-mêmes. Par exemple, plutôt que Peggy et Victor déclarent eux-mêmes leur salaire, supposons qu'ils puissent s'appuyer sur un document signé du service des ressources humaines pour faire leur déclaration afin que tous deux sachent que l'autre déclare son véritable salaire. Les informations d'identification vérifiables fournissent un système permettant d'utiliser les ZKP pour prouver de nombreux faits différents, seuls ou de concert, de manière à donner confiance dans la méthode et dans les données.

ZKP non interactifs

Dans les exemples précédents, Peggy a pu prouver des choses à Victor grâce à une série d'interactions. Pour que les ZKP soient pratiques, les interactions entre le prouveur et le vérificateur doivent être minimes. Heureusement, une technique appelée SNARK permet des preuves non interactives sans connaissance.

Les SNARK ont les propriétés suivantes (d'où leur nom) :

• Succinct : les tailles des messages sont petites par rapport à la longueur de la preuve réelle.
• Non interactif : hormis certaines configurations, le prouveur n'envoie qu'un seul message au vérificateur.
• Arguments : il s’agit en réalité d’un argument selon lequel quelque chose est correct, et non d’une preuve telle que nous l’entendons mathématiquement. Plus précisément, le prouveur pourrait théoriquement prouver de fausses déclarations avec suffisamment de puissance de calcul. Ainsi, les SNARK sont « informatiquement solides » plutôt que « parfaitement sains ».
• de Connaissance : le prouveur connaît le fait en question.

Vous verrez généralement « zk » (pour zéro connaissance) affiché au recto pour indiquer qu'au cours de ce processus, le vérificateur n'apprend rien d'autre que les faits prouvés.

Les mathématiques sous-jacentes aux zkSNARK impliquent un calcul homomorphe sur des polynômes de haut degré. Mais nous pouvons comprendre comment fonctionnent les zkSNARK sans connaître les mathématiques sous-jacentes qui garantissent leur solidité. Si vous souhaitez plus de détails sur les mathématiques, je vous recommande "zkSNARKs in a Nutshell" de Christian Reitwiessner .

À titre d'exemple simple, supposons que Victor reçoive un hachage sha256 , H , d'une certaine valeur. Peggy veut prouver qu'elle connaît une valeur s telle que sha265(s) == H sans révéler s à Victor. Nous pouvons définir une fonction C qui capture la relation :

 C(x, w) = ( sha256(w) == x )

Ainsi, C(H, s) == true , tandis que les autres valeurs de w renverront false .

Le calcul d'un zkSNARK nécessite trois fonctions G , P et V . G est le générateur de clé qui prend un paramètre secret appelé lambda et la fonction C et génère deux clés publiques, la clé de preuve pk et la clé de vérification vk . Ils ne doivent être générés qu’une seule fois pour une fonction C donnée. Le paramètre lambda doit être détruit après cette étape car il n'est plus nécessaire et quiconque le possède peut générer de fausses preuves.

La fonction de preuve P prend en entrée la clé de preuve pk , une entrée publique x et un témoin privé (secret) w . Le résultat de l'exécution P(pk,x,w) est une preuve, prf , que le prouveur connaît une valeur pour w qui satisfait C .

La fonction vérificateur V calcule V(vk, x, prf) qui est vrai si la preuve prf est correcte et fausse sinon.

De retour à Peggy et Victor, Victor choisit une fonction C représentant ce qu'il veut que Peggy prouve, crée un nombre aléatoire lambda et exécute G pour générer les clés de preuve et de vérification :

 (pk, vk) = G(C, lambda)

Peggy ne doit pas apprendre la valeur de lambda . Victor partage C , pk et vk avec Peggy.

Peggy veut prouver qu'elle connaît la valeur s qui satisfait C pour x = H . Elle exécute la fonction de preuve P en utilisant ces valeurs comme entrées :

 prf = P(pk, H, s)

Peggy présente la preuve prf à Victor qui gère la fonction de vérification :

 V(vk, H, prf)

Si le résultat est vrai, alors le Victor peut être assuré que Peggy connaît la valeur s .

La fonction C n'a pas besoin d'être limitée à un hachage comme nous l'avons fait dans cet exemple. Dans les limites des mathématiques sous-jacentes, C peut être assez compliqué et impliquer un certain nombre de valeurs que Victor aimerait que Peggy prouve, en même temps.

Cet article est un extrait de mon livre Learning Digital Identity , publié par O'Reilly Media.

Remarques

1. Quisquater, Jean-Jacques ; Guillou, Louis C. ; Berson, Thomas A. (1990). Comment expliquer les protocoles de connaissance zéro à vos enfants (PDF). Avancées en cryptologie – CRYPTO '89 : Actes. Notes de cours en informatique. 435. pp. 628-631. est ce que je:10.1007/0-387-34805-0_60. ISBN978-0-387-97317-3.