🔢 mathematics

A Compact Post-quantum Strong Designated Verifier Signature Scheme from Isogenies

Cet article propose un nouveau schéma de signature compacte à vérificateur désigné fort, post-quantique, basé sur des actions de groupes cryptographiques (abéliens) et des isogénies, garantissant que seul le vérificateur désigné peut confirmer l'authenticité d'une signature.

Auteurs originaux : Farzin Renan, Wendi Gao, Jason T. LeGrow

Publié 2026-09-14

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Farzin Renan, Wendi Gao, Jason T. LeGrow

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

Dans le monde numérique, la confiance est généralement une affaire publique. Lorsque vous signez un document en ligne, une signature numérique agit comme un sceau que quiconque possède les outils appropriés peut vérifier. Cette transparence est l'épine dorsale de la sécurité moderne, garantissant qu'un message provient réellement de son expéditeur et n'a pas été altéré. Cependant, il existe des situations où cette nature publique est un défaut plutôt qu'une caractéristique. Imaginez une conversation privée entre deux personnes où l'une veut prouver son identité à l'autre, mais doit s'assurer qu'aucun tiers ne pourra jamais être convaincu que le message vient d'elle. Si le destinataire pouvait prouver l'origine à un juge ou à un ami, la confidentialité de l'échange serait rompue. C'est le défi des signatures à « vérificateur désigné » : créer une preuve qui est indéniable pour le destinataire prévu, mais totalement non convaincante pour quiconque d'autre.

La difficulté s'accentue lorsque nous considérons l'avenir. Les méthodes de chiffrement qui protègent actuellement nos données reposent sur des problèmes mathématiques difficiles pour les ordinateurs d'aujourd'hui, mais qui pourraient être résolus facilement par de puissantes machines quantiques. Alors que les scientifiques se lancent dans une course pour construire des systèmes capables de résister à ces menaces futures, ils se tournent vers une branche des mathématiques impliquant les formes de courbes et les manières dont elles peuvent être transformées les unes en les autres. Ces transformations, connues sous le nom d'isogénies, offrent un nouveau fondement à la sécurité qui est censé être sûr face aux attaques quantiques. L'objectif est de construire un système qui non seulement survive à l'ère quantique, mais préserve également la délicate vie privée des conversations désignées.

Une équipe de chercheurs a maintenant introduit une nouvelle méthode pour créer ces signatures privées et résistantes au quantique. Ils appellent leur système CSI-SDVS, un schéma construit sur les propriétés des isogénies supersingulières commutatives. L'idée centrale est d'utiliser la relation mathématique unique entre les courbes elliptiques pour créer une signature que seul le destinataire prévu peut vérifier. Dans ce système, l'expéditeur et le destinataire détiennent chacun une clé secrète et une clé publique correspondante. Lorsque l'expéditeur souhaite signer un message, il utilise sa clé secrète et la clé publique du destinataire pour générer un code unique. Le destinataire peut ensuite utiliser sa propre clé secrète pour vérifier si le code est valide. La brillance de la conception réside dans sa capacité de simulation. Le destinataire peut également utiliser sa clé secrète pour générer une signature qui ressemble exactement à celle de l'expéditeur. Parce que le destinataire peut créer un faux parfait, il ne peut pas prouver à un tiers qu'une signature spécifique provient de l'expéditeur plutôt que d'avoir été créée par lui-même. Cette propriété, connue sous le nom de non-transférabilité, garantit que la conversation reste privée même si le destinataire tente de partager la preuve.

Les chercheurs ont démontré que leur nouveau schéma est non seulement sécurisé contre les ordinateurs quantiques, mais aussi hautement efficace. Dans les tentatives précédentes pour construire des systèmes similaires, les clés numériques et les signatures étaient souvent énormes, nécessitant des centaines de kilo-octets de données pour être stockées ou transmises. Cela les rendait peu pratiques pour de nombreuses applications réelles. Le nouveau design, cependant, est remarquablement compact. En utilisant un ensemble spécifique de paramètres connus sous le nom de CSIDH-512, les chercheurs ont obtenu un système où les clés secrètes mesurent 256 bits, les clés publiques 512 bits, et les signatures elles-mêmes ne font également que 512 bits. Pour mettre cela en perspective, une signature numérique standard dans les anciens systèmes pourrait avoir la taille d'un petit fichier texte, tandis que cette nouvelle signature a environ la taille d'une seule ligne de texte. Cette réduction spectaculaire de la taille rend la technologie viable pour une utilisation sur des appareils dotés d'une mémoire et d'une bande passante limitées.

L'équipe a prouvé que leur système répond à toutes les normes de sécurité rigoureuses requises pour ce type de cryptographie. Ils ont montré qu'un attaquant ne peut pas falsifier une signature sans les clés secrètes, et ils ont prouvé que l'identité du signataire reste cachée pour quiconque autre que le vérificateur désigné. Ces preuves reposent sur l'hypothèse que résoudre certains problèmes mathématiques liés aux actions de groupe de ces courbes est informatiquement impossible, même pour un ordinateur quantique. Les chercheurs ont également exploré un modèle mathématique spécifique pour montrer que la sécurité de leur système pourrait être liée à un problème légèrement différent, mais tout aussi difficile. Cette approche à double couche renforce la confiance dans la robustesse du système.

En combinant la confidentialité de la vérification désignée avec l'efficacité de la cryptographie basée sur les isogénies, ce travail offre une solution pratique pour une communication sécurisée et privée dans un monde post-quantique. Il fait passer le domaine des possibilités théoriques aux outils concrets et utilisables. Les chercheurs ont montré qu'il est possible d'avoir une signature suffisamment forte pour être la confiance du destinataire, mais suffisamment faible pour être niée à tous les autres, tout en gardant les données assez petites pour être utilisées partout. Cet équilibre entre confidentialité, sécurité et efficacité marque une étape importante dans la préparation de notre infrastructure numérique aux défis de l'avenir.

Résumé Technique : Un schéma de signature à vérificateur désigné fort et compact post-quantique issu des isogénies

Énoncé du Problème

Les signatures numériques assurent traditionnellement la non-répudiation, ce qui signifie que toute partie ayant accès à la clé publique d'un signataire peut vérifier l'authenticité d'une signature. Bien qu'utile pour de nombreuses applications, cette propriété est indésirable dans les scénarios nécessitant des communications « hors enregistrement » (off-the-record), où un signataire (Alice) souhaite authentifier un message auprès d'un destinataire spécifique (Bob) sans permettre à Bob de prouver à un tiers que le message provient d'Alice.

Pour répondre à cela, les signatures à vérificateur désigné fort (SDVS - Strong Designated Verifier Signatures) ont été introduites. Un schéma SDVS garantit que seul le vérificateur désigné peut vérifier l'authenticité de la signature. Crucialement, il satisfait la non-transférabilité : le vérificateur désigné peut simuler des signatures qui sont informatiquement indiscernables des signatures réelles, empêchant ainsi de convaincre un tiers de la validité de la signature. De plus, les schémas SDVS doivent satisfaire la Confidentialité de l'Identité du Signataire (PSI - Privacy of Signaler's Identity), garantissant que, compte tenu d'une signature valide et de plusieurs clés publiques candidates, aucun tiers ne peut déterminer quelle clé a été utilisée pour signer.

Bien que des schémas SDVS existent en cryptographie classique (basés sur les couplages bilinéaires ou les signatures de Schnorr), ils sont vulnérables aux attaques quantiques via l'algorithme de Shor. Les propositions post-quantiques existantes basées sur les codes ou les réseaux (lattices) souffrent souvent de tailles de clés et de signatures importantes (par exemple, une complexité de $O(\lambda^2)$ ) ou se sont avérées échouer à satisfaire les propriétés de non-transférabilité. Des propositions récentes basées sur les isogénies ont fait face à des ruptures de sécurité (par exemple, SIDH) ou reposent sur des hypothèses qui pourraient ne pas être aussi robustes que souhaité.

Méthodologie

Les auteurs proposent CSI-SDVS, un nouveau schéma SDVS basé sur l'action de groupe CSIDH (Commutative Supersingular Isogeny Diffie-Hellman). La construction exploite la structure algébrique de l'action du groupe de classes idéales sur l'ensemble des courbes elliptiques supersingulières sur un corps fini $\mathbb{F}_p$ .

Composants Fondamentaux

Configuration de l'Action de Groupe : Le schéma opère au sein d'une action de groupe effective $(G, X, *)$ , où $G$ est le groupe de classes idéales d'un ordre dans un corps quadratique imaginaire, et $X$ est l'ensemble des courbes elliptiques supersingulières. L'action est libre et transitive.
Génération de Clés :
- Le signataire et le vérificateur génèrent des clés secrètes ( $sk_S, sk_V$ ) comme des entiers aléatoires dans $\mathbb{Z}_N$ (où $N$ est le nombre de classes).
- Les clés publiques sont générées en appliquant l'action de groupe à une courbe de base $E$ : $pk_S = [g^{sk_S}] * E$ et $pk_V = [g^{sk_V}] * E$ .
Signature et Simulation :
- Signature : Pour signer un message $m$ , le signataire choisit un $z$ aléatoire dans $\mathbb{Z}_N$ , calcule $Y = [g^{z+sk_S}] * pk_V$ , et définit la signature $\sigma = (h, z)$ où $h = H(Y || m)$ .
- Simulation : Le vérificateur, possédant $sk_V$ , peut simuler une signature en choisissant un $z$ aléatoire, en calculant $Y = [g^{z+sk_V}] * pk_S$ , et en définissant $\sigma = (h, z)$ avec $h = H(Y || m)$ .
- Correction : En raison de la commutativité de l'action de groupe, $[g^{z+sk_S}] * pk_V = [g^{z+sk_S+sk_V}] * E = [g^{z+sk_V}] * pk_S$ . Ainsi, la valeur $Y$ calculée par le signataire et le simulateur est identique, garantissant que les deux produisent des signatures valides pour le même intrant de hachage.
Vérification : Le vérificateur vérifie si $h = H([g^{z+sk_V}] * pk_S || m)$ .

Contributions Clés

SDVS Post-Quantique Compact : Le document présente CSI-SDVS, un schéma SDVS efficace avec une complexité de $O(\lambda)$ pour les clés et les signatures. En utilisant les paramètres CSIDH-512, le schéma atteint :
- Clé Secrète : 256 bits.
- Clé Publique : 512 bits.
- Signature : 512 bits.
  Cela représente une amélioration significative par rapport aux précédents schémas SDVS basés sur les réseaux qui ont souvent des tailles de $O(\lambda^2)$ , et aux schémas basés sur les isogénies avec des clés publiques plus grandes.
Preuves de Sécurité dans le ROM et l'AGAM :
- Non-Transférabilité (NT) : Prouvée de manière inconditionnelle, car les distributions des signatures réelles et simulées sont identiques.
- Unforgeabilité Forte (SUF-CMA) et PSI : Prouvées sûres dans le Modèle de l'Oracle Aléatoire (ROM) sous l'hypothèse GA-DDH (Group Action Decisional Diffie-Hellman).
- Réductions Serrées : Les auteurs prouvent ensuite que dans le Modèle d'Action de Groupe Algébrique (AGAM), la sécurité SUF-CMA et PSI de CSI-SDVS se réduisent étroitement au GAIP (Group Action Inverse Problem), un problème computationnel plutôt que décisionnel.
Analyse de Sécurité : Le schéma est démontré comme satisfaisant toutes les définitions de sécurité SDVS standards (NT, SUF-CMA, PSI) sans dépendre du protocole SIDH qui a été cassé, en utilisant l'action de groupe CSIDH actuellement considérée comme sûre.

Résultats

Le document fournit des preuves de sécurité formelles démontrant que :

Le schéma est inconditionnellement non-transférable.
Sous l'hypothèse GA-DDH dans le ROM, le schéma est fortement infalsifiable et assure la confidentialité de l'identité du signataire.
Sous l'hypothèse GAIP dans l'AGAM et le ROM, le schéma atteint des réductions serrées pour la sécurité SUF-CMA et PSI.
Performance : Le Tableau 1 du document compare CSI-SDVS aux travaux antérieurs (Sun et al. [26] et Khuc et al. [12]). CSI-SDVS offre la clé publique (512 bits) et la signature (512 bits) les plus petites parmi les schémas post-quantiques comparés, tout en maintenant une taille de clé secrète de 256 bits.

Signification

Les auteurs positionnent CSI-SDVS comme une solution pratique et sécurisée pour les signatures à vérificateur désigné post-quantiques. La signification réside dans :

Efficacité : Il atteint des paramètres compacts adaptés aux environnements à ressources limitées, répondant aux limitations de taille des précédentes propositions basées sur les réseaux ou les isogénies.
Robustesse : En fondant la sécurité sur le GAIP (une hypothèse computationnelle) dans l'AGAM, le schéma évite de dépendre d'hypothèses décisionnelles qui peuvent parfois être plus faibles ou moins intuitives dans le contexte de l'action de groupe.
Complétude : Ce travail fournit une analyse de sécurité complète couvrant les trois piliers de la SDVS (non-transférabilité, infalsifiabilité et confidentialité du signataire) dans un contexte post-quantique, comblant une lacune laissée par les schémas précédents qui soit échouaient à la non-transférabilité, soit souffraient d'inefficacité.

Le document conclut que CSI-SDVS offre un compromis équilibré entre sécurité et efficacité, ce qui en fait un candidat viable pour les applications nécessitant une authentification non transférable et résistante au quantique.