Un accumulateur cryptographique permet de représenter un jeu de données de façon concise, et de prouver sa non-appartenance à un ensemble plus grand. Ce concept fut introduit en 1993 par Benaloh et De Mare. Ses applications aux cryptomonnaies et au Web3 concernent principalement la confidentialité.
Qu'est-ce qu'un accumulateur cryptographique ?
Ce type d'algorithme permet de justifier l'appartenance d'un ensemble de données à un ensemble plus grand. Il fonctionne à sens unique, c'est-à-dire qu'il est possible de prouver l'appartenance du jeu de données sans divulguer l'ensemble auquel il appartient.
Un accumulateur cryptographique est donc un système de preuve à divulgation nulle de connaissance.
Une preuve à divulgation nulle de connaissance (zero-knowledge proof ou ZKP) permet de prouver la véracité d'une proposition sans avoir connaissance de la proposition elle-même.
Il y a plusieurs méthodes pour construire un accumulateur, reposant généralement sur des fonctions de hachage.
Une fonction de hachage permet de transformer un nombre - ou une chaîne de caractère - de très grande taille en une valeur (le hash) de longueur fixe. Elle est à sens unique : connaître la résultante ne permet pas de reconstruire les données d'entrée. De plus, deux entrées différentes donneront toujours un hash différent.
On emploie donc une fonction de hachage pour accumuler un grand ensemble de données, et le représenter de façon unique et compacte. On appelle le résultat la valeur d'accumulation. Cette valeur peut ensuite être utilisée pour prouver qu'une donnée particulière fait ou non partie de l'ensemble accumulé, sans révéler cet ensemble.
- Le témoin est la valeur qui prouve qu'un élément particulier est inclus ou non dans l'ensemble accumulé ;
- Si un élément est inclus dans l'ensemble accumulé, on a une preuve d'adhésion ;
- Si l'élément n'est pas inclus dans l'ensemble, il s'agit d'une preuve de non-adhésion.
Cela nous amène donc aux applications des accumulateurs cryptographiques dans le domaine de l'authentification.
Cas d'usage
Originellement, les accumulateurs cryptographiques furent utilisés dans les systèmes d'horodatage, pour prouver l'existence d'une valeur à un instant donné. Ils ont ensuite servi à construire des systèmes d'authentification :
- Signatures numériques homomorphes ;
- Informations d'identification anonymes ;
- Signatures de groupe ;
- Externalisation de données, tout en préservant leur confidentialité ;
- Authentification de structures de données ;
- Etc.
Dans le domaine des cryptomonnaies, ils permettent de prouver la validité des transactions d'un utilisateur sans les divulguer, préservant ainsi son anonymat. On peut également les utiliser pour compresser l'état d'une blockchain, réduisant ainsi les coûts en stockage et en calcul. Ils sont également employés pour réaliser des calculs multi-partites (MPC) sécurisés et confidentiels. Sur Ethereum, on peut implémenter des accumulateurs cryptographiques grâce à l'EIP-198.
Fonctionnement d'un accumulateur cryptographique
Depuis leur introduction par Benaloh et De Mare en 1993, plusieurs méthodes furent utilisées pour construire ces algorithmes de preuve. Elles ont été améliorées selon 3 axes majeurs :
- Gestion des données efficace (coûts de stockage et de calcul) ;
- Sécurité de l'authentification ;
- Confidentialité.
On distingue plusieurs types d'accumulateurs. Tout d'abord, un accumulateur est dit statique si l'ensemble accumulé ne change pas au cours du temps. Dans le cas contraire, il est dit dynamique. Ce dernier présente plus de cas d'usages que le premier type.
Un accumulateur universel permet d'accumuler tous types de valeurs (entiers, chaînes). Les accumulateurs non-universels sont conçus pour gérer efficacement des entiers ou des chaînes spécifiques.
Avec ceci en tête, il faut choisir une fonction de hachage pour construire un accumulateur. L'algorithme RSA est privilégié, car il représente le meilleurs compromis entre :
- Le nombre de paramètres d'entrée ;
- La taille de la valeur d'accumulation ;
- Le calcul d''une preuve.
Les accumulateurs RSA nécessitent de choisir deux nombres premiers de grande taille (1024 bits). Ils peuvent alors être générés par une entité centralisée (trusted setup : il faut faire confiance au générateur) ou décentralisée (ce qui est plus sécurisé). Les mathématiques de la construction de la valeur d'accumulation, d'un témoin, et du calcul des preuves d'appartenance ou de non-appartenance sont trop complexes à détailler ici (voir ressources en pied de page). Pour résumer le processus :
- Chaque élément de l'ensemble accumulé est transformé en nombre premier ;
- Les valeurs sont accumulées en calculant l'exponentiation modulaire de la valeur actuelle de l'accumulateur pour chaque nouvel élément ;
- Le témoin est recalculé chaque fois qu'un élément est ajouté ou enlevé à l'accumulateur.
Ressources
Les férus de mathématiques et de cryptologie peuvent aller plus loin en consultant les références suivantes :
- One-way accumulators : A decentralized alternative to digital signatures - Benaloh & de Mare (1993)
- Dynamic accumulators and application to efficient revocation of anonymous credentials - Camenisch, Lysyanskaya (2002)
- Performances of Cryptographic Accumulators - Amrit Kumar, Pascal Lafourcade, Cédric Lauradoux
- Universal Accumulators with Efficient Nonmembership Proofs - Jiangtao Li, Ninghui Li, Rui Xue
