Preuves à divulgation nulle de connaissance : introduction aux principes fondamentaux

Introduction

Les preuves à divulgation nulle de connaissance comptent parmi les outils les plus puissants conçus par les cryptographes. Malheureusement, elles restent incomprises du grand public. Cet article vise à y remédier en proposant une présentation complète des preuves à divulgation nulle de connaissance à partir de leurs principes fondamentaux. Nous abordons la théorie, les mathématiques et la cryptographie qui les sous-tendent afin que chacun puisse comprendre les dernières avancées sur Solana, notamment ZK Compression et l’avenir de l’interopérabilité.

Cet article suppose une connaissance du modèle de programmation de Solana et des primitives cryptographiques propres aux systèmes blockchain (c’est-à-dire les fonctions de hachage, les pointeurs de hachage, les arbres de Merkle et les arbres de Merkle concurrents). Si ces concepts sont nouveaux pour vous, je vous recommande de commencer par lire les articles de blog suivants :

• Les outils cryptographiques pour débutants — Explication des fonctions de hachage et des arbres de Merkle
• Le modèle de programmation de Solana : introduction au développement sur Solana

Notez que cet article a été conçu dans une optique de modularité. Il est recommandé aux personnes qui découvrent ces sujets de lire chaque section et sous-section dans l’ordre. Toutefois, si vous connaissez déjà certains sujets ou souhaitez en approfondir un en particulier, vous pouvez accéder directement à la section correspondante.

Il s’agit également du premier article d’une série en deux parties consacrée aux preuves à divulgation nulle de connaissance. Nous vous recommandons vivement de lire cet article avant de passer à Preuves à divulgation nulle de connaissance : leurs applications sur Solana.

La théorie des preuves à divulgation nulle de connaissance

En 1989, les chercheurs du MIT Shafi Goldwasser, Silvio Micali (fondateur d’Algorand) et Charles Rackoff ont publié La complexité de la connaissance dans les systèmes de preuve interactifs. Ils travaillaient sur des systèmes dans lesquels une partie (le prouveur) échange des messages avec une seconde partie (le vérificateur) afin de la convaincre qu’un énoncé mathématique est vrai. Ils ont été les premiers à poser la question suivante : « Que se passe-t-il si le prouveur et le vérificateur ne se font pas confiance ? » Il s’agit ici de déterminer la quantité d’informations que le vérificateur peut apprendre au fil de ces échanges, au-delà du simple fait que l’énoncé est vrai. Par exemple, le prouveur peut vouloir convaincre le vérificateur qu’il connaît la solution d’une énigme complexe sans révéler la solution elle-même.

Quel type de problèmes cherchons-nous à résoudre ?

Tricoloration de graphe

La tricoloration de graphe est un problème classique en informatique et en théorie des graphes. Elle consiste à colorier les sommets d’un graphe avec trois couleurs de sorte qu’aucun sommet adjacent ne partage la même couleur. Pour un graphe à trois sommets, l’opération est simple. Cependant, elle devient de plus en plus difficile à mesure que le nombre de sommets augmente.

La création des emplois du temps universitaires constitue une application concrète. Dans une grande université, les emplois du temps doivent être conçus de sorte qu’aucun étudiant n’ait des cours qui se chevauchent. Chaque cours peut être représenté par un sommet dans un graphe, tandis que les arêtes représentent les étudiants communs à plusieurs cours. Ainsi, deux cours suivis par un même étudiant ne sont jamais programmés au même moment. Il faut également tenir compte de contraintes telles que la capacité des salles, les horaires privilégiés par les enseignants et la répartition uniforme des cours sur la semaine. Les créneaux horaires et les salles doivent donc être attribués aux cours de manière à ce que deux cours adjacents ne partagent pas le même créneau. La tricoloration de graphe permet de résoudre ce problème.

Imaginons maintenant que l’emploi du temps final doive être vérifié par un cabinet d’audit externe. En raison de réglementations spécifiques sur la confidentialité, l’université ne peut pas communiquer aux auditeurs les informations détaillées sur les inscriptions des étudiants. Elle doit plutôt prouver que l’emploi du temps final respecte les contraintes requises sans révéler quels étudiants sont inscrits à quels cours. 

Pour ce faire, l’université doit créer un graphe dans lequel chaque sommet représente un cours. Une arête relie deux sommets si les cours correspondants ont au moins un étudiant en commun. L’université attribue des créneaux horaires à chaque cours de manière à ce qu’aucun cours adjacent ne soit programmé simultanément. Elle prend ensuite un engagement sur son emploi du temps final à l’aide d’un schéma d’engagement cryptographique. Pour cela, elle crée un hachage cryptographique du créneau attribué à chaque cours et transmet les hachages au vérificateur sans révéler les créneaux. Le cabinet d’audit externe sélectionne alors aléatoirement des paires de cours adjacents afin de contester le créneau attribué. L’université révèle les créneaux engagés pour la paire de cours adjacents sélectionnée et fournit les engagements d’origine (c’est-à-dire les hachages), afin que le cabinet d’audit externe puisse vérifier les valeurs révélées. Ces dernières étapes de contestation, de révélation et de vérification sont répétées jusqu’à ce que le cabinet d’audit externe soit convaincu qu’aucun cours ne se chevauche. Je vous recommande vivement la démonstration interactive de tricoloration à divulgation nulle de connaissance du MIT pour observer ces étapes en temps réel.

L’université veut prouver au cabinet d’audit externe qu’elle connaît un emploi du temps correct. Autrement dit, elle veut prouver à une autre partie qu’elle sait quelque chose. L’intérêt de ce problème est qu’il est NP-complet.

NP-complet

Dans la théorie de la complexité algorithmique, un problème est NP-complet lorsque :

• Pour toute entrée du problème, la sortie est soit « oui », soit « non »
• Lorsque la réponse est « oui », elle peut être démontrée à l’aide d’une solution courte
• La validité de chaque solution doit pouvoir être vérifiée rapidement, et un algorithme de force brute peut trouver une solution en essayant toutes les solutions possibles

Les problèmes NP-complets sont importants, car ils représentent les problèmes les plus difficiles de la classe NP (c’est-à-dire un ensemble d’énigmes très complexes pour lesquelles il est facile de vérifier une solution proposée en temps polynomial, mais difficile de trouver cette solution). Ces problèmes se distinguent par leur capacité universelle de simulation. Autrement dit, si nous pouvons résoudre rapidement un problème NP-complet, nous pouvons réduire ou transformer n’importe quel problème NP en problème NP-complet et trouver sa solution en temps polynomial. Il est également facile de vérifier les solutions aux problèmes NP-complets. 

Ainsi, nous disposons de toute une classe de problèmes que nous pouvons prouver efficacement au moyen de preuves à divulgation nulle de connaissance. Par exemple :

• Problème du voyageur de commerce — À partir d’une liste de villes et des distances entre chaque paire, trouver l’itinéraire le plus court qui visite chaque ville une fois et revient à la ville de départ. Ce problème a de nombreuses applications dans la logistique, la planification d’itinéraires, la production et la gestion de la chaîne logistique
• Problème du sac à dos — À partir d’un ensemble d’objets, déterminer le nombre de chaque objet à inclure dans une collection de façon à ce que le poids total soit inférieur ou égal à une limite donnée et que la valeur totale soit aussi élevée que possible. Ce problème est courant dans les domaines de la finance et de l’allocation des ressources
• Ordonnancement de tâches — À partir d’un ensemble de tâches ayant des durées et des échéances précises, les planifier sur une seule machine afin de minimiser la pénalité totale liée aux retards. Ce problème trouve de nombreuses applications en informatique, dans la production et dans la gestion de projet

De plus, le théorème de Cook-Levin établit que le problème de satisfaisabilité booléenne est NP-complet. Autrement dit, tout problème dont les variables peuvent être remplacées par les valeurs vrai ou faux de manière à ce que son évaluation finale soit vraie peut être transformé en problème NP-complet. Cela signifie que tout problème pouvant être réduit à une série de questions vraies ou fausses peut être prouvé efficacement au moyen de preuves à divulgation nulle de connaissance.

Propriétés d’une preuve à divulgation nulle de connaissance

Compte tenu de la complexité et de l’importance des problèmes NP-complets, il devient essentiel de pouvoir prouver leurs solutions de façon efficace et sécurisée. Les preuves à divulgation nulle de connaissance permettent de le faire sans compromettre la confidentialité des informations concernées. Goldwasser, Micali et Rackoff ont proposé que toutes les preuves à divulgation nulle de connaissance satisfassent les propriétés suivantes :

• Complétude — si le prouveur est honnête, il finira par convaincre le vérificateur
• Solidité — un prouveur malhonnête ne pourra jamais convaincre un vérificateur d’un énoncé faux
• Divulgation nulle de connaissance — l’interaction entre le prouveur et le vérificateur révèle uniquement si un énoncé est vrai, et rien d’autre

En tirant parti des propriétés robustes des preuves à divulgation nulle de connaissance, nous pouvons prouver des faits ou la connaissance de certaines informations dans divers contextes, tout en préservant la confidentialité et en garantissant l’exactitude. Dans les sections suivantes, nous verrons pourquoi ces qualités sont si précieuses pour les applications exigeant des niveaux élevés de sécurité et d’efficacité, comme les blockchains.

Interactif ou non interactif

Les preuves à divulgation nulle de connaissance suivent généralement la même structure en trois étapes :

• Le prouveur génère une solution au calcul (c’est-à-dire le témoin), puis envoie un engagement sur la réponse du témoin
• Le vérificateur répond avec une valeur de défi générée aléatoirement
• Le prouveur calcule la preuve finale à partir de l’engagement et du défi

Cette structure est intrinsèquement interactive : le prouveur affirme qu’il sait quelque chose, et le vérificateur le met continuellement au défi jusqu’à ce que la probabilité que le prouveur le trompe devienne négligeable. Ce fonctionnement n’est pas idéal pour la plupart des applications, car le prouveur doit recevoir une ou plusieurs réponses avant de pouvoir générer la preuve complète. Cette configuration présente par nature les difficultés suivantes :

• Le vérificateur pourrait s’entendre avec le prouveur pour lui permettre de falsifier des preuves
• Le vérificateur pourrait créer de fausses preuves
• Le vérificateur doit stocker ses valeurs secrètes quelque part, ce qui peut les exposer à des fuites ou à des attaques

L’heuristique de Fiat-Shamir est une technique qui permet de transformer une preuve de connaissance interactive en signature numérique. Un fait peut ainsi être prouvé publiquement sans révéler les informations sous-jacentes. L’idée est la suivante : au lieu que le vérificateur envoie une valeur de défi aléatoire au prouveur, ce dernier peut calculer lui-même cette signature numérique à l’aide d’une fonction aléatoire, comme une bonne fonction de hachage cryptographique. Ainsi, au lieu que le vérificateur examine le calcul à 500 endroits différents pour vérifier qu’ils sont tous corrects, le prouveur calcule une racine de Merkle du calcul, utilise cette racine pour choisir 500 indices de manière pseudo-aléatoire, puis fournit les 500 branches de Merkle correspondantes. L’idée essentielle est que le prouveur ne sait pas quelles branches il devra révéler avant d’avoir pris un engagement sur les données.

Le lecteur attentif remarquera peut-être un défaut rédhibitoire dans l’application d’un échantillonnage aléatoire au contrôle ponctuel des calculs : un calcul est intrinsèquement fragile. Un prouveur malveillant pourrait inverser un seul bit au milieu du calcul sans que le vérificateur ne le découvre jamais. Comment un vérificateur peut-il contrôler chaque partie du calcul sans les examiner une par une ? Avec des polynômes.

Toutefois, avant de parler des polynômes, nous devons comprendre un certain nombre de notions mathématiques.

Les mathématiques des preuves à divulgation nulle de connaissance

L’objectif n’est pas de proposer une introduction exhaustive aux domaines mathématiques suivants : chacune de ces sections pourrait faire l’objet d’un article entier. Il s’agit plutôt d’une brève introduction destinée à vous aider à comprendre les fondements mathématiques des preuves à divulgation nulle de connaissance et leur fonctionnement général.

Cet article vous présentera également la notation mathématique appropriée. Par exemple, dans la sous-section suivante consacrée à la théorie des ensembles, nous introduisons les symboles ∈, ∉ et ⊆. En définitive, ces symboles sont tous des substituts d’autres concepts. Les preuves à divulgation nulle de connaissance ne sont pas un sujet pour débutants. Par conséquent, la grande majorité des articles sur le sujet ne sont pas accessibles aux novices. Ils n’expliquent pas la signification de ces symboles et supposent que le lecteur comprend cette notation. Introduire cette notation dès maintenant est essentiel pour la rendre moins intimidante aux yeux de ceux qui souhaitent approfondir les preuves à divulgation nulle de connaissance. Essayez de ne pas vous perdre dans la notation. Persévérez : un jour viendra où vous regarderez ces symboles et verrez les concepts sous-jacents plutôt qu’une simple lettre grecque.

Théorie des ensembles

La théorie des ensembles est une branche des mathématiques qui étudie les collections d’objets. Un ensemble est une collection d’objets distincts. Ces objets sont appelés les éléments, ou membres, de l’ensemble. Prenons par exemple une collection de fruits :

Dans la notation ensembliste, les accolades servent à encadrer une collection d’éléments afin de représenter un ensemble. Nous savons ainsi que la pomme, l’orange, la poire et la banane font partie de l’ensemble, contrairement à un élément comme la « pomme de terre ». Le symbole ∈ indique l’appartenance à un ensemble et se lit « est un élément de ». De même, ∉ indique qu’un élément n’appartient pas à un ensemble donné. Nous pouvons donc écrire :

Cette expression se lit ainsi : « la pomme est un élément de l’ensemble Fruit et la pomme de terre n’est pas un élément de l’ensemble Fruit ».

Sous-ensembles

Nous pouvons également avoir des ensembles constitués d’autres ensembles. Un sous-ensemble est un ensemble qui ne contient que des éléments présents dans un autre ensemble. Par exemple, si nous avions :

Nous pouvons dire que l’ensemble Citrus est un sous-ensemble de l’ensemble plus vaste AllFruits. Nous pourrions également reprendre notre ensemble Fruit précédent et dire que Fruit est un sous-ensemble de l’ensemble plus vaste AllFruit. En notation ensembliste, cela s’écrit :

Pourquoi est-ce important ?

La théorie des ensembles est essentielle pour comprendre les notions d’intervalles et de contraintes. Dans les prochaines sections consacrées à la théorie des nombres et à l’arithmétique modulaire, nous étudierons l’idée selon laquelle les nombres appartiennent à un certain intervalle. Par exemple, nous pourrions avoir un ensemble de valeurs possibles pour une clé cryptographique :

Ici, K définit l’intervalle de toutes les clés possibles. Nous pouvons concevoir nos preuves à divulgation nulle de connaissance de manière à appliquer certaines contraintes à cet ensemble, afin que seules certaines valeurs soient valides. Par exemple, nous pourrions imposer que la clé soit un nombre compris entre 1 et 5. 

La théorie des ensembles fournit donc le langage, les outils et la notation fondamentaux permettant de définir et d’analyser les ensembles d’entrées, de sorties et d’états possibles dans les protocoles cryptographiques. Dans les preuves à divulgation nulle de connaissance, nous devons souvent prouver qu’un élément appartient à un ensemble ou à un intervalle donné sans révéler l’élément lui-même.

Je vous recommande de consulter Khan Academy, qui propose d’excellents exercices sur la notation ensembliste de base.

Théorie des nombres

La théorie des nombres est une branche des mathématiques qui étudie les entiers et les fonctions arithmétiques. Les entiers peuvent être définis comme un ensemble de nombres sans partie fractionnaire, comprenant les nombres positifs, les nombres négatifs et zéro. Nous pouvons définir plus formellement l’ensemble des entiers comme suit :

Ici, ℤ désigne l’ensemble des entiers, et les points de suspension indiquent que les entiers vont de l’infini négatif à l’infini positif. Par exemple, le nombre 12 est un entier, tout comme -1978649832794275.

Nombres rationnels

Les nombres rationnels sont des nombres que nous pouvons exprimer sous forme de fraction dont le dénominateur (c’est-à-dire le nombre situé sous la barre de fraction, un diviseur) n’est pas nul. Par exemple, $(\frac{1}{2}), 74, (\frac{2}{3})$ sont tous des nombres rationnels. Plus formellement, nous pouvons définir les nombres rationnels comme un ensemble de nombres pouvant être exprimés sous la forme d’une fraction pq, où p est le numérateur, q le dénominateur et q est différent de 0. Le symbole ℚ désigne les nombres rationnels. En notation ensembliste, nous écririons :‍

‍Cette expression peut sembler intimidante au premier abord, mais elle décrit exactement la phrase précédente. Ce jargon mathématique à l’apparence étrange se lit ainsi : « Q est l’ensemble de toutes les fractions p sur q, où p et q sont des entiers et où q est différent de zéro ». 

Nombres réels

Les nombres réels englobent à la fois les nombres rationnels et irrationnels. Les nombres irrationnels sont ceux qui ne peuvent pas être exprimés sous la forme d’une fraction simple et dont le développement décimal est infini et non périodique. Par exemple, pi (c’est-à-dire π) et $\sqrt{2}$ (c’est-à-dire 1.4.1421…) sont des nombres irrationnels. Nous laisserons de côté la notation ensembliste pour le moment, mais retenez que les nombres réels sont désignés par le symbole ℝ.

Pourquoi est-ce important ?

La théorie des nombres est étroitement liée à la théorie des ensembles, car elle étudie des ensembles précis de nombres, comme les nombres rationnels. Ces ensembles servent souvent à définir des intervalles et des contraintes dans les problèmes mathématiques et cryptographiques. 

Nous pouvons également constater les liens entre la théorie des nombres et la théorie des ensembles. Par exemple, l’ensemble de tous les entiers ℤ est un sous-ensemble des nombres rationnels ℚ. Cela apparaît clairement dans la définition des nombres réels en notation ensembliste ci-dessus, lorsque nous précisons que le numérateur et le dénominateur sont des entiers.

Arithmétique modulaire

L’arithmétique modulaire, également appelée arithmétique de l’horloge, est un système d’opérations numériques sur les entiers dans lequel les nombres « reviennent au début » après avoir atteint une valeur précise, appelée module. Au lieu de travailler avec un ensemble infini de nombres, nous utilisons les n premiers nombres positifs.

Horloges

Prenons une horloge analogique (je déteste devoir préciser, à notre époque, qu’elle possède des aiguilles et n’est pas numérique) affichant les nombres de 1 à 12. S’il est 11 heures et que nous voulons savoir quelle heure il sera dans deux heures, nous n’obtenons pas 13 heures. Nous revenons plutôt à 1 heure. Cela peut s’écrire $11 + 2 \equiv 1 \pmod{12}$ . L’expression mathématique correcte serait ici $13 \bmod 12 = 1$. Les développeurs connaissent probablement l’utilisation de l’opération modulo sous la forme $13 \% 12 = 1$.

Opération modulo

Lorsque nous écrivons n mod k, nous cherchons le reste de la division de n par k. C’est ce que l’on appelle l’opération modulo. Par exemple :

• 25 mod 3 signifie diviser 25 par 3, ce qui donne un reste de 1, car $25 = 8 \times 3 + 1$
• 15 mod 4 signifie diviser 15 par 4, ce qui donne un reste de 3, car $15 = 3 \times 4 + 3$

En arithmétique modulaire, le reste est toujours positif ou nul.

Pourquoi est-ce important ?

Comprendre l’arithmétique modulaire est essentiel, car elle permet de mieux saisir le comportement des nombres soumis à des contraintes, ce qui est précieux en cryptographie. L’arithmétique modulaire constitue la base de nombreux algorithmes cryptographiques et s’utilise dans toute l’informatique, l’ingénierie et les domaines qui exigent de manipuler et de chiffrer des données de manière sécurisée.

Prenons le calcul x + y = z. Imaginons que nous travaillions dans un corps fini défini par un nombre premier p = 17 (nous aborderons ce sujet très bientôt. Pour l’instant, considérez-le comme l’ensemble de tous les entiers de 0 à 16 qui revient à 0 après 17). Dans ce corps, le calcul serait (x + y) mod p = z. Si x = 12 et y = 15, le calcul serait :‍

L’utilisation de l’arithmétique modulaire nous permet ici d’effectuer des calculs dans un intervalle de valeurs gérable, défini par le nombre premier p. C’est particulièrement important, car l’espace disponible sur les ordinateurs et les processeurs est limité. Nous travaillons donc généralement avec des entiers de taille fixe comme u32 ou u64. L’arithmétique modulaire garantit que nos valeurs restent dans ces limites. De plus, l’utilisation de nombres premiers ajoute un niveau de complexité. Cela est essentiel d’un point de vue cryptographique, car cette approche renforce la sécurité et rend certaines propriétés mathématiques plus prévisibles et fiables.

Par exemple, l’arithmétique modulaire est utilisée dans les zk-SNARKs pour garantir que les valeurs calculées restent dans des limites précises et gérables. Elle permet également de créer des circuits arithmétiques sur un ensemble de nombres donné. Nous pouvons ainsi exprimer des calculs tout en garantissant qu’ils peuvent être vérifiés efficacement. Ici, le prouveur devrait démontrer qu’il a effectué ce calcul sans révéler les valeurs de x, y et z.

Je vous recommande vivement de consulter la série de problèmes d’Art of Problem Solving et les exercices d’arithmétique modulaire de Joseph Zoller pour vous entraîner davantage à résoudre des problèmes d’arithmétique modulaire. 

Théorie des groupes

La théorie des groupes est une branche des mathématiques qui étudie les structures algébriques appelées groupes. Un groupe est un ensemble d’éléments muni d’une opération qui satisfait les conditions suivantes, appelées axiomes de groupe :

• Stabilité — Le résultat de tout calcul arithmétique est un autre élément de l’ensemble
• Associativité — Lorsque la même opération porte sur trois éléments ou plus, la manière de les regrouper ne change pas le résultat
• Élément neutre — Il existe un élément avec lequel vous pouvez effectuer une opération sur n’importe quel autre élément sans modifier la valeur de ce dernier
• Élément inverse — Pour chaque élément, il en existe un autre avec lequel une opération produit l’élément neutre

Formellement, ces axiomes sont définis comme suit :

• Stabilité — Si a et b appartiennent au groupe, alors le résultat de l’opération (souvent notée $a \times b$, $ab$, $a \circ b$, ou $ab$) appartient également au groupe. Formellement, nous pouvons écrire $\forall a, b \in G \mid a \circ b \in G$. Cette expression se lit ainsi : « pour toutes les valeurs des éléments a et b de l’ensemble G, le résultat de l’opération entre a et b appartient à G »
• Associativité — Si a, b et c appartiennent au groupe, alors (ab)c = a(cb). Formellement, nous pouvons écrire $\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$. Cette expression se lit ainsi : « pour toutes les valeurs des éléments a, b et c de l’ensemble G, l’opération entre a et b, suivie de c, est égale à l’opération entre a et le résultat de l’opération entre b et c »
• Élément neutre — Il existe un élément e dans le groupe tel que, pour chaque élément a du groupe, l’opération $e \circ a = a \circ e = a$ est vérifiée. Formellement, nous écririons $\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$. Cette expression se lit ainsi : « il existe un élément e dans l’ensemble G tel que, pour chaque élément a de l’ensemble G, l’opération de e suivie de a est égale à l’opération de a suivie de e, elle-même égale à a »
• Élément inverse — Pour chaque élément a du groupe, il existe un élément b dans le groupe tel que $a \circ b = b \circ a = e$, où e est l’élément neutre. Formellement, nous écririons $\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$. Cette expression se lit ainsi : « pour toutes les valeurs des éléments a de l’ensemble G, il existe un élément b dans l’ensemble G tel que l’opération de a suivie de b est égale à l’opération de b suivie de a, elle-même égale à l’élément neutre »

Un exemple permet de rendre tout ce jargon mathématique plus accessible. Prenons l’ensemble des entiers muni de l’addition. Nous pouvons dire que cet ensemble forme un groupe, car il satisfait les quatre axiomes de groupe :

• Stabilité — L’addition de deux entiers produit un autre entier
• Associativité — $(5 + 4) + 3 = 5 + (4 + 3)$
• Élément neutre — Le nombre zéro est considéré comme l’élément neutre, car l’ajout de zéro à un entier ne modifie pas sa valeur. Par exemple, $7 + 0 = 0 + 7 = 7$
• Élément inverse — L’inverse de tout entier est son opposé, car leur addition produit l’élément neutre. Par exemple, $5 + (-5) = 0$. Nous pouvons généraliser cette expression en $n + (-n) = 0$

Nous pouvons également passer à un exemple plus difficile, comme l’ensemble des nombres rationnels non nuls $\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$ muni de la multiplication. Celui-ci forme également un groupe :

• Stabilité — La multiplication de deux nombres rationnels non nuls produit un nombre rationnel non nul
• Associativité — $ab \times cd \times ef = ab \times (cd \times ef)$
• Élément neutre — Le nombre 1 est considéré comme l’élément neutre, car la multiplication d’un nombre rationnel non nul par un ne modifie pas sa valeur. Par exemple, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Élément inverse — L’inverse de tout nombre rationnel non nul est son réciproque (c’est-à-dire que le numérateur et le dénominateur sont permutés), car leur produit est égal à 1, l’élément neutre. Par exemple, $\frac{3}{5} \times \frac{5}{3} = 1$

Sous-groupes

Un sous-groupe est un groupe à l’intérieur d’un autre groupe. Pour dire que le sous-groupe H du groupe G est un sous-ensemble de G, les axiomes de groupe suivants doivent être satisfaits :

• Stabilité — Si a et b appartiennent à H, le résultat de l’opération entre les deux doit également appartenir à H
• Associativité — Cet axiome est hérité du groupe plus vaste G 
• Élément neutre — L’élément neutre de G doit également appartenir à H 
• Élément inverse — Pour chaque élément a de H, il doit exister un élément b appartenant également à H tel que ab et ba soient tous deux égaux à l’élément neutre

L’exemple classique est celui de l’ensemble des entiers pairs muni de l’addition, qui constitue un sous-groupe de l’ensemble des entiers muni de l’addition :

• Stabilité — L’addition de deux entiers pairs produit un autre entier pair
• Associativité — Cet axiome est hérité des entiers. Par exemple, $2 + (4 + 6) = (2 + 4) + 6$
• Élément neutre — Le nombre zéro est considéré comme l’élément neutre, car l’ajout de zéro à n’importe quel entier pair ne modifie pas sa valeur. Zéro appartient également à l’ensemble des entiers
• Élément inverse — L’inverse de tout nombre pair est également un nombre pair. Par exemple, l’inverse de 4 est -4, car $4 + (-4) = 0$, qui est l’élément neutre

Nous pouvons appliquer ce raisonnement à un exemple plus difficile. Prenons l’ensemble de tous les nombres rationnels non nuls (c’est-à-dire ℚ*) muni de la multiplication. Nous pouvons prouver que ℚ* est un sous-groupe de l’ensemble des nombres réels non nuls (c’est-à-dire ℝ*) muni de la multiplication :

• Stabilité — Si a et b sont des nombres rationnels non nuls, leur produit ab est également un nombre non nul. Par exemple, $\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$, qui est un nombre rationnel non nul
• Associativité — La multiplication des nombres rationnels est associative. Par exemple, $(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$
• Élément neutre — Le nombre 1 est considéré comme l’élément neutre, car la multiplication de tout nombre rationnel non nul par 1 ne le modifie pas. Par exemple, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Élément inverse — Tout nombre rationnel non nul $a = \frac{p}{q}$ possède un inverse multiplicatif $a^{-1} = \frac{q}{p}$, qui est également un nombre rationnel non nul et dont le produit avec le nombre initial est égal à l’élément neutre. Par exemple, soit a = $\frac{2}{3}$. Son inverse est $\frac{3}{2}$, car $\frac{2}{3} \times \frac{3}{2} = 1$

Puisque ℚ* satisfait tous les axiomes de groupe, il forme un groupe. De plus, comme ℚ* est un sous-ensemble de ℝ* et en hérite les propriétés, nous pouvons affirmer que ℚ* est un sous-groupe de ℝ*.

Pourquoi est-ce important ?

Les groupes constituent le fondement de nombreux concepts et structures mathématiques et cryptographiques. Par exemple, les cryptosystèmes tels que RSA et la cryptographie sur courbes elliptiques reposent largement sur les propriétés des groupes et leurs opérations. Comprendre les sous-groupes permet de mieux saisir la structure des groupes plus vastes en étudiant leurs sous-ensembles plus petits et plus faciles à manipuler. Les groupes fournissent un cadre élémentaire pour comprendre la symétrie, les opérations et les transformations, qui sera essentiel lorsque nous aborderons les corps dans la section suivante.

Corps

Un corps est un ensemble d’éléments qui satisfait les axiomes de corps pour l’addition et la multiplication et constitue une algèbre à division commutative (c’est-à-dire que la division, sauf par zéro, est toujours possible). Les axiomes de corps sont généralement présentés par paires additives et multiplicatives :

• Addition
  • Associativité : $(a + b) + c = a + (b + c)$
  • Commutativité : $a + b = b + a$
  • Distributivité : $a(b + c) = ab + ac$
  • Élément neutre : $a + 0 = 0 + a = a$
  • Élément inverse : $a + (-a) = 0$
• Multiplication
  • Associativité : $(ab)c = a(bc)$
  • Commutativité : $ab = ba$
  • Distributivité : $(a + b)c = ac + bc$
  • Élément neutre : $(a + b)c = ac + bc$
  • Élément inverse : $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

Corps finis et générateurs

Un corps fini est un corps dont l’ensemble d’éléments est limité. Les corps finis sont également appelés corps de Galois. Le nombre d’éléments est appelé l’ordre, ou le cardinal, du corps. Ce nombre est toujours une puissance d’un nombre premier. L’avantage des corps finis est que toute opération arithmétique effectuée sur leurs éléments produit un résultat qui appartient encore au corps. En effet, toutes les opérations sont effectuées modulo l’ordre du corps, ce qui fait revenir les valeurs au début.

Chaque corps fini possède un générateur. Par exponentiation, celui-ci peut générer tous les éléments du corps. Autrement dit, nous pouvons prendre le générateur et incrémenter son exposant d’une unité jusqu’à avoir obtenu tous les éléments du corps. Un générateur est donc un élément du corps qui, grâce à ses puissances, peut produire tous les éléments non nuls de ce corps.

Imaginons par exemple que nous prenions l’ensemble des entiers modulo p = 7 et le corps $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$. Si nous voulons trouver le générateur g de $\mathbb{Z}_7^*$ (c’est-à-dire le groupe multiplicatif des éléments non nuls de $\mathbb{Z}_7$, nous devons nous assurer que g1, g2, g3, etc. peuvent générer tous les éléments non nuls du corps.

Vérifions si 3 est un générateur :

Les puissances de 3 génèrent tous les éléments non nuls de $\mathbb{Z}_7$. Par conséquent, 3 est un générateur du groupe multiplicatif $\mathbb{Z}_7^*$.

Pourquoi est-ce important ?

La cryptographie est une science qui traite d’ensembles finis. Cette notion constitue un fondement indispensable pour aborder des sujets tels que le problème du logarithme discret, le chiffrement, l’échange de clés Diffie-Hellman et les courbes elliptiques. Les générateurs permettent d’effectuer des opérations arithmétiques sur des polynômes chiffrés sans les déchiffrer (c’est-à-dire le chiffrement homomorphe). Autrement dit, nous pouvons calculer des données chiffrées tout en préservant la confidentialité des valeurs sous-jacentes. Il est essentiel de comprendre cette section pour saisir l’aspect « divulgation nulle de connaissance » de ces preuves.

Je vous recommande de consulter Bill’s Security Site, qui propose un exemple interactif de génération de corps finis avec des paramètres précis, ainsi que la théorie sous-jacente en Python. 

Fonctions

Une fonction est une expression, une règle ou une loi qui définit une relation entre deux variables : la variable indépendante et la variable dépendante. Ces deux variables sont souvent décrites respectivement comme la cause et l’effet. Cette relation est généralement notée y = f(x), qui se lit « f de x ». À chaque valeur de x correspond une valeur unique de y. Ainsi, f(x) ne peut pas avoir plusieurs valeurs pour un même x.

Les fonctions peuvent être injectives ou plusieurs-à-un, ce que l’on décrit souvent en termes de cardinalité. Cela signifie qu’une valeur x peut correspondre à une valeur y unique, ou que plusieurs valeurs x peuvent correspondre à la même valeur y

Imaginons une droite définie par $y = 3x + 4$. Il s’agit d’une fonction linéaire dans laquelle l’insertion d’une valeur de x renvoie une valeur correspondante de y. Ensemble, ces deux valeurs forment un point sur la droite. Par exemple, nous pouvons réécrire l’équation sous la forme $f(x) = 3x + 4$ et l’évaluer lorsque x = 1, ce qui donne $f(1) = 7$. Les fonctions peuvent également comporter plusieurs variables. Prenons par exemple la formule de l’aire d’un triangle : $A = \frac{bh}{2}$. Ici, A (c’est-à-dire l’aire) est défini comme une fonction de b (c’est-à-dire la base) et de h (c’est-à-dire la hauteur).

Domaine de définition et image

Le domaine de définition d’une fonction est l’ensemble de toutes les valeurs d’entrée possibles (c’est-à-dire les variables indépendantes) que la fonction peut accepter. L’image de la fonction est l’ensemble de toutes les valeurs de sortie possibles (c’est-à-dire les variables dépendantes) que la fonction peut produire.

Pour la fonction $y = 2x + 2$ :

• Le domaine de définition comprend tous les nombres réels, car n’importe quel nombre de l’infini négatif à l’infini positif convient. Par exemple :
  • Si x = 2.5, alors $y = 2(2.5) + 2 = 7$ 
  • Si x = -9234525, alors $y = 2(-9234525) + 2 = -18469048$
• L’image comprend également tous les nombres réels, car n’importe quel nombre de l’infini négatif à l’infini positif peut être produit. Par exemple :
  • Pour obtenir y = -50, nous résolvons -50 = 2x + 2, ce qui donne x = -26. 
  • Pour obtenir y = 0, nous résolvons 0 = 2x + 2, ce qui donne x = 0

Pourquoi est-ce important ?

Les fonctions sont essentielles pour comprendre les polynômes. Ceux-ci sont des fonctions particulières qui comportent des variables élevées à différentes puissances ainsi que leurs coefficients. Les polynômes sont des structures algébriques fondamentales qui servent de base à la construction de protocoles cryptographiques. Dans la section suivante, nous les étudierons en détail et examinerons leurs propriétés ainsi que leur importance dans les preuves à divulgation nulle de connaissance.

Je vous recommande de consulter Paul’s Online Notes et de résoudre les exercices proposés afin de mieux comprendre les fonctions.

Polynômes

Un polynôme est une fonction composée de plusieurs variables et coefficients qui ne fait intervenir que l’addition, la soustraction, la multiplication et l’exponentiation des variables par des entiers positifs ou nuls. Les polynômes s’écrivent généralement sous la forme suivante :‍

Où $a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ sont des coefficients et x est la variable. La plus grande puissance de la variable x ayant un coefficient non nul est appelée le degré du polynôme.

Les polynômes peuvent être univariés, lorsqu’ils comportent une seule variable (comme dans la forme ci-dessus), ou multivariés, lorsqu’ils comportent plusieurs variables (par exemple, $P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$. Sum-Check est un exemple de protocole qui utilise des polynômes multivariés. Toutefois, la plupart du temps, les preuves à divulgation nulle de connaissance ne nécessitent qu’une seule variable.

Les noms couramment attribués aux polynômes selon leur degré sont les suivants :

• Degré 0 — Constante non nulle (par exemple, $P(x) = 6$)
• Degré 1 — Linéaire (par exemple, $P(x) = 2x - 7$)
• Degré 2 — Quadratique (par exemple, $P(x) = 8x^2 - 3x + 1$)
• Degré 3 — Cubique (par exemple, $P(x) = 3x^3 - 4x$)

Si deux polynômes distincts sont de degré inférieur ou égal à $d$, ils ne peuvent se couper en plus de $d$ points (par exemple, si nous égalons une fonction linéaire à une fonction cubique, elles peuvent se couper jusqu’à trois fois). Cette propriété découle de la manière dont nous trouvons les points communs. Pour déterminer où deux polynômes se coupent, nous les égalons. Dans la sous-section suivante, nous nous entraînerons à trouver les racines d’un polynôme, c’est-à-dire les points où un polynôme donné coupe l’axe des x. Le théorème fondamental de l’algèbre établit qu’un polynôme de degré $d$ peut avoir au maximum $d$ solutions et, par conséquent, au maximum $d$ points communs.

Racines des polynômes 

Les racines, ou zéros, d’un polynôme sont les valeurs de x pour lesquelles le polynôme est égal à zéro. Autrement dit, si $P(x)$ est un polynôme, une racine $r$ est une solution de l’équation $P(r) = 0$. Pour trouver les racines, nous devons savoir factoriser les polynômes. La factorisation consiste à déterminer ce qu’il faut multiplier pour obtenir une quantité donnée. Par exemple, il existe plusieurs façons de factoriser 12 :

Une méthode courante de factorisation consiste à décomposer entièrement le nombre en facteurs premiers positifs. Lors d’une factorisation, il est toujours préférable de commencer par le plus grand commun diviseur (PGCD) de tous les termes. Par exemple :

Dans l’exemple ci-dessus, les deux termes (c’est-à-dire 6x et 3) sont divisibles par 3 ; leur PGCD est donc 3. Les facteurs sont ainsi 3 et $2x + 1$. Nous appliquons la distributivité en sens inverse : $3 \times 2x$ et $3 \times 1$. Trouver les racines revient à résoudre l’équation pour x lorsque $P(x) = 0$.

La factorisation est simple pour les polynômes à deux termes. Elle l’est encore davantage à partir d’un graphique, puisque les racines correspondent aux points où le polynôme coupe l’axe des x. Cependant, un degré supérieur ou égal à trois peut compliquer le problème. Pour une explication plus approfondie, je vous recommande l’article Comment factoriser des polynômes. 

Il n’est pas indispensable de connaître toutes les subtilités de la factorisation des différents polynômes pour lire la suite de cet article. Ici, nous nous intéressons au cas où un polynôme est égalé à une autre valeur. Dans le cas présent, nous cherchons quand un polynôme est égal à zéro. Plus loin, nous chercherons quand un polynôme est égal à un autre ou quand la différence entre deux polynômes est identiquement nulle (c’est-à-dire que tous les coefficients sont nuls), ce qui implique de vérifier si un polynôme donné possède certaines racines.

Le lemme de Schwartz-Zippel 

Le lemme de Schwartz-Zippel est un outil probabiliste permettant de vérifier si une équation polynomiale est toujours vraie. Il évalue le polynôme en des points aléatoires et vérifie si le résultat est nul.

Imaginez une équation complexe faisant intervenir les variables $x_1, x_2, \ldots, x_n$. Si cette équation est un polynôme et non un simple assemblage aléatoire de termes, le lemme de Schwartz_Zippel nous aide à vérifier si elle est vraie pour toutes les valeurs possibles de ces variables.

Voici comment il fonctionne :

• Soit $P(x_1, x_2, \ldots, x_n)$ un polynôme de degré total d (c’est-à-dire la plus grande somme d’exposants parmi tous les termes)
• Choisissez un ensemble fini S dans le corps (comme si vous choisissiez un ensemble de nombres)
• Sélectionnez aléatoirement, dans l’ensemble S, une valeur pour chaque variable $x_1, x_2, \ldots, x_n$

Le lemme établit que la probabilité que P soit nul en ces points choisis aléatoirement est au plus égale à $\frac{d}{S}$. Autrement dit, si le polynôme n’est pas nul, il est très peu probable qu’il paraisse l’être par pur hasard. Cette propriété est particulièrement utile pour les preuves à divulgation nulle de connaissance, où nous devons vérifier efficacement des identités polynomiales.

Interpolation de Lagrange

L’interpolation de Lagrange est une méthode permettant de construire un polynôme qui passe par un ensemble donné de points. Le polynôme de Lagrange est le polynôme de plus petit degré passant par chacun des points donnés. Pour n points, il est possible de créer un polynôme de degré n-1 passant par tous les points. Par exemple, si vous avez deux points dans un plan, nous pouvons définir une droite qui les traverse. Si nous avons trois points dans un plan, nous pouvons définir un polynôme quadratique (c’est-à-dire $y = ax^2 + bx + c$) qui passe par tous ces points. Et ainsi de suite.

Pourquoi est-ce important ?

Un polynôme est un objet mathématique unique pouvant contenir une quantité illimitée d’informations — considérez un polynôme comme une liste d’entiers, et cela devient évident. Une seule équation entre des polynômes peut donc représenter un nombre illimité d’équations entre des nombres. Si une personne peut vérifier une équation donnée entre des polynômes, elle vérifie implicitement et simultanément toutes les équations possibles. C’est ainsi que nous protégeons les preuves non interactives contre les risques liés à un prouveur malveillant et que nous évitons de devoir nous fier à des contrôles ponctuels et aléatoires d’un calcul donné. 

Les polynômes possèdent également plusieurs propriétés qui les rendent utiles pour créer des preuves :

• Si nous disposons d’un nombre suffisant de points pour un polynôme donné, le polynôme entier peut être reconstruit
• Une petite modification de l’entrée d’un polynôme peut entraîner un changement important de sa sortie, ce qui facilite la détection des erreurs
• Les polynômes peuvent détecter et corriger les erreurs de calcul, tout comme les codes d’effacement rendent les données tolérantes aux pannes, ce qui est essentiel au fonctionnement de Turbine

Les preuves à divulgation nulle de connaissance servent à prouver certains calculs. Les polynômes sont extrêmement précieux dans ce domaine, car nous pouvons les concevoir avec des caractéristiques précises. Supposons que vous souhaitiez prouver un calcul ou un ensemble de points de données. Le moyen le plus simple consiste à l’encoder dans un polynôme, puis à exploiter les propriétés de ce dernier pour créer une preuve :

• Encodez les données dans un polynôme $P(x)$ de sorte que l’évaluation de $P(x)$ en certains points produise les données d’origine ou le résultat d’un calcul donné
• Pour vous assurer que le polynôme respecte les critères donnés (par exemple, que toutes les valeurs se trouvent dans un intervalle), créez un polynôme de contrainte $C(x)$. Par exemple, $C(x) = (P(x) - 0)(P(x) - 1)$ garantit que $P(x)$ vaut 0 ou 1
• Transformez le problème afin de prouver que $P(x)$ satisfait certaines conditions pour votre jeu de données ou votre calcul
• Créez un polynôme connu $H(x)$, multiple de $P(x)$, qui encode ces conditions
• Le prouveur engage les valeurs de $P(x)$ et de tous les polynômes associés en créant un arbre de Merkle à partir des évaluations, puis envoie le hachage racine au vérificateur
• Le vérificateur sélectionne aléatoirement quelques points et demande au prouveur de fournir les valeurs de $P(x)$ et de $C(x)$ en ces points
• Le vérificateur compare les valeurs fournies au hachage racine engagé et aux relations polynomiales attendues

La taille du polynôme importe peu : puisque nous utilisons l’engagement polynomial, nous pouvons vérifier rapidement des équations entre polynômes. Il s’agit d’une méthode très concise et efficace pour créer des preuves. Toute erreur est amplifiée et, grâce à des techniques telles que l’heuristique de Fiat-Shamir, ces preuves peuvent devenir non interactives afin que tout le monde puisse les vérifier sans interaction supplémentaire. 

Pour approfondir votre compréhension, je vous recommande les exercices suivants :

• Exercices sur les polynômes
• Exercices sur la recherche des zéros de polynômes
• Factorisation des polynômes : problèmes très difficiles avec solutions

Khan Academy propose également une unité complète sur les expressions, les équations et les fonctions polynomiales.

Pour mieux comprendre les engagements polynomiaux, nous devons maintenant explorer la cryptographie qui sous-tend les preuves à divulgation nulle de connaissance.

La cryptographie derrière les preuves à divulgation nulle de connaissance

Explorons le chiffrement symétrique et le chiffrement asymétrique.

Chiffrement symétrique

Le chiffrement symétrique est une technique qui utilise la même clé pour chiffrer le texte en clair et déchiffrer le texte chiffré. Cette clé est souvent appelée clé secrète ou clé privée, car l’utilisation d’une seule clé exige qu’elle reste secrète. Cela signifie toutefois que les deux parties doivent se communiquer la clé secrète avant de pouvoir échanger de manière sécurisée. La gestion et la distribution sécurisées de la clé secrète peuvent donc être difficiles et exposées à des fuites si elles ne sont pas effectuées correctement. Malgré cet inconvénient, le chiffrement symétrique est rapide, efficace et nécessite moins de puissance de calcul et de mémoire que les autres systèmes de chiffrement.

Les algorithmes de chiffrement symétrique courants comprennent :

Advanced Encryption Standard (AES)

L’Advanced Encryption Standard (AES) est une variante du chiffrement par blocs Rijndael, largement utilisée dans le monde entier pour sécuriser les données. Il prend en charge des tailles de clé de 128, 192 et 256 bits.

ChaCha20

ChaCha20 est un chiffrement par flot moderne et efficace développé par Daniel J. Bernstein. Il s’agit d’une variante du chiffrement par flot Salsa20 qui exploite les opérations d’addition-rotation-XOR (ARX). Il associe une clé de 256 bits, un nonce de 64 bits et un compteur de 64 bits à un bloc de 512 bits du flot de clés, ce qui permet à un utilisateur d’atteindre efficacement n’importe quelle position du flot de clés en temps constant.

Bien que le chiffrement symétrique soit robuste et efficace, il nécessite une méthode sécurisée d’échange des clés. L’une de ces méthodes est l’échange de clés Diffie-Hellman, qui permet à deux parties de partager une clé secrète en toute sécurité sur un canal non sécurisé. Cette méthode repose toutefois sur les principes du chiffrement asymétrique, que nous aborderons dans la section suivante.

Chiffrement asymétrique

Le chiffrement asymétrique, également appelé chiffrement à clé publique, utilise une paire de clés liées (c’est-à-dire une clé publique et une clé privée) pour chiffrer et déchiffrer des informations. La clé publique est partagée ouvertement, tandis que la clé privée reste secrète. Lorsqu’un expéditeur souhaite chiffrer un message, il utilise la clé publique du destinataire. À la réception, le destinataire déchiffre le message avec la clé privée correspondante. Les données chiffrées avec la clé publique ne peuvent être déchiffrées qu’avec la clé privée. Le chiffrement asymétrique permet ainsi de communiquer de manière sécurisée sur des canaux non sécurisés, puisque la clé de déchiffrement n’est jamais partagée.

Le chiffrement asymétrique offre un niveau élevé de sécurité, car la clé privée n’est jamais partagée. Il simplifie également la distribution des clés, puisque la clé publique peut être communiquée ouvertement, et permet d’utiliser des signatures numériques. Il exige toutefois davantage de ressources de calcul et s’avère plus lent que le chiffrement symétrique. La gestion des paires de clés peut également devenir complexe, en particulier dans les systèmes comptant de nombreux utilisateurs et où les paires de clés ne sont pas intuitives. 

Les algorithmes de chiffrement asymétrique courants comprennent :

• Rivest-Shamir-Adleman (RSA) — l’un des cryptosystèmes à clé publique les plus anciens et les plus utilisés pour transmettre des données en toute sécurité. Développé dans les années 1970, il repose sur la difficulté pratique de factoriser le produit de deux grands nombres premiers
• Cryptographie sur les courbes elliptiques (ECC) — une approche de la cryptographie à clé publique fondée sur la structure algébrique des courbes elliptiques sur des corps finis. Elle offre une sécurité comparable à RSA avec des clés plus petites, ce qui accélère les calculs et réduit les besoins de stockage. Solana utilise la courbe elliptique Ed25519 pour générer ses paires de clés

Signatures numériques

Les signatures numériques sont un aspect essentiel de la cryptographie à clé publique. Elles permettent de vérifier l’authenticité et l’intégrité d’un message, d’un logiciel ou d’un document numérique. Une signature numérique est créée avec la clé privée de l’expéditeur et peut être vérifiée par toute personne ayant accès à la clé publique correspondante. Cela garantit que le message a été envoyé par un expéditeur légitime et n’a pas été modifié.

Les algorithmes couramment utilisés pour les signatures numériques comprennent :

• Digital Signature Algorithm (DSA) — une approche fondée sur l’exponentiation modulaire (c’est-à-dire une exponentiation effectuée modulo un nombre) et le problème du logarithme discret
• Elliptic Curve Digital Signature Algorithm (ECDSA) — une variante de DSA qui utilise la cryptographie sur les courbes elliptiques afin d’offrir un niveau de sécurité supérieur avec des clés plus petites

Problème du logarithme discret

Le problème du logarithme discret consiste à trouver l’exposant k dans l’équation $g^k \equiv h \pmod{p}$, où :

• g est une base connue (c’est-à-dire un générateur)
• h est un résultat connu (c’est-à-dire un élément du groupe)
• p est un nombre premier (c’est-à-dire l’ordre du groupe)
• k est l’exposant inconnu (c’est-à-dire le logarithme discret de h en base g)

Autrement dit, si vous connaissez les valeurs de g, h et p, le problème du logarithme discret consiste à trouver k. Par exemple, pour l’équation $2^k \equiv 9 \pmod{23}$, l’objectif est de trouver k.

Le problème du logarithme discret est considéré comme difficile à résoudre efficacement, en particulier pour les grands nombres. Cette difficulté constitue le fondement de la sécurité de plusieurs systèmes cryptographiques, notamment Solana, le chiffrement ElGamal, les algorithmes de signature numérique (c’est-à-dire DSA et ECDSA) et l’échange de clés Diffie-Hellman

Échange de clés Diffie-Hellman

L’échange de clés Diffie-Hellman est une méthode permettant d’échanger des clés cryptographiques de manière sécurisée sur un canal public.  Son implémentation d’origine, qui est aussi la plus simple (Diffie-Hellman sur corps fini), fonctionne comme suit :

• Alice et Bob conviennent publiquement de deux nombres : un grand nombre premier p (c’est-à-dire le module) et une base g (c’est-à-dire le générateur), qui est une racine primitive modulo p 
• Alice choisit un entier secret a, puis envoie à Bob $A \equiv g^a \pmod{p}$
• Bob choisit un entier secret b, puis envoie à Alice $B \equiv g^b \pmod{p}$
• Alice calcule $s \equiv B^a \pmod{p}$ 
• Bob calcule $s = A^b \pmod{p}$ 

Alice et Bob possèdent désormais la même valeur secrète. En effet, les deux calculs produisent le même secret s, car :

Ce secret partagé s peut ensuite servir de clé de chiffrement symétrique, permettant à Alice et Bob de communiquer de manière sécurisée. La sécurité de l’échange de clés Diffie-Hellman repose sur la difficulté du problème du logarithme discret. Sans connaître les valeurs secrètes a et b, il est impossible en pratique pour une personne qui intercepte les communications de déduire le secret partagé. C’est ce que l’on appelle une fonction à sens unique : elle est relativement facile à calculer, mais extrêmement difficile à inverser.

Bien que l’échange de clés Diffie-Helman sur corps fini soit sécurisé et largement utilisé, il exige de grandes tailles de clé. Par exemple, si Alice et Bob choisissaient publiquement un module de 23, il serait bien plus facile de le casser puisqu’il n’existe que 23 résultats possibles pour n mod 23. Cette méthode peut donc être gourmande en calcul et moins efficace. Pour résoudre ces problèmes, la cryptographie sur les courbes elliptiques (ECC) offre une solution plus efficace, car elle assure le même niveau de sécurité avec des clés nettement plus petites et des calculs plus rapides.

Courbes elliptiques

Une courbe elliptique est définie par l’équation $y^2 = x^3 + ax + b$, où a et b sont des constantes. La cryptographie sur les courbes elliptiques consiste simplement à travailler avec des points situés sur une courbe elliptique donnée. Ces courbes possèdent plusieurs propriétés uniques qui les rendent utiles en cryptographie. Par exemple :

• Addition de points — Étant donnés deux points, P et Q, sur une courbe elliptique donnée, leur somme R = P + Q sera également un point de la courbe. L’article de Preethi Kasireddy, Un guide indolore de la cryptographie pour les preuves à divulgation nulle de connaissance, explique clairement comment additionner des points sur une courbe elliptique
• Multiplication scalaire — Étant donné un point P sur une courbe elliptique donnée et un entier k, la multiplication scalaire consiste à additionner le point P à lui-même k fois. Cela produit un autre point (c’est-à-dire kP) sur la courbe. Cette opération sert à générer les clés publiques à partir des clés privées
• Problème du logarithme discret — Le problème du logarithme discret sur les courbes elliptiques est beaucoup plus difficile à résoudre que son équivalent sur les entiers. Étant donnés les points P et q = kP, il est impossible en pratique de déterminer k si les paramètres de la courbe sont correctement choisis. Les courbes elliptiques offrent donc la même sécurité que les systèmes traditionnels avec des clés bien plus petites, ce qui les rend plus efficaces

Grâce à nos nouvelles connaissances en théorie des groupes, nous pouvons affirmer que certaines équations de courbes elliptiques satisfont les axiomes d’un groupe :

• Deux points quelconques peuvent être additionnés pour obtenir un troisième point
• L’ordre dans lequel les deux points sont additionnés n’a pas d’importance
• S’il faut additionner plus de deux points, l’ordre dans lequel ils sont additionnés n’a pas d’importance
• Il existe un élément neutre (c’est-à-dire que l’ajout de zéro à n’importe quel point de la courbe donne le même point)

Je vous recommande vivement de lire Cryptographie sur les courbes elliptiques de Georgie Bumpus pour explorer plus en détail cette structure de groupe. 

Les courbes elliptiques offrent le même niveau de sécurité que d’autres cryptosystèmes traditionnels, comme RSA, mais avec des clés beaucoup plus petites. Par exemple, une clé ECC de 256 bits offre une sécurité comparable à celle d’une clé RSA de 3 072 bits. Cela présente plusieurs avantages :

• Des clés plus petites accélèrent le chiffrement et le déchiffrement
• Les clés et les certificats nécessitent moins d’espace
• Des clés plus petites réduisent la quantité de données transmises, ce qui est avantageux dans les environnements à bande passante limitée, comme une blockchain

Courbes de Montgomery

Les courbes de Montgomery sont des courbes elliptiques définies par l’équation $By^2 = x^3 + Ax^2 + x$ sur un corps fini, où A et B sont des constantes, B est différent de zéro et A n’est égal ni à -2 ni à 2. Ces courbes sont particulières, car la multiplication sur les courbes elliptiques peut y être implémentée plus efficacement au moyen d’une échelle de Montgomery. 

Une échelle de Montgomery prend essentiellement un point P sur une courbe de Montgomery et un scalaire k, initialise deux points de l’infini jusqu’à P, puis traite chaque bit du scalaire k, du bit de poids fort au bit de poids faible. L’idée principale consiste à conserver deux points et à les mettre à jour avec une séquence constante d’opérations, indépendamment des bits du scalaire k.

Cette propriété est importante pour plusieurs raisons :

• Elle résiste aux attaques par canal auxiliaire, c’est-à-dire aux attaques fondées sur des informations supplémentaires recueillies en raison de l’implémentation ou de la conception d’un protocole ou d’un algorithme donné. C’est un terrier de lapin vraiment, vraiment technique que je vous recommande d’explorer. Ces attaques vont de la variation de la consommation électrique du matériel pendant les calculs aux fuites de rayonnement électromagnétique
• La coordonnée y n’est pas nécessaire, car la multiplication scalaire peut être effectuée uniquement à partir des coordonnées x
• Elle fonctionne en temps constant, ce qui signifie que la durée d’un calcul donné ne dépend pas de la valeur d’entrée

Les courbes de Montgomery sont largement utilisées dans les protocoles cryptographiques, notamment dans l’algorithme X25519 d’échange de clés, qui utilise la forme de Montgomery de la courbe Curve25519. Cet algorithme constitue le fondement des communications sécurisées modernes et est notamment implémenté dans des protocoles courants tels que TLS. 

Courbes d’Edwards

Les courbes d’Edwards sont un type de courbe elliptique défini par l’équation $x^2 + y^2 = 1 + d x^2 y^2$, où d est une constante non nulle différente de 1.  

Ces courbes sont importantes pour les raisons suivantes :

• Efficacité des opérations sur les points — L’addition de deux points sur une courbe d’Edwards est plus efficace que sur d’autres formes de courbes elliptiques. Les formules d’addition et de doublement de points sont plus simples et impliquent moins d’opérations sur le corps, ce qui accélère leur calcul
• Formule d’addition unifiée — Les courbes d’Edwards utilisent une formule d’addition unifiée, ce qui signifie que la même formule peut servir à l’addition et au doublement de points. Cela réduit le risque d’erreurs d’implémentation et renforce la sécurité
• Complétude — Pour certaines valeurs de d, les courbes d’Edwards sont complètes. La loi d’addition couvre alors toutes les entrées possibles, sans exception.
• Résistance aux attaques par canal auxiliaire — Comme les courbes de Montgomery, les courbes d’Edwards résistent aux attaques par canal auxiliaire grâce à leurs schémas d’opérations uniformes et prévisibles.

Une courbe d’Edwards largement utilisée est Edwards25519, définie par l’équation $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$. Cette courbe est connue pour l’efficacité de son arithmétique et ses clés de 256 bits. Son schéma de signature est implémenté dans divers protocoles et systèmes de sécurité, notamment Solana, OpenSSH et Tor. Monero utilise Edwards25519 comme base pour générer ses paires de clés.

Pourquoi est-ce important ?

Les courbes elliptiques jouent un rôle essentiel dans les preuves à divulgation nulle de connaissance en raison de leur efficacité et de leurs propriétés qui renforcent la sécurité. Remarque : leur utilisation permet de créer des preuves plus petites et plus rapides, ce qui est indispensable à toute implémentation pratique. Nous approfondirons ce point lorsque nous aborderons les développements liés à la divulgation nulle de connaissance, mais disposer de preuves petites et rapides est essentiel dans un environnement de calcul intensif soumis à diverses contraintes sur les comptes et les transactions. C’est ce qui rend les preuves à divulgation nulle de connaissance intéressantes pour créer des rollups : il devient possible de générer une preuve concise attestant que toutes les opérations sur une L2 sont valides, puis de la valider sur la L1.

En définitive, considérez les courbes elliptiques comme un substitut à l’arithmétique modulaire. Avec les courbes elliptiques, il est nettement plus difficile d’obtenir un point précis. Supposons que nous utilisions l’arithmétique modulaire traditionnelle avec $g^a \bmod n$, où g est un générateur, n un grand nombre premier et a la clé secrète. Comme nous l’avons vu avec le problème du logarithme discret, un très grand nombre premier est nécessaire pour protéger la clé secrète. Les courbes elliptiques offrent une solution plus efficace avec des clés plus petites, tout en assurant le même niveau de sécurité et de bien meilleures performances.

Aléa

Rien d’autre dans cet article n’aurait d’importance sans l’aléa, un aspect fondamental de la cryptographie. Comment un système pourrait-il être sécurisé si ses valeurs sont prévisibles et biaisées ? Il peut être difficile d’obtenir un véritable aléa, mais celui-ci est indispensable pour plusieurs raisons :

• Génération de clés — Les clés cryptographiques doivent être générées aléatoirement afin de garantir qu’elles sont imprévisibles et sécurisées
• Nonces et sels — Les nonces (c’est-à-dire des nombres utilisés une seule fois) et les sels (c’est-à-dire des valeurs aléatoires ajoutées aux données avant leur hachage) empêchent respectivement les attaques par rejeu et les attaques précalculées
• Protocoles sécurisés — L’aléa sert à garantir l’équité et la sécurité en évitant la prévisibilité et les schémas que des attaquants pourraient exploiter

La plupart des générateurs de nombres aléatoires ne parviennent pas à produire un nombre aléatoire vérifiable cryptographiquement. Ils restent donc vulnérables à la manipulation et leurs cas d’usage sont limités. Les fonctions aléatoires vérifiables résolvent toutefois ce problème.

Fonctions aléatoires vérifiables

Une fonction aléatoire vérifiable (VRF) est une primitive cryptographique qui produit une sortie aléatoire ainsi qu’une preuve attestant que cette sortie a été correctement générée à partir d’une entrée donnée. Une VRF doit être imprévisible : sa sortie doit être impossible à distinguer d’une valeur aléatoire pour toute personne qui ne connaît pas l’entrée secrète. Sa sécurité repose sur l’hypothèse RSA selon laquelle il est difficile de calculer $y = h^d \bmod n$ sans connaître l’exposant secret d, ainsi que sur la sécurité de la fonction de hachage H. 

Les principales étapes d’une VRF sont les suivantes :

• Génération de clés — L’utilisateur génère une paire de clés RSA : (e, n) comme clé publique et (d, n) comme clé privée. Dans la clé publique, e est l’exposant et n le module. Dans la clé privée, d est l’exposant secret
• Calcul — À partir d’une entrée x, l’utilisateur calcule la sortie VRF y et la preuve π. Il calcule d’abord le hachage h = H(x), où H est une fonction de hachage cryptographique. Il calcule ensuite $y = h^d \bmod n$, qui correspond à la signature RSA du hachage. Enfin, il calcule la preuve π = (h, y)
• Vérification — À partir de la clé publique (e, n), de l’entrée x, de la sortie y et de la preuve π = (h, y), n’importe qui peut vérifier l’exactitude de la sortie VRF en contrôlant que le hachage h est égal à $H(x)$ et que $y^e \equiv h \pmod{n}$ vérifie l’équation RSA‍

Les VRF sont souvent utilisées dans les protocoles de consensus qui exigent un aléa à la fois imprévisible et vérifiable. Des L1, notamment Algorand, Cardano, Internet Computer et Polkadot, utilisent des VRF dans leurs mécanismes de consensus afin de sélectionner aléatoirement les producteurs de blocs. Chainlink propose Chainlink VRF comme couche d’abstraction entre l’utilisateur et la blockchain afin de générer des valeurs probablement équitables et vérifiables. Pyth Entropy fournit également une source d’aléa fiable et sécurisée.

Cérémonies et configurations de confiance

Les cérémonies cryptographiques sont des protocoles ou des événements au cours desquels des calculs cryptographiques critiques sont effectués dans un environnement sécurisé et contrôlé. Il existe plusieurs types de cérémonies cryptographiques :

• Cérémonies de génération de clés — Elles consistent à générer des clés cryptographiques de façon à ce qu’aucune entité ne contrôle à elle seule le processus de génération
• Cérémonies de génération de paramètres — Elles consistent à créer des paramètres cryptographiques qui seront utilisés par plusieurs parties
• Cérémonies de calcul multipartite (MPC) — Elles impliquent plusieurs parties qui effectuent conjointement un calcul cryptographique afin qu’aucune d’entre elles ne puisse compromettre le processus à elle seule

Une cérémonie de configuration de confiance est un événement ou un processus spécial conçu pour générer l’ensemble de paramètres cryptographiques nécessaires à l’exécution d’un protocole cryptographique. Dans notre section consacrée aux preuves à divulgation nulle de connaissance interactives et non interactives, nous avons établi que la première étape d’une preuve consiste à faire convenir le prouveur et le vérificateur d’une valeur à utiliser. Lors d’une cérémonie de configuration de confiance, plusieurs participants fournissent de l’aléa afin qu’aucun d’entre eux ne contrôle à lui seul le processus. Chaque participant génère une valeur aléatoire qui est combinée aux valeurs fournies par les autres. Le résultat combiné devient un ensemble de paramètres auquel tout le monde peut faire confiance. 

Ce processus est essentiel, car si tous les participants s’entendaient, ils pourraient compromettre le système en générant une preuve pour une affirmation invalide. La présence d’un seul participant honnête suffit toutefois à garantir la sécurité des paramètres. 

Zcash a notamment utilisé une cérémonie de confiance pour initialiser les fonctionnalités de confidentialité de la chaîne. Ethereum a également organisé la cérémonie KZG, un rituel public coordonné destiné à fournir une base cryptographique à ses efforts de mise à l’échelle (par exemple, EIP-4844 / proto-danksharding). 

Notez que certains systèmes de preuve à divulgation nulle de connaissance, comme les zk-STARK, ne nécessitent aucune configuration de confiance. Nous approfondirons ce sujet dans le deuxième article.

Conclusion

Dans cet article, nous avons exploré la théorie, les mathématiques et la cryptographie qui sous-tendent les preuves à divulgation nulle de connaissance. Vous disposez désormais de toutes les bases nécessaires pour comprendre ce qu’elles sont. Nous pouvons maintenant appliquer ces connaissances à des réseaux comme Solana afin de contribuer aux discussions et au développement de ces preuves.

Nous poursuivons cette analyse dans le deuxième et dernier article de notre série en deux parties sur les preuves à divulgation nulle de connaissance, judicieusement intitulé Preuves à divulgation nulle de connaissance : leurs applications sur Solana. 

Si vous avez lu jusqu’ici, merci, anon ! Saisissez votre adresse e-mail ci-dessous pour ne manquer aucune actualité sur les nouveautés de Solana. Envie d’aller plus loin ? Découvrez les derniers articles sur le blog Helius et poursuivez votre exploration de Solana dès aujourd’hui.

Ressources supplémentaires

• Le véritable hasard existe-t-il ?
• Courbes elliptiques — Computerphile
• Introduction à la classe de complexité NP-complète
• Problèmes d’échange de clés — Computerphile
• Le cours de Khan Academy sur la cryptographie
• Cryptographie à clé publique — Computerphile
• La complexité en connaissance des systèmes de preuve interactifs