💻 computer science

TALUS: Threshold ML-DSA with One-Round Online Signing via Boundary Clearance and Carry Elimination

Cet article introduit TALUS, la première construction ML-DSA à seuil qui parvient à une signature en ligne en un seul tour avec plus de 99 % de succès en surmontant la barrière de l'arrondi non linéaire du schéma grâce à une Condition de Clarté de Bordure et un Cadre d'Élimination de Retenue, tout en maintenant la compatibilité des signatures standards et la sécurité.

Auteurs originaux : Leo Kao

Publié 2026-07-09

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Leo Kao

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

La vue d'ensemble : Le problème du « Coffre-fort numérique »

Imaginez que vous possédez un coffre-fort numérique (une clé privée) si précieux que vous ne voulez pas qu'une seule personne en détienne la clé. Si cette personne est piratée, le coffre est perdu. Vous divisez donc la clé en plusieurs morceaux et les distribuez à un groupe de personnes (un comité). Pour ouvrir le coffre (signer un document), un certain nombre d'entre eux (par exemple, 3 sur 5) doivent travailler ensemble.

C'est ce qu'on appelle la Signature à Seuil (Threshold Signing). C'est comme un coffre de banque qui nécessite que trois clés soient tournées simultanément.

Pendant longtemps, réaliser cela avec les nouvelles signatures numériques « résistantes au quantique » (appelées ML-DSA ou FIPS 204) a été un cauchemar. C'était lent, nécessitait de nombreux cycles d'allers-retours de messages (comme un jeu du « téléphone arabe » qui dure une éternité), ou nécessitait un « super-utilisateur » de confiance pour détenir une partie de la clé, ce qui va à l'encontre de l'objectif de partage des risques.

TALUS est une nouvelle méthode qui résout ce problème. Elle permet au comité de signer un document en un seul tour de communication, ce qui le rend aussi rapide qu'une signature par une seule personne, tout en préservant la sécurité d'une clé partagée.

Les deux obstacles principaux (et comment TALUS les franchit)

L'article identifie deux « goulots d'étranglement » spécifiques qui ont fait échouer les tentatives précédentes. TALUS utilise deux astuces ingénieuses pour les contourner.

1. Le problème de la « limite de l'arrondi » (La condition de dégagement de la limite)

L'analogie : Imaginez que vous essayez d'empiler des blocs pour atteindre une hauteur spécifique. Les règles disent : « Si votre pile est trop près du bord de la table, vous devez vérifier si un poids lourd (une partie secrète de la clé) va la renverser. » Dans les systèmes précédents, le comité devait s'arrêter, calculer ce poids lourd ensemble et vérifier si la pile était sûre. Cela prenait du temps et des étapes supplémentaires.

L'astuce de TALUS : Les auteurs ont réalisé que si vous choisissez vos blocs (le « nonce ») avec soin, vous pouvez garantir qu'ils sont loin du bord de la table.

La « Zone de Sécurité » : Si les blocs sont au milieu de la table, le poids lourd ne peut pas les renverser, peu importe sa lourdeur.
Le résultat : Si les blocs sont dans cette « Zone de Sécurité », vous n'avez pas besoin de calculer le poids lourd du tout ! Vous pouvez simplement empiler les blocs et continuer.
Le bémol : Cette « Zone de Sécurité » n'apparaît qu'environ 31,7 % du temps (environ 1 fois sur 3).
La solution : TALUS effectue la « vérification » hors ligne (avant que la signature réelle ne commence). Il cherche une configuration de blocs en « Zone de Ségecurité » en arrière-plan. Une fois qu'il en trouve une, il la sauvegarde. Lorsque le moment de la signature réelle arrive, il n'a plus qu'à récupérer les blocs pré-approuvés de la « Zone de Sécurité ». Cela élimine le besoin de la lente et lourde de calcul pendant la signature réelle.

2. Le problème de la « retenue » (Le cadre d'élimination de la retenue)

L'analogie : Imaginez que le comité essaie d'additionner ses nombres pour obtenir une somme totale. Dans les mathématiques classiques, si vous faites 7 + 8, vous obtenez 15. Le « 1 » est une retenue qui passe à la colonne suivante. Dans ce monde de signatures numériques, les mathématiques sont étranges : lorsque les morceaux sont additionnés, la « retenue » (le bit supplémentaire) est perdue ou brouillée à cause de la façon dont les nombres bouclent.

L'ancienne méthode : Pour corriger la retenue perdue, le comité devait avoir une conversation complexe en plusieurs étapes pour comprendre exactement où la retenue était passée. Cela prenait de nombreux cycles de messages.
L'astuce de TALUS : Les auteurs ont trouvé un « raccourci » mathématique (une identité spécifique impliquant le nombre 16 et le modulo). Ils ont réalisé qu'ils pouvaient calculer le total final sans jamais avoir besoin de reconstruire la somme complète et désordonnée au préalable.
Le résultat : Au lieu d'une longue conversation pour corriger la « retenue », ils utilisent une technique de masquage ingénieuse. Chaque personne envoie une version légèrement « brouillée » de son nombre. Le coordinateur (la personne qui assemble la signature) peut désembrouiller le total à l'aide d'une formule simple, éliminant ainsi le besoin de la complexe conversation de correction de la retenue.

Les deux versions de TALUS

L'article présente deux façons d'utiliser ce système, selon le degré de confiance que vous accordez à votre matériel :

TALUS-TEE (La version « Matériel de Confiance ») :
- Fonctionnement : Une personne (le Coordinateur) possède un coffre numérique spécial et inviolable (un Environnement d'Exécution Sécurisé ou TEE). Ce coffre détient la partie « poids lourd » de la clé.
- L'avantage : Comme le coffre est de confiance, le Coordinateur peut effectuer la vérification de la « Zone de Sécurité » et les calculs de « Retenue » tout seul. Les autres membres du comité ne font qu'envoyer leur pièce du puzzle.
- Le résultat : Extrêmement rapide, fonctionne même si le comité est petit (pas besoin d'une majorité de personnes honnêtes) et ne nécessite qu'un seul tour de messagerie.
TALUS-MPC (La version « Entièrement Distribuée ») :
- Fonctionnement : Personne ne fait confiance à personne. Tout le monde est égal. Ils utilisent l'astuce d'« Élimination de la Retenue » pour faire les calculs ensemble sans révéler leurs secrets.
- Le bémol : Pour que les mathématiques fonctionnent sans coffre de confiance, ils ont besoin d'un peu de temps de préparation avant que la signature ne commence (tours hors ligne) pour générer les nombres « brouillés ». De plus, pour des groupes plus larges, ils ont besoin d'une « majorité honnête » (plus de la moitié des personnes doivent être des gens de bien) pour empêcher la triche.
- Le résultat : Toujours un seul tour de messagerie lors de la signature réelle, mais cela nécessite un peu plus de préparation au préalable.

Pourquoi cela compte (Le miracle du « Un seul tour »)

Dans le monde des signatures numériques, le temps, c'est de l'argent. Chaque fois que le comité doit envoyer un message en faisant des allers-retours, cela ajoute un délai.

Les anciennes méthodes : Peuvent prendre de 3 à 29 tours de messages. Si vous signez une transaction à travers l'océan, cela peut prendre des secondes, voire des minutes.
TALUS : Prend exactement un seul tour. Le comité envoie sa pièce, et la signature est terminée.
L'analogie : Imaginez une course de relais. Les anciennes méthodes étaient comme passer le témoin 10 fois avant de franchir la ligne d'arrivée. TALUS, c'est comme si tout le monde courait sa part simultanément et franchissait la ligne ensemble.

La « Note » en haut de page (Le rappel à la réalité)

L'article inclut une note très honnête au tout début (datée de juillet 2026). Il admet qu'un chercheur nommé Guilhem Niot a trouvé des failles de sécurité dans la conception originale :

La faille de « l'Engagement » : Dans la version distribuée (MPC), la façon dont ils promettaient de garder les secrets était légèrement poreuse. Un observateur pouvait mathématiquement rétro-concevoir les clés secrètes.
La faille de « la Vérification » : Ils affirmaient ne pas avoir besoin de vérifier une condition de sécurité spécifique (la vérification $s_2$ ) à cause de leur astuce de « Zone de Sécurité », mais ils avaient tort ; cette vérification est toujours nécessaire pour une sécurité totale.

La réponse de l'article : Ils ne cachent pas cela. Ils admettent que les attaques sont correctes. Ils déclarent que l'astuce de la « Zone de Sécurité » (BCC) fonctionne toujours, mais qu'ils doivent corriger la façon dont ils verrouillent les secrets (en utilisant un type de verrou différent appelé « engagement caché » ou hiding commitment). Ils travaillent sur une version révisée.

Résumé

TALUS est une avancée majeure pour rendre les signatures numériques « résistantes au quantique » utilisables pour des groupes de personnes. Il utilise une astuce de « Zone de Sécurité » pour sauter les calculs lents et une astuce d'« Élimination de la Retenue » pour éviter les longues conversations. Cela permet à un groupe de signer un document en une seule étape, aussi rapidement qu'une seule personne. Bien que les auteurs admettent devoir corriger quelques failles de sécurité dans la version distribuée, l'idée centrale de rendre la signature à seuil rapide et efficace est une étape majeure.

Résumé Technique : TALUS – Signature ML-DSA à Seuil avec Signature en Ligne en Un Seul Tour

1. Énoncé du Problème

Le déploiement de ML-DSA (FIPS 204, basé sur CRYSTALS-Dilithium) dans un cadre à seuil est resté un problème ouvert en raison de l'étape de l'arrondi non linéaire inhérente au schéma. Contrairement aux signatures à seuil classiques (ex. FROST pour Schnorr/ECDSA) qui reposent sur l'homomorphisme additif, ML-DSA nécessite une vérification d'un résidu secondaire $r_0 - cs_2$ pour garantir que l'indice de la signature reste dans les limites. Dans un contexte de signature à seuil, la composante de la clé secrète $s_2$ est partagée entre plusieurs parties. Les approches antérieures pour gérer cette vérification de $r_0$ nécessitaient :

Un MPC coûteux : Calcul multi-partie pour évaluer $cs_2$ en ligne.
Des coordinateurs de confiance : Détention de $s_2$ dans un environnement d'exécution de confiance (TEE) ou par une partie unique de confiance.
Le remplissage par bruit (Noise Flooding) : Dégradation des paramètres pour masquer la vérification.

Ces méthodes augmentent soit la latence en ligne (plusieurs tours), soit restreignent le modèle de confiance, soit dégradent les paramètres de sécurité. De plus, un « Trilemme des Réseaux à Seuil » fondamental existe : aucun homomorphisme de groupe à partir de l'espace des nonces ne peut être simultanément dissimulant (hiding) et liant (binding), ce qui exclut les schémas de engagement homomorphes standards utilisés dans les contextes de logarithme discret.

2. Méthodologie et Innovations Clés

TALUS (Threshold Agile Lattice Unified Signatures) surmonte ces barrières en découplant la vérification de $r_0$ de la phase de signature en ligne et en résolvant le problème de l'engagement distribué via un nouveau cadre algébrique.

2.1 Condition de Libération de Limite (Boundary Clearance Condition - BCC)

Le papier identifie une propriété géométrique de l'espace d'engagement de ML-DSA. Le processus de signature implique un résidu $r_0 = \text{LowBits}(Ay)$ . Le décalage dépendant du secret $cs_2$ ne peut provoquer un franchissement de limite de l'arrondi que si $r_0$ est proche des limites modulaires ( $\pm \gamma_2$ ).

Observation : Si chaque coefficient de $r_0$ est éloigné des limites de plus de $\beta = \tau\eta$ (où $\tau$ est le poids du défi et $\eta$ la borne du secret), alors le décalage $cs_2$ ne peut pas franchir de limite.
Implication : Sous cette Condition de Libération de Limite (BCC), la partie de haut rang de l'engagement ( $w_1$ ) reste inchangée par $s_2$ , et l'indice $h$ devient entièrement calculable à partir de valeurs publiques ( $r = Az - ct_1 \cdot 2^d$ et $w_1$ ).
Probabilité : La BCC est respectée avec une probabilité $p_{BCC} \approx 31,7 \%$ par tentative de nonce.
Stratégie : TALUS effectue un prétraitement hors ligne pour générer des nonces satisfaisant la BCC. Cela filtre les « mauvais » nonces avant la phase en ligne, éliminant ainsi le besoin de calculer $cs_2$ ou de vérifier $r_0$ pendant la signature.

2.2 Cadre d'Élimination de Retenue (Carry Elimination Framework - CEF)

Même avec la BCC, les parties doivent calculer l'entrée du hachage de l'engagement $w_1 = \text{HighBits}(Ay)$ de manière distribuée. Puisque $\text{HighBits}$ n'est pas un homomorphisme de groupe, la somme des parts individuelles $w_{1,i}$ introduit des « retenues » (carries) qui doivent être résolues sans reconstruire le nonce complet $y$ .

Identité Clé : Le papier exploite l'identité modulaire $\alpha^{-1} \equiv -16 \pmod q$ (où $\alpha = 2\gamma_2$ ).
Protocole :
- TALUS-TEE : Un coordinateur de confiance (dans un TEE) détient le nonce agrégé et calcule $w_1$ directement.
- TALUS-MPC : Les parties utilisent un Protocole de Comparaison Sécurisé contre les Retenues (CSCP). Elles diffusent des décompositions masquées de leurs morceaux de nonce additifs. En utilisant des triplets de Beaver et un circuit de comparaison par arbre de préfixe, les parties calculent un bit de retenue unique $c$ et un bit de correction FIPS $\delta$ . Cela permet au coordinateur de reconstruire le $w_1$ exact sans apprendre les bits faibles (low-bits) individuels du nonce.
Efficacité : Pour $T=2$ , cela dégénère en une Fonction de Comparaison Distribuée (DCF), réduisant considérablement la communication. Pour $T \ge 3$ , cela nécessite $O(\log N)$ tours hors ligne mais reste indépendant de la phase en ligne.

3. Instanciations du Protocole

Le papier présente deux profils de déploiement :

TALUS-TEE (Environnement d'Exécution de Confiance)

Modèle : Un coordinateur détient $s_2$ et $t_0$ à l'intérieur d'un TEE. Les signataires détiennent des parts de $s_1$ .
Processus : Le TEE effectue le prétraitement hors ligne pour trouver un nonce conforme à la BCC. Il diffuse $w_1$ . Les signataires répondent avec $z_i = y_i + c \cdot s_{1,i}$ . Le TEE assemble la signature.
Confiance : Nécessite un coordinateur TEE semi-honnête ; les signataires peuvent être malveillants (arrêt identifiable).
Contraintes : Pas d'exigence de majorité honnête ( $N \ge T$ ).

TALUS-MPC (Entièrement Distribué)

Modèle : Entièrement distribué ; aucune partie ne détient $s_2$ ou le nonce agrégé.
Processus : Les parties calculent conjointement $w_1$ via le CEF lors du prétraitement hors ligne. La signature en ligne est identique au mode TEE (un tour).
Confiance : Sécurité malveillante avec Arrêt Identifiable (IA) pour $T \ge 2$ .
Contraintes : Pour $T \ge 3$ , nécessite une majorité honnête ( $N \ge 2T - 1$ ) pour empêcher un adversaire précipité (rushing adversary) d'apprendre les bits faibles du nonce (la « Barrière de la Majorité Malhonnête »). Pour $T=2$ , aucune majorité honnête n'est requise.

4. Contributions Clés

Trilemme des Réseaux à Seuil : Une preuve qu'aucun homomorphisme de groupe à partir de l'espace des nonces de réseau ne peut être simultanément dissimulant et liant. Cela établit que la résolution de la retenue est une nécessité mathématique pour les schémas de réseaux à seuil compatibles avec FIPS, et non un artefact de protocole.
Condition de Libération de Limite (BCC) : Une preuve formelle que la vérification de $r_0$ peut être contournée pour $\approx 31,7 \%$ des nonces, permettant l'élimination du calcul de $s_2$ dans la phase en ligne.
Cadre d'Élimination de Retenue (CEF) : Un protocole distribué pour calculer $\text{HighBits}(Ay)$ sans reconstruire $y$ , en utilisant les propriétés spécifiques de l'arithmétique modulaire de ML-DSA.
Signature en Ligne en Un Seul Tour : Les deux variantes atteignent un seul tour de diffusion pour la signature en ligne, égalant la latence d'une signature à partie unique et surpassant les propositions antérieures compatibles FIPS (ex. Mithril, Quorus) qui nécessitent 2 à 3 tours.
Implémentation : Une implémentation de référence en Rust couvrant les trois niveaux de sécurité FIPS 204 (ML-DSA-44, 65, 87).

5. Résultats et Performances

Taux de Succès : Le nombre attendu de tentatives de prétraitement par signature réussie est d'environ $\approx 3,15$ (en raison du taux de passage BCC de $31,7 \%$ ).
Latence (ML-DSA-65, $T=3$ ) :
- TALUS-TEE : La signature en ligne prend 0,29 ms ; le total amorti (incluant la préparation hors ligne) est de 1,52 ms.
- TALUS-MPC : La signature en ligne prend 0,68 ms ; le total amorti est de 4,09 ms.
- Comparaison : TALUS-TEE est 2,4x plus rapide que Mithril (3,6 ms) en latence en ligne. TALUS-MPC est compétitif avec Mithril mais y parvient avec un seul tour en ligne contre 3 tours pour Mithril.
Communication :
- T=2 : Coût hors ligne d'environ 5 Ko par lot (DCF).
- T $\ge$ 3 : Coût hors ligne d'environ 350 Ko par lot (dominé par CarryCompare).
- En ligne : Constant à environ 3,6 Ko par signataire, indépendant de $T$ et $N$ .
Latence Réseau : Dans les expériences distribuées (GCP), la latence de bout en bout évolue linéairement avec le RTT du réseau (ex. $\approx 350$ ms US-Europe), confirmant l'avantage du tour unique.

6. Signification et Revendications

Le papier affirme que TALUS est la première construction de signature ML-DSA à seuil qui atteint simultanément :

Pleine Compatibilité FIPS 204 : Les signatures sont vérifiables par des vérificateurs standards non modifiés.
Seuil Arbitraire : Supporte le $T$ -de- $N$ pour tout $1 \le T \le N$ (avec des contraintes de majorité honnête spécifiques pour le MPC $T \ge 3$ ).
Signature en Ligne en Un Seul Tour : Étale la latence d'une signature à partie unique, une amélioration significative par rapport aux travaux antérieurs nécessitant plusieurs tours en ligne.

Les auteurs soulignent que le « coût de la retenue » est un prix algébrique inhérent au cadre des réseaux, mais que TALUS minimise ce coût en le transférant entièrement à la phase hors ligne. Le travail démontre que la compatibilité FIPS 204 ne nécessite pas de pénalité de performance dans les contextes à seuil.

Note sur la Cryptanalyse : Le papier inclut une note (datée du 09-07-2026) reconnaissant une cryptanalyse par G. Niot. Les attaques confirment que le schéma d'engagement dans TALUS-MPC n'est pas dissimulant (récupération de $x$ à partir de $Ax$) et que le retrait de la vérification de $s_2$ introduit une fuite statistique. Les auteurs admettent ces points, retirent certaines revendications concernant la dissimulation de $As_{1,i}$ et la redondance de la vérification de $s_2$ pour la secretesse, et déclarent qu'une construction révisée utilisant des engagements véritablement dissimulants est en préparation. Ils notent que TALUS-TEE n'est pas affecté par les attaques sur l'engagement.