Lattice-based extended withdrawability

Résumé Technique : Signature à Retrait Étendu basée sur les Réseaux

Énoncé du Problème
Les signatures numériques assurent traditionnellement la permanence : une fois signé, un message reste vérifiable sous la clé publique du signataire indéfiniment. Cependant, de nombreuses applications décentralisées (par exemple, accès à durée limitée, accords révocables, séquestre décentralisé) nécessitent la possibilité de retirer une signature sans révéler la clé secrète ni invalider d'autres signatures. Liu, Susilo et Baek ont introduit les signatures à retrait étendu (EWS - extended withdrawable signatures) pour répondre à ce besoin, permettant à une signature d'être ambiguë parmi un ensemble de signataires potentiels jusqu'à ce que le véritable signataire la « confirme ». Leur construction repose sur des primitives de logarithme discret (signatures de Schnorr et signatures 1-sur-N).

Ce document traite de l'écart post-quantique : l'algorithme de Shor brise la fondation de logarithme discret des schémas EWS existants. Bien que des signatures basées sur les réseaux (par exemple, Dilithium) existent, une « transcription littérale » directe de la construction de Liu-Susilo-Baek (LSB) vers les réseaux échoue en raison d'obstructions structurelles. Plus précisément, le schéma LSB repose sur la publication de décalages multiplicatifs des clés publiques pour re-randomiser la contribution du signataire. Dans le cadre des réseaux (Fiat-Shamir avec abandon), de tels décalages prennent la forme de $As_1 s_j$, qui partagent un facteur commun $As_1$ avec la clé publique du signataire $t_i = As_1 + s_2$. Publier ces décalages divulgue l'identité du signataire, rompant ainsi l'ambiguïté requise.

Méthodologie
Les auteurs proposent une nouvelle construction pour les EWS basées sur les réseaux qui s'écarte de l'approche LSB en traitant le schéma comme une signature de groupe revendiquable (Park et Sealfon). Au lieu de tenter de re-randomiser les clés publiques en clair, la construction sépare les deux fonctions fondamentales de l'EWS :

1. L'ambiguïté : Assurée par une signature anonyme 1-sur-N (de groupe), utilisée comme une boîte noire.
2. La confirmation : Assurée par la revendication du signataire, consistant en une signature liante sur l'objet retirable et l'ouverture d'un engagement masquant l'indice du signataire.

La construction opère selon le paradigme Fiat-Shamir avec abandon et repose sur trois ingrédients modulaires :

• Un schéma de signature de base (par exemple, un schéma de type Dilithium sans indice et à $t$ complet).
• Une signature anonyme 1-sur-N (instanciée via une preuve de type 1-sur-plusieurs dans les réseaux).
• Un schéma d'engagement de type masquage et de liaison (de type Ajtai).

La signature retirable $\sigma$ consiste en une signature de groupe $\sigma_r$ sur le message, un engagement $C$ vers l'indice du signataire, ainsi que l'ensemble des clés publiques. Pour confirmer, le signataire révèle l'ouverture $(i, \rho)$ de $C$ et signe l'intégralité de l'objet retirable $\langle \mu, \pi, \sigma \rangle$ avec sa clé secrète de base.

Contributions Clés

1. Raffinement du Modèle de Sécurité : Les auteurs affinent le modèle de sécurité de LSB.

   • Ils remplacent la définition de « complétude » de LSB de la retraitabilité étendue par un jeu d'indistinguabilité anonymat-jusqu'à-revendication (Définition 14), capturant explicitement la garantie de masquage.
   • Ils introduisent la solidité de la revendication (Définition 16), garantissant qu'une signature confirmée lie l'identité à un indice de signataire unique, empêchant un adversaire d'attribuer la même signature à différents membres du groupe.
   • Ils formalisent l' inforgeabilité sous corruption interne avec un indice cible fixe, évitant la perte de réduction multiplicative $q_H$ (requête de hachage) présente dans la preuve de LSB.

2. Construction Générique : Une construction générique d'EWS sur le paradigme Fiat-Shamir avec abandon est présentée. Crucialement, elle ne publie aucune valeur dérivée du signataire en clair. L'ambiguïté provient uniquement des propriétés de connaissance nulle de la signature de groupe, et la traçabilité provient de la propriété de liaison de l'engagement.

3. Résultat d'Impossibilité : Le document prouve (Proposition 2) qu'une transcription littérale dans les réseaux de la signature 1-sur-N de LSB (utilisant la division de défi additive) est peu sûre. Dans le contexte des réseaux avec des défis creux, la probabilité qu'un signataire honnête produise une division de défi valide est négligeable ($2^{-\Omega(n)}$), et même si la complétude pouvait être corrigée, l'anonymat échouerait car le transcript simulé ne serait pas indiscernable d'un transcript réel.

4. Preuves de Sécurité Complètes : Les auteurs fournissent des réductions explicites par jeu dans le Modèle de l'Oracle Aléatoire Quantique (QROM) pour :

   • La correction : Réduction à la correction des primitives sous-jacentes.
   • Le retrait étendu : Réduction au masquage de l'engagement (MLWE décisionnel) et à l'anonymat du schéma 1-sur-N.
   • L'inforgeabilité : Réduction à la sécurité EUF-CMA de la signature de base (sans retour en arrière et sans perte $q_H$).
   • La solidité de la revendication : Réduction à la liaison de l'engagement (MSIS).

5. Instanciation : Le schéma est instancié en utilisant une signature de base de type Dilithium sans indice et à $t$ complet, et une preuve 1-sur-plusieurs établie dans les réseaux. Le document discute des choix de paramètres et note que HAETAE pourrait servir d'alternative de base.

Résultats
Le document établit que la construction proposée est :

• Correcte : Les signatures honnêtes se vérifient avec une probabilité écrasante.
• À Retrait Étendu : Un adversaire détenant toutes les clés secrètes ne peut distinguer quel membre d'un groupe a produit une signature retirable avant que le signataire ne la confirme.
• Inforgeable : Même avec accès aux oracles de signature et aux clés secrètes de tous les membres du groupe sauf le cible, un adversaire ne peut pas forger une signature confirmée pour un nouveau message.
• Solide : Une signature confirmée ne peut être attribuée à deux signataires différents.

La sécurité repose sur des hypothèses standards de réseaux modulaires : MLWE décisionnel, MSIS et SelfTargetMSIS, ainsi que sur la propriété de connaissance nulle de la preuve 1-sur-plusieurs.

Signification
Le document revendique sa pertinence en fournissant la première réalisation post-quantique sécurisée de signatures à retrait étendu. Il démontre que la construction de logarithme discret de LSB ne peut pas être directement transposée aux réseaux en raison de l'absence de « re-randomisation libre » des valeurs partagées. En recadrant le problème comme une signature de groupe revendiquable et en utilisant un mécanisme de confirmation basé sur l'engagement, les auteurs parviennent à un schéma qui est :

• Sécurisé Post-Quantique : Résistant aux adversaires quantiques via les hypothèses de réseaux.
• Vérifiable Publiquement : Contrairement aux variantes à vérificateur désigné, toute partie peut vérifier la signature retirable.
• Modulaire : Les preuves de sécurité reposent uniquement sur les interfaces des primitives sous-jacentes, permettant la substitution de différents composants de réseaux (par exemple, différentes signatures de base ou preuves de groupe) sans avoir à re-prouver l'ensemble du système.
• Fidèle aux Objectifs Originaux : La conception préserve les objectifs fonctionnels et l'intuition du schéma LSB original tout en corrigeant ses failles structurelles dans le contexte des réseaux.