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 :
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.
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 approximativement nulle et non une connaissance parfaitement nulle.
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 :
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.
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) :
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.
Également publié ici.