Traduction partielle de How to leak a secret?
Ronald L. Rivest (1) , Adi Shamir (2) et Yael Tauman (2)
(1) Laboratoire d’informatique, Massachusetts Institute of Technology,
Cambridge, MA 02139, rivest@mit.edu
(2) Département d’informatique, Institut Weizmann, Rehovot 76100, Israël.
Dans cet article, nous formalisons la notion de signature en anneau, ce qui permet de spécifier un ensemble de signataires possibles sans révéler quel membre a effectivement produit la signature. Contrairement aux signatures de groupe, les signatures en anneau n’ont pas de gestionnaires de groupe, pas de procédures de configuration, pas de procédure de révocation, ni de coordination: tout utilisateur peut choisir un ensemble de signataires possibles qui comprend lui-même, et signer tout message en utilisant sa clé secrète et les clés publiques des autres, sans obtenir leur approbation ou assistance. Les signatures en anneau offrent un moyen élégant :
La principale contribution de cet article est une nouvelle construction de ces signatures qui est inconditionnellement ambigue sur les signataures, prouvablement sécurisée dans le modèle d’oracle aléatoire, et exceptionnellement efficace: l’ajout de chaque membre de l’anneau augmente le coût de signature ou vérification par une seule multiplication modulaire et une seule cryptage symétrique.
Mots-clés: schéma de signature, schéma de signature en anneau, schéma de signature signataire-ambigu, schéma de signature de groupe, schéma de signature du vérificateur désigné.
La notion générale d’un système de signature de groupe a été introduite en 1991 par Chaum et van Heyst. Dans un tel schéma, un gestionnaire de groupe de confiance définit à l’avance certains groupes d’utilisateurs et distribue des clés spécialement conçues à leurs membres. Les membres individuels peuvent ensuite utiliser ces clés pour signer des messages de manière anonyme au nom de leur groupe. Les signatures produites par différents membres du groupe sont impossibles à distinguer de leurs vérificateurs, mais pas du responsable de groupe qui peut révoquer l’anonymat des signataires qui se conduisent mal.
Dans cet article, nous formalisons la notion connexe de schémas de signature en anneau . Celles-ci sont des schémas de signature de groupe simplifiés qui n’ont que des utilisateurs et pas de gestionnaires (nous appelons ces signatures «signatures en anneau» au lieu de «signatures de groupe» car les anneaux sont des régions géométriques à périphérie uniforme et sans centre). Les signature de groupe sont utiles lorsque les membres veulent coopérer, tandis que les signatures en anneau sont utile lorsque les membres ne veulent pas coopérer.
Les signatures de groupe et les signatures en anneau sont ambiguës au signataire (le signataire ne peut pas être connu), mais dans un schéma de signature en anneau, il y a pas de groupes d’utilisateurs prédéfinis, il n’y a pas de procédures pour définir, modifier ou supprimer les groupes, il n’existe aucun moyen de distribuer des clés spécialisées, ni de manière de révoquer l’anonymat du signataire réel (à moins qu’il ne décide de s’exposer lui-même). Notre seule hypothèse est que chaque membre est déjà associé à la clé publique d’un schéma de signature standard tel que RSA. Pour produire une signature en anneau, le signataire lui-même déclare un ensemble arbitraire de signataires possibles comprend lui-même, et calcule la signature entièrement par lui-même en utilisant uniquement sa clé secrète et les clés publiques des autres. En particulier, les autres signataires possibles n’auraient pu choisir d’utiliser leurs clés RSA que pour faire du commerce électronique sur Internet, et peuvent ignorer complètement que leurs clés publiques sont utilisées par un étranger pour produire une signature en anneau sur un message qu’ils n’ont jamais vu et
ne voudraient pas signer.
La notion de signature en anneau n’est pas complètement nouvelle, mais les références précédentes ne formalisent pas clairement la notion de manière précise et proposent des constructions moins efficaces et/ou qui ont des objectifs différents, quoique liés. Eles ont tendance à décrire cette notion dans le contexte des signatures générales de groupe ou de constructions multiparties, qui sont assez inefficaces.
La publication peut être considérée comme un schéma de signature en anneau. Cependant, les anciennes approches exigent des preuves de connaissance zéro à chaque signature (zero-knowledge proofs), et les approches plus récentes nécessitent autant d’exponentiations modulaires qu’il y a de membres dans l’anneau. Cramer et Al. montrent comment produire des preuves interactives indiscernables par un témoin. Tel preuves pourraient être combinées avec la technique Fiat-Shamir pour produire des régimes de nature. De même, DeSantis et al. montrent que le SZK interactif pour les langues auto-réductibles aléatoires sont fermées dans le cadre d’opérations booléennes monotones, et montrer l’applicabilité de ce résultat à la construction d’une signature en anneau (bien qu’ils n’utilisent pas cette terminologie). La construction directe des signatures en anneau proposée dans cet article est basée sur une idée complètement différente, et est exceptionnellement efficace pour les grands anneaux (en ajoutant une seule multiplication modulaire et un chiffrement symétrique par membre à la fois pour générer et pour vérifier ces signatures). Les signatures résultantes sont inconditionnellement signataires ambigus et prouvablement sécurisés dans l’oracle aléatoire modèle
Terminologie : Nous appelons un ensemble de signataires possibles un anneau . Nous appelons le membre de l’anneau qui produit la signature réelle le signataire et chacun des autres membres de l’anneau un non-signataire . Nous supposons que chaque signataire possible est associé (via un répertoire PKI ou certificat) avec une clé publique Pk qui définit son schéma de signature et précise sa clé de vérification. La clé secrète correspondante (qui est utilisée pour générer des signatures classiques) est notée Sk . La notion générale d’un schéma de signature en anneau ne nécessite aucune propriété particulière de ces schémas de signature individuels, mais notre construction la plus simple suppose qu’ils utilisent des permutations unidirectionnelles de trappe (telles que les fonctions RSA) pour générer et vérifier les signatures. Un schéma de signature en anneau est défini par deux procédures :
Un schéma de signature en anneau est mis en place gratuitement : le signataire n’a pas besoin de la connaissance, ni de son consentement ou de l’aide des autres membres de l’anneau pour les mettre dans l’anneau – tout ce dont il a besoin est la connaissance de leurs clés publiques habituelles.
Différents membres peuvent utiliser différents schémas de signature de clé publique indépendants, avec des clés et des tailles de signature. La vérification doit satisfaire la solidité et l’exhaustivité habituelles conditions, mais en plus nous voulons que les signatures soient ambiguës par rapport aux signataires dans le sens que le vérificateur ne devrait pas être en mesure de déterminer l’identité du signataire réel dans un anneau de taille r avec une probabilité supérieure à 1/r . Cette anonymat limité peut être informatique ou inconditionnel .
Notre construction principale fournit un anonymat inconditionnel dans le sens où même un adversaire infiniment puissant ayant accès à un nombre illimité de signatures de messages choisis produits par le même membre de l’anneau ne peut deviner son identité avec aucun et ne peut lier des signatures supplémentaires au même signataire.
