May 21, 2021

Zero Knowledge Proof

5 MIN READ – TEAM XSL LABS

Share on twitter
Share on telegram
Share on email
Share on linkedin
Share on facebook

Zero Knowledge Proof

Les données personnelles représentent un enjeu majeur pour les grandes entreprises du numérique, sans s’y limiter. Les GAFAM, et plus particulièrement les réseaux sociaux exploitent les données personnelles de leurs utilisateurs, ce qui leur permet de les revendre à des tiers principalement dans le domaine de la publicité ciblée, et générer ainsi des dizaines de milliards de bénéfices (1). Ceci grâce à nos données, grâce à vos données, et le développement d’outils toujours plus précis permettant de récolter et analyser ce qui constitue notre identité. Le scandale Cambridge Analytica de 2018 a montré que l’intérêt pour nos données dépasse leur simple monétisation, allant jusqu’à chercher à potentiellement manipuler des élections, et remettant en cause l’idée même de démocratie.
Ces mécanismes de collecte sont généralisés, particulièrement dans le domaine de la publicité. Derrière le but affiché d’ « améliorer l’expérience utilisateur », nous ne savons pas ce qui est fait de nos données, qui les utilise, à qui elles sont transmises. C’est le point de départ du règlement général sur la protection des données (RGPD) entré en vigueur le 25 Mai 2018, qui veut soumettre la collecte de ces données personnelles au consentement des utilisateurs, et qui dans les faits est entré en application en Mars 2021 en France.
En outre, et au-delà de cette collecte et de ce qu’on appelle communément le « Big Data », les données centralisées représentent un intérêt croissant pour les hackers. Chaque semaine, de nouveaux cas de piratage de bases de données sont découverts, et les informations représentent une manne financière également importante sur le dark web (2).
Le but de XSL Labs est de fournir une solution qui permettra de reprendre la main sur nos données personnelles. L’utilisation de protocoles de type Zero Knowledge Proof (ZKP), que l’on peut traduire par « preuve à divulgation nulle de connaissance » ou « preuve sans connaissance » constitue un des moyens de parvenir à ces objectifs.

Historique

Le ZKP est un protocole interactif entre deux parties, le fournisseur de preuve et le vérificateur. Le fournisseur de la preuve prouve au vérificateur qu’une proposition est vraie sans transmettre aucune autre information. Imaginé dans les années 1980 par Goldwasser, Micali et Rackoff (3), le ZKP a donc pour but de transmettre la preuve de véracité d’une information sans révéler celle-ci.

Leur définition exacte se retrouve dans ces termes : « Les preuves à connaissance nulle sont définies comme les preuves qui ne transmettent aucune connaissance supplémentaire autre que l’exactitude de la proposition en question ».

Le ZKP possède trois propriétés essentielles :

– Sa consistance : Il s’agit d’une propriété indiquant que dès lors que le protocole est suivi par les deux parties, alors la preuve doit toujours être acceptée par le vérificateur.
– Sa robustesse : Si la proposition est fausse, alors le fournisseur de la preuve ne pourra pas convaincre le vérificateur que la proposition est vraie, ou avec une probabilité extrêmement faible.

– L’absence d’apport d’information (zero knowledge) : Le vérificateur ne peut obtenir que la véracité de la proposition de la part du fournisseur de preuve. Le vérificateur n’obtient strictement aucune autre information nouvelle.

Le protocole du ZKP interactif est indiqué protocole Σ « sigma », en ce qu’il s’agit d’un protocole à 3 échanges :

– l’engagement : Dans cette phase, le fournisseur de preuve indique qu’il peut prouver la véracité de l’information au vérificateur
– le défi : Il s’agit de la réponse envoyée par le vérificateur
– la réponse : Littéralement la réponse à ce défi de la part du fournisseur de preuve.

La caverne d’Ali Baba

Afin d’expliquer la preuve à divulgation nulle de connaissance, un exemple courant est inscrit dans l’article « How to explain Zero-Knowledge Protocols to your Children » (4), basé sur le conte d’Ali Baba et que nous allons résumer ici.

Dans cet exemple, Ali Baba se fait voler sa bourse par un voleur, qui s’enfuit dans une grotte possédant deux passages, un en direction de la gauche, l’autre en direction de la droite. Ali Baba qui a suivi le voleur ne sait pas dans quelle direction celui-ci est allé.
Il choisit donc le passage gauche, mais arrive dans un cul-de-sac. Il se dit donc que le voleur a dû prendre l’autre direction. Tentant d’emprunter le passage de droite, il se rend compte qu’il s’agit également d’un cul-de-sac, et ne retrouve pas le voleur.
Les jours suivant, ce phénomène se reproduit, Ali Baba se fait de nouveau voler, arrive devant cette grotte et ne retrouve pas le voleur, quelle que soit la direction empruntée. Au bout de 40 jours, Ali Baba finit par se rendre à l’évidence : il ne peut pas y avoir de hasard derrière ceci car la probabilité qu’il prenne toujours la mauvaise direction est trop infime. Il décide donc de se cacher au fond de la caverne, et découvre que les voleurs utilisent un mot magique qui leur permet de passer d’un côté à l’autre de la grotte, il existait en effet une porte cachée reliant les passages.

A partir de cette situation, imaginons deux personnages que nous appellerons Alice et BoB, et une grotte avec une bifurcation ouvrant vers les passages A et B qui sont, de l’autre côté, reliés par une porte fermée qui s’ouvre avec un mot magique.

Bob veut prouver à Alice qu’il connaît le mot magique qui permet d’ouvrir la porte, mais sans donner ce mot à Alice (sans divulgation d’information).

Pour procéder, un scénario est créé :

Etape 1 : Alice attend devant la grotte, sans regarder. Bob entre dans la grotte par l’un des passages, au hasard et va jusqu’à la porte.
Etape 2 : Une fois ceci fait, Alice vient à la bifurcation et lance une pièce. En fonction du résultat, elle crie A ou B.
Etape 3 : Bob doit apparaître du côté de la sortie demandée par Alice à l’étape 2.

Zero Knowledge Proof

Ainsi, si Bob connaît réellement le mot magique, il est facile pour lui de répondre à la requête d’Alice et apparaître systématiquement du bon côté.
En revanche, s’il ne connaît pas le mot magique, il a une chance sur deux de se tromper à chaque essai puisqu’il est déjà d’un côté de la grotte, et que pour réussir, ce côté doit correspondre à celui demandé par Alice après le lancer de pièce.
Si le scénario est reproduit, les chances de succès diminuent, et ainsi en une vingtaine de tentatives successives par exemple, la probabilité de réussite est de 1/220 soit moins d’une chance sur un million.

Ainsi dans cet exemple, la répétition du scénario sous la forme d’un jeu interactif montre qu’il devient de plus en plus improbable que Bob ne connaisse pas le mot magique. Un bémol est donc à apporter : ce système ne permet jamais de garantir à cent pour cent que la proposition est vraie.

On peut en revanche imaginer un protocole différent ou Alice se place d’emblée à la bifurcation, puis Bob entre par l’un des côtés de la grotte pour ressortir par l’autre côté, ce qui prouve en un seul essai que Bob connaît le mot magique, sans donner d’autre information à Alice que la preuve qu’il le connaît. A noter que dans un tel cas de figure, ceci pourrait être observé ou enregistré par Alice ou un tiers. Dans ce cas, n’importe qui pourrait être au fait de la détention du mot magique par Bob.

L’exemple initial constitue un cas de ZKP sous forme interactive : comme indiqué précédemment, le protocole prend la forme d’un « jeu » itératif entre les deux parties.

Le ZKP et la protection des données

Comme souligné par la CNIL dans un document de Septembre 2018 concernant le RGPD (5) vis-à-vis de la blockchain, les exigences du RGPD sont difficilement applicables.
En effet l’une des propriétés de la blockchain consiste en l’irréversibilité des données inscrites : une fois une donnée stockée sur la blockchain, elle ne peut pas être modifiée ni supprimée.

Ainsi si les droits d’accès et de portabilité des données à caractère personnel peuvent être exercés de manière effective, il n’en va pas de même s’agissant des droits de rectification et suppression des données inscrites sur la blockchain.
La CNIL constate qu’il est « techniquement impossible de faire droit à la demande d’effacement de la personne concernée lorsque des données sont inscrites dans la blockchain » et présente dans ce document des premières recommandations, dans l’attente d’une évaluation approfondie.

L’idée principale est qu’il ne convient pas d’inscrire de données à caractère personnel en clair sur la blockchain.

Dans la pratique, l’ensemble des transactions traditionnelles (par exemple dans le cadre du bitcoin) sont publiques. L’idée est que n’importe qui peut constater le solde d’un acteur ainsi que ses transactions, et le pseudonymat est dans les faits une illusion de vie privée au sens où les pseudonymes peuvent être in fine reliés à des individus (6).

De façon notable, le projet Zcash recourt au ZKP non interactif afin de pouvoir cacher l’ensemble des données (7). Ce projet s’appuie sur les « zk-SNARKs » (pour Zero-Knowledge Succinct Non- Interactive Argument of Knowledge), un système spécifique de preuve efficace (succinct) qui consiste en un seul message transmis de la part du fournisseur de preuve vers le vérificateur (non- interactif). Mais d’autres acteurs s’intéressent à ces preuves sans divulgation d’information, c’est le cas notamment de JP Morgan ou ING (8)

Rappelons ici la différence principale entre des protocoles interactifs et non interactifs en matière de ZKP : Le protocole interactif nécessite une répétition des interactions entre le fournisseur de la preuve et le vérificateur, alors que le protocole non interactif ne demande qu’un minimum d’interactions, typiquement uniquement l’envoi d’une preuve au système, de manière à ce que n’importe quel vérificateur puisse avoir accès à cette preuve à tout moment.

S’agissant de XSL Labs, le SDI se comportera le cas échéant comme un protocole de ZKP. L’exemple courant concerne une vérification de majorité qui ne nécessitera pas de transmettre les informations d’un document d’identité mais simplement une preuve attestant « l’âge est supérieur à 18 ans », ne fournissant pas l’information « date de naissance », ni même « âge » de façon précise, et encore moins toutes les informations qui peuvent être contenues dans un document d’identité. D’autres cas simples peuvent consister par exemple en une preuve de possession d’une certaine somme sans indiquer à l’autre partie le montant total de nos fonds ni révéler des informations bancaires, particulièrement sensibles (un exemple typique réside dans le Yao’s Millionnaire Problem (9), qui peut trouver des réponses dans des protocoles ZKP).

Ainsi, le ZKP constitue une technologie d’avenir qui permettra de résoudre des problématiques liées à la sécurité des données, et ouvrent une voie dans la résolution des problématiques liées au règlement européen sur la protection des données personnelles. Ce système de preuve sans apport de connaissance commence à s’insérer progressivement dans différentes industries, à commencer typiquement par certaines banques, et cette technologie pourra à l’avenir trouver des applications dans de nombreux domaines qui relèvent de la protection de l’information, à commencer par l’authentification, la recherche, voire même le vote électronique. L’utilisation des ZKP est amené à se répandre massivement, et ils pourraient devenir une norme dans le futur. À XSL Labs, nous nous ancrons dans cette révolution des usages, et participons ainsi à l’évolution de l’internet de confiance.


Copyright © 2020 XSL Labs – All rights reserved