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é : . (ZKP) les preuves à connaissance nulle 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 que le vérificateur, Victor, peut apprendre sur la prouveuse, Peggy. supplémentaires 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 que Peggy connaît le secret. preuve probabiliste 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. Notez que cette propriété repose sur l'algorithme utilisant un bon générateur de nombres pseudo-aléatoires avec une graine à haute entropie afin que Peggy et les observateurs tiers ne puissent pas prédire les choix de Victor. 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 nulle et non une connaissance nulle. approximativement parfaitement Systèmes ZKP L'exemple de la Grotte d'Alibaba est une utilisation très spécifique des ZKP, ce qu'on appelle une . 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. preuve de connaissance à connaissance nulle Pour comprendre comment nous pouvons prouver des propositions en connaissance zéro, considérons un exemple différent, parfois appelé le . 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é). problème du millionnaire socialiste 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 et prouve la proposition vraie ou fausse sans aucune connaissance (c'est-à-dire sans révéler aucune autre information). transfert inconscient VictorSalary = PeggySalary 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. 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. Les informations d'identification vérifiables 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. ont les propriétés suivantes (d'où leur nom) : Les SNARK les tailles des messages sont petites par rapport à la longueur de la preuve réelle. Succinct : : hormis certaines configurations, le prouveur n'envoie qu'un seul message au vérificateur. Non interactif 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 ». Arguments : le prouveur connaît le fait en question. de Connaissance : 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 , , d'une certaine valeur. Peggy veut prouver qu'elle connaît une valeur telle que sans révéler à Victor. Nous pouvons définir une fonction qui capture la relation : sha256 H s sha265(s) == H s C C(x, w) = ( sha256(w) == x ) Ainsi, , tandis que les autres valeurs de renverront . C(H, s) == true w false Le calcul d'un zkSNARK nécessite trois fonctions , et . est le générateur de clé qui prend un paramètre secret appelé et la fonction et génère deux clés publiques, la clé de preuve et la clé de vérification . Ils ne doivent être générés qu’une seule fois pour une fonction donnée. Le paramètre doit être détruit après cette étape car il n'est plus nécessaire et quiconque le possède peut générer preuves. G P V G lambda C pk vk C lambda de fausses La fonction de preuve prend en entrée la clé de preuve , une entrée publique et un témoin privé (secret) . Le résultat de l'exécution est une preuve, , que le prouveur connaît une valeur pour qui satisfait . P pk x w P(pk,x,w) prf w C La fonction vérificateur calcule qui est vrai si la preuve est correcte et fausse sinon. V V(vk, x, prf) prf De retour à Peggy et Victor, Victor choisit une fonction représentant ce qu'il veut que Peggy prouve, crée un nombre aléatoire et exécute pour générer les clés de preuve et de vérification : C lambda G (pk, vk) = G(C, lambda) Peggy ne doit pas apprendre la valeur de . Victor partage , et avec Peggy. lambda C pk vk Peggy veut prouver qu'elle connaît la valeur qui satisfait pour . Elle exécute la fonction de preuve en utilisant ces valeurs comme entrées : s C x = H P prf = P(pk, H, s) Peggy présente la preuve à Victor qui gère la fonction de vérification : prf 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 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, peut être assez compliqué et impliquer un certain nombre de valeurs que Victor aimerait que Peggy prouve, en même temps. C C Cet article est un extrait de mon livre , publié par O'Reilly Media. Learning Digital Identity Remarques 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. Également publié ici.
