💻 computer science

Withdrawability in Fiat-Shamir with aborts constructions

Cet article étend le concept de signatures révocables au paradigme de Fiat-Shamir avec aband (aborts) en proposant une construction abstraite avec des preuves de sécurité et en fournissant une instanciation concrète basée sur un schéma de type Dilithium sans indices (no-hint), tout en notant les ajustements mineurs requis pour la version de production ML-DSA avec indices.

Auteurs originaux : Ramses Fernandez-Valencia

Publié 2026-07-08

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ramses Fernandez-Valencia

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous possédez un tampon numérique très spécial et incassable. Une fois que vous avez apposé ce tampon sur un document, il est généralement permanent. Vous ne pouvez pas le retirer, et personne ne peut prétendre que vous ne l'avez pas signé. C'est ainsi que fonctionnent la plupart des signatures numériques aujourd'hui.

Mais et si vous vouliez une signature « douce » ? Une signature que vous pourriez retirer si vous changiez d'avis, avant que quiconque ne la voie, sans pour autant détruire votre capacité à signer d'autres choses.

Ce document présente un nouveau type de signature numérique appelée « Signature Retirable » (Withdrawable Signature). Elle est conçue pour fonctionner dans un futur où de puissants ordinateurs quantiques pourraient briser la sécurité actuelle, elle utilise donc des mathématiques basées sur les « réseaux » (pensez à un labyrinthe complexe et multidimensionnel) plutôt que l'ancienne mathématique que les ordinateurs quantiques peuvent résoudre facilement.

Voici comment le document le décompose, en utilisant des analogies simples :

1. Le Problème : Le « Tampon Permanent »

Habituellement, lorsque vous signez un contrat numérique, c'est comme si vous tamponniez un document avec de l'encre humide qui sèche instantanément. Une fois sec, c'est là pour toujours.

Le Problème : Parfois, vous avez besoin de changer d'avis. Peut-être avez-vous signé un contrat intelligent sur une blockchain, mais l'accord a échoué. Ou peut-être avez-vous voté dans une élection numérique mais vous vous êtes rendu compte que vous aviez fait une erreur avant que les votes ne soient comptés.
L'Objectif : Vous avez besoin d'un moyen de dire : « J'ai signé ceci, mais je le retire », sans révéler votre mot de passe secret (clé privée) ou gâcher vos autres signatures.

2. La Solution : L'« Enveloppe Double Magique »

Les auteurs ont créé un système où une signature commence comme une note secrète et retirable et peut plus tard être transformée en un tampon public et confirmé.

Imaginez cela comme suit :

Étape 1 : La Signature Retirable (La Note Secrète)
Imaginez que vous écriviez une note et que vous la placiez à l'intérieur d'une boîte spéciale et verrouillée. Vous donnez cette boîte à une personne spécifique (le « vérificateur désigné »).
- Seule cette personne spécifique possède la clé pour ouvrir la boîte et lire la note.
- Le Tour de Magie : Pour n'importe qui d'autre (même un espion qui vous observe), la boîte ressemble à du bruit aléatoire. Ils ne peuvent pas savoir si c'est vous qui avez mis la note dedans, ou si le destinataire a écrit la note lui-même et l'a mise dans la boîte. C'est une situation parfaite de « parole contre parole ». Cela s'appelle l'Ambiguïté.
- En raison de cette ambiguïté, vous pouvez dire : « Je n'ai jamais signé cela », et le destinataire ne peut pas prouver que vous l'avez fait, à moins que vous ne décidiez de le confirmer.
Étape 2 : La Confirmation (Le Tampon Public)
Si vous décidez que vous voulez que la signature soit permanente, vous effectuez une étape de « Confirmation ».
- Vous sortez la note secrète de la boîte et utilisez votre clé secrète pour générer une signature publique standard qui prouve : « Oui, j'ai définitivement écrit ceci ».
- Maintenant, n'importe qui peut le voir, et personne ne peut le nier.

3. Le « Labyrinthe Anti-Quantique » (Fiat-Shamir avec Aborts)

Le document construit ce système en utilisant un type spécifique de mathématiques appelé « Fiat-Shamir avec Aborts ».

L'Analogie : Imaginez essayer de résoudre un labyrinthe géant et complexe pour prouver que vous connaissez le chemin.
La partie « Abort » (Abandon) : Parfois, vous pourriez prendre un mauvais tournant qui révèle accidentellement un secret sur la façon dont vous avez résolu le labyrinthe. Si cela arrive, vous dites simplement : « Abort ! J'ai fait une erreur », et vous recommencez depuis le début. Vous continuez à essayer jusqu'à ce que vous trouviez un chemin qui prouve que vous connaissez le chemin sans divulguer de secrets.
Cette méthode de « essai et réessai » est ce qui rend la signature sécurisée contre les ordinateurs quantiques.

4. Comment ils l'ont construit (Le « No-Hint Dilithium »)

Les auteurs ont pris un schéma de signature quantique existant très célèbre appelé Dilithium (qui est comme un tampon standard à haute sécurité) et l'ont modifié.

Ils ont supprimé une petite fonctionnalité d'« indice » (hint) que Dilithium utilise habituellement pour le rendre plus rapide.
Pourquoi ? Supprimer l'indice rend les mathématiques « parfaites ». Cela garantit que la note secrète est véritablement indiscernable d'une fausse, même pour un supercalculateur.
Ils ont enveloppé cette signature modifiée dans une couche de chiffrement. C'est comme mettre l'« Enveloppe Double Magique » à l'intérieur d'un service de coursier sécurisé que seul l'expéditeur et le destinataire peuvent ouvrir.

5. Pourquoi cela importe (Selon le document)

Le document affirme que cette construction atteint deux choses principales :

L'Inforgeabilité : Même si un pirate vole la clé secrète du destinataire, il ne peut toujours pas falsifier une signature qui semble provenir de l'expéditeur original. Seul l'expéditeur original peut transformer la note « retirable » en un tampon « confirmé ».
La Retirabilité : Tant que vous n'avez pas confirmé la signature, personne (pas même le destinataire) ne peut prouver qui a écrit la note. C'est une égalité parfaite.

Résumé

Le document présente une nouvelle façon de signer des documents numériques qui permet de révoquer votre signature avant qu'elle ne devienne permanente. Elle utilise une « note secrète » que seule une personne spécifique peut lire, qui peut plus tard être transformée en un « tampon public ». Ce système est construit sur des mathématiques « anti-quantiques » (réseaux) et utilise une méthode de « essai et réessai » pour garantir qu'aucun secret ne soit divulgué.

Crucialement, le document se concentre entièrement sur la construction mathématique et les preuves de sécurité. Il mentionne que cela pourrait être utile pour les systèmes de blockchain ou de vote, mais il ne prétend pas avoir construit une application de blockchain ou de vote fonctionnelle pour le moment ; il fournit seulement le « moteur » sécurisé qui pourrait alimenter de tels outils à l'avenir.

Résumé technique : Retrait de signature dans les constructions de type Fiat–Shamir avec abandons

Énoncé du problème
Les signatures numériques offrent traditionnellement une permanence ; une fois générée, une signature ne peut être révoquée sans compromettre la clé privée du signataire ou invalider d'autres signatures. Cette limitation pose des défis dans des environnements dynamiques tels que les contrats intelligents de blockchain, le vote électronique décentralisé et les services d'entiercement (escrow), où les participants peuvent avoir besoin de révoquer des engagements en fonction de l'évolution des conditions. Liu, Baek et Susilo [LBS23] ont introduit les « signatures retirables » (withdrawable signatures), une primitive permettant à un signataire de générer une signature vérifiable uniquement par un vérificateur désigné, laquelle peut ultérieurement être transformée en une signature publiquement vérifiable. Cependant, leur construction repose sur des hypothèses classiques (Logarithme Discret, Diffie-Hellman) vulnérables aux attaques quantiques.

Le défi abordé par cet article est d'étendre le concept de signatures retirables au cadre post-quantique, plus précisément au sein du paradigme Fiat–Shamir avec abandons (Fiat–Shamir with aborts). Ce paradigme est le fondement de schémas de signature post-quantiques de premier plan comme Dilithium (ML-DSA) et HAETAE. Un obstacle structurel spécifique existe : la construction originale de Liu–Baek–Susilo repose sur un secret partagé Diffie-Hellman « gratuit » pour assurer simultanément l'ambiguïté signataire/vérificateur et la désignation. La cryptographie sur réseaux (lattice-based) manque d'un analogue efficace et peu coûteux pour ce secret partagé, nécessitant une nouvelle approche architecturale.

Méthodologie
L'article propose une construction abstraite générale pour les signatures retirables basée sur le paradigme Fiat–Shamir avec abandons, suivie d'une instanciation concrète.

Construction abstraite :
Les auteurs définissent un cadre comprenant cinq algorithmes : KeyGen, WSign (signature avec retrait), WSVerify (vérification avec retrait), Confirm, et CVerify.
- Mécanisme central : Le schéma utilise une preuve de connaissance de type OR (OR-proof) de Fiat–Shamir avec abandons à deux parties. La signature avec retrait se compose de deux branches : l'une générée par le signataire (utilisant sa clé secrète) et l'autre simulée par le signataire pour imiter la branche du vérificateur.
- Ambiguïté : Comme le signataire et le vérificateur désigné peuvent tous deux générer une branche valide (le signataire en simulant le vérificateur, et le vérificateur en simulant le signataire), l'origine de la signature est indiscernable pour des tiers.
- Confirmation : Pour rendre la signature publiquement vérifiable, le signataire exécute l'algorithme Confirm, qui génère une signature ordinaire standard sur le message, l'ensemble des clés publiques et la signature avec retrait elle-même. Cela lie la signature avec retrait à l'identité du signataire sans nécessiter la redérivation de l'aléa partagé (ce qui est infaisable dans le cadre de la réduction d'échantillonnage de rejet du mode Fiat–Shamir avec abandons sur réseaux).
Variante de Vérificateur Désigné Fort (SDVS) :
Pour garantir que la signature avec retrait ne soit pas publiquement vérifiable (correspondant au modèle de Liu–Baek–Susilo), les auteurs chiffrent le cœur public de la signature à l'aide d'un schéma de chiffrement à clé publique (PKE) (spécifiquement, le module-LWE sécurisé en CPA sous-jacent à ML-KEM/Kyber).
- La signature est chiffrée à la fois pour la clé publique du vérificateur désigné et pour la clé publique du signataire. Cela permet au vérificateur de déchiffrer et de vérifier, et permet au signataire de déchiffrer et d'effectuer l'opération Confirm de manière sans état (stateless).
- Cette approche remplace le secret partagé Diffie-Hellman par un chiffrement explicite, reconnaissant que l'échange de clés non interactif (NIKE) sur réseaux est actuellement trop inefficace à cette fin.
Instanciation concrète :
Le cadre abstrait est instancié à l'aide d'une construction de type Dilithium sans indice (no-hint), full- $t$ .
- Les auteurs utilisent une variante de Dilithium qui n'utilise pas d'« indices » (la séparation $t_1$ / $t_0$ ), garantissant que le simulateur de la preuve de connaissance nulle est parfait ( $\varepsilon_{zk} = 0$ ).
- Ce choix simplifie les preuves de sécurité, particulièrement pour la propriété de retraitabilité, en évitant les petites erreurs statistiques associées aux schémas avec indices.

Contributions clés

Cadre général : L'article introduit la première construction abstraite pour les signatures retirables basée sur le paradigme Fiat–Shamir avec abandons, comblant le fossé entre le modèle de Liu–Baek–Susilo et la cryptographie sur réseaux post-quantique.
Preuves de sécurité :
- Non-falsifiabilité : Le schéma est prouvé non falsifiable sous corruption interne (où l'adversaire détient la clé secrète du vérificateur) dans le modèle de l'oracle aléatoire quantique (QROM). La preuve se réduit à la sécurité EUF-CMA du schéma de signature sur réseaux sous-jacent (hypothèses SelfTargetMSIS/MSIS).
- Retraitabilité : Le schéma est prouvé comme étant retirable, ce qui signifie qu'un adversaire ne peut pas distinguer si une signature a été générée par le signataire ou par le vérificateur désigné. Pour l'instanciation sans indice, cette propriété est statistique (informationnelle) avec $\varepsilon_{zk} = 0$ , reposant sur la perfection de la connaissance nulle honnête-vérificateur sans abandon (naHVZK) du schéma d'identification sous-jacent et l'entropie minimale des engagements.
Adaptation aux contraintes post-quantiques : L'article traite explicitement l'absence de secret partagé Diffie-Hellman sur réseaux. Il démontre que la désignation peut être accomplie via le chiffrement à clé publique (PKE) plutôt que par NIKE, et que l'ambiguïté du signataire peut être obtenue via des preuves OR plutôt que par symétrie algébrique.

Résultats

Sécurité concrète : Pour l'instanciation Dilithium sans indice, l'article fournit des bornes de sécurité concrètes. L'avantage de non-falsifiabilité est borné par la sécurité du schéma sous-jacent plus un terme négligeable lié à la programmation de l'oracle aléatoire ( $2^{-1024}$ ). L'avantage de retraitabilité est borné par $1/2$ plus un terme statistique négligeable, atteignant effectivement une ambiguïté parfaite pour le vérificateur désigné dans le cas sans indice.
Comparaison : Les auteurs fournissent une comparaison détaillée avec le schéma de Liu–Baek–Susilo (Tableau 2). Bien que la construction sur réseaux nécessite du matériel de clé supplémentaire (clés de chiffrement) et aboutisse à des signatures plus grandes (en raison de la surcharge de chiffrement), elle gagne deux propriétés significatives : la signature avec retrait est pseudialeatoire (cachant son existence aux tiers) et la non-transférabilité contre le vérificateur désigné est parfaite (statistique) plutôt que computationnelle.

Signification
L'article affirme que cette recherche est une adaptation nécessaire de la primitive de signature retirable à l'ère post-quantique. Il établit que la retraitabilité est réalisable en cryptographie sur réseaux sans dépendre des analogues de Diffie-Hellman sur réseaux, qui sont inefficaces ou inexistants. En séparant les mécanismes de désignation (chiffrement) et d'ambiguïté (preuves OR), les auteurs proposent une construction robuste et prouvable, qui maintient les propriétés de sécurité des schémas sous-jacents comme Dilithium tout en ajoutant la flexibilité critique de la révocation de signature. Ces travaux suggèrent que ces constructions pourraient améliorer la résistance quantique dans les systèmes blockchain où la révocation de transactions est souhaitable mais traditionnellement difficile à mettre en œuvre.