💻 computer science

Post-Quantum Sanitizable Signatures from McEliece-Based Chameleon Hashing

Cet article présente le premier schéma de signature sanitizable post-quantique transparent basé sur le code de Goppa, qui utilise le hachage chameau de McEliece et le décodage de Patterson pour permettre des modifications autorisées tout en garantissant l'indistinguabilité des signatures et la sécurité contre la falsification.

Auteurs originaux : Shahzad Ahmad, Stefan Rass, Zahra Seyedi

Publié 2026-02-25

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shahzad Ahmad, Stefan Rass, Zahra Seyedi

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

🌟 Le Concept de Base : Un Document "Modifiable" mais "Inviolable"

Imaginez que vous avez un document officiel très important (comme un dossier médical ou un contrat) signé par un médecin ou un notaire. Ce document est scellé avec un sceau numérique (une signature) qui garantit qu'aucun mot n'a été changé.

Le problème ? Parfois, il faut modifier ce document pour des raisons légales ou de confidentialité (par exemple, effacer le nom d'un patient pour le rendre anonyme, ou changer une date d'expiration).

Le problème classique : Si vous changez un seul mot, le sceau se brise et le document devient invalide.
La solution de ce papier : Ils ont inventé un sceau spécial qui permet à une personne de confiance (le "sanitiseur") de changer certaines parties du document (comme le nom) sans casser le sceau, tout en garantissant que le reste du document (le diagnostic médical) reste figé à jamais.

🛡️ Pourquoi est-ce si important ? (La menace des ordinateurs quantiques)

Aujourd'hui, la plupart des signatures numériques reposent sur des mathématiques complexes (comme la factorisation de grands nombres) qui sont sûres pour nos ordinateurs actuels. Mais les chercheurs craignent l'arrivée des ordinateurs quantiques, des machines du futur si puissantes qu'elles pourraient casser ces verrous en quelques secondes (comme un marteau sur une vitre).

Ce papier propose une solution résistante aux ordinateurs quantiques (Post-Quantum). Au lieu d'utiliser les vieux verrous, ils utilisent une nouvelle technologie basée sur les codes correcteurs d'erreurs (une méthode utilisée depuis 45 ans pour envoyer des messages clairs à travers le bruit, comme dans les sondes spatiales). C'est un verrou qui résiste même aux marteaux quantiques.

🎨 L'Analogie du "Tampon Magique" (La fonction de hachage Caméléon)

Le cœur de leur invention est une sorte de tampon magique appelé "Fonction de Hachage Caméléon".

Le Sceau Ordinaire : Imaginez un sceau de cire. Si vous essayez de changer le mot "100€" en "1000€", la cire se fissure. Tout le monde voit que c'est falsifié.
Le Sceau Caméléon : Imaginez un sceau fait d'une matière spéciale.
- Le Signataire (le médecin) met le sceau sur le document.
- Le Sanitiseur (l'administrateur) possède une clé secrète (un "piège" mathématique).
- Avec cette clé, le sanitiseur peut changer le mot "100€" en "1000€" et recréer instantanément un sceau parfaitement identique à l'original.
- Pour un observateur extérieur, le document avec le nouveau mot et le nouveau sceau semble exactement comme s'il avait été signé par le médecin à l'origine. Personne ne peut dire : "Tiens, quelqu'un a modifié ce document !"

🔐 Comment ça marche ? (L'histoire du Code Goppa et du Décodage)

Pour créer ce tampon magique, les auteurs utilisent une idée ingénieuse basée sur les mathématiques des codes :

Le Défi : Trouver une erreur dans un message brouillé est normalement très difficile (c'est comme chercher une aiguille dans une botte de foin). C'est ce qu'on appelle le "problème du décodage de syndrome".
Le Piège : Seul le sanitiseur possède la "carte au trésor" (la clé secrète du code Goppa) qui lui permet de trouver cette erreur très rapidement, comme s'il avait un aimant pour l'aiguille.
La Sécurité : Si un pirate essaie de changer le document sans la clé, il doit trouver cette aiguille dans le foin sans aide. Avec les paramètres choisis (basés sur le standard NIST), cela prendrait des milliers d'années, même avec un super-ordinateur.

✨ La Grande Innovation : La "Transparence Parfaite"

C'est le point le plus brillant de l'article.
Dans les systèmes précédents, on pouvait parfois deviner si un document avait été modifié ou non en analysant les statistiques de la signature (comme détecter une légère différence dans la texture de la cire).

Ici, les auteurs ont imposé une règle stricte : le signataire original doit choisir ses "mots de passe" (les randomiseurs) d'une manière très précise (avec un poids exact).

Résultat : La signature modifiée par le sanitiseur est mathématiquement identique à une signature fraîche.
Analogie : C'est comme si le sanitiseur utilisait exactement la même encre, le même pinceau et la même main que le signataire original. Même un expert ne peut pas dire qui a touché le document. C'est ce qu'ils appellent la transparence parfaite.

🚀 À quoi ça sert dans la vraie vie ?

Dossiers Médicaux : Un hôpital peut publier des statistiques sur une épidémie en effaçant les noms des patients, tout en gardant la signature du médecin qui atteste que les données sont vraies.
Certificats Numériques : Une autorité peut changer la date d'expiration d'un certificat de sécurité sans avoir à le réémettre entièrement, ce qui est plus rapide et plus sûr.
Chaîne d'Approvisionnement : Une entreprise peut cacher le prix d'un produit dans un contrat public tout en prouvant que la qualité du produit est certifiée.

⚖️ Les Petits Bémols (Pour être honnête)

Comme toute nouvelle technologie, il y a des compromis :

Taille des clés : Les "clés" (les fichiers de sécurité) sont un peu plus grosses que les systèmes classiques (environ 650 Ko, contre quelques Ko aujourd'hui). C'est comme si votre passeport numérique était un peu plus épais, mais il est beaucoup plus résistant.
Modèle théorique : La sécurité repose sur une hypothèse mathématique appelée "Oracle Aléatoire" (un modèle idéal). C'est une pratique courante, mais les chercheurs aimeraient un jour prouver la sécurité sans cette hypothèse.

🏁 En Résumé

Ce papier nous donne le premier sceau numérique inviolable par les ordinateurs quantiques qui permet de modifier certains détails d'un document sans briser la confiance. C'est comme donner à un gardien de musée le pouvoir de changer l'étiquette d'un tableau pour le rendre anonyme, tout en garantissant à tous les visiteurs que le tableau lui-même n'a jamais été touché ni falsifié.

C'est une avancée majeure pour protéger nos données à long terme dans un futur où les ordinateurs seront beaucoup plus puissants qu'aujourd'hui.

1. Problématique et Contexte

Les signatures de type « sanitizable » (ou signatures modifiables) permettent à un signataire de déléguer à un « assainisseur » (sanitizer) le droit de modifier certaines parties d'un document signé sans invalider la signature globale, tout en garantissant que le reste du contenu reste immuable. Ces schémas sont cruciaux pour des applications comme la protection des données médicales (anonymisation), la mise à jour de certificats X.509 ou l'anonymisation de documents de la chaîne d'approvisionnement.

Cependant, les schémas existants reposent sur des primitives cryptographiques classiques (RSA, logarithmes discrets, couplages) qui sont vulnérables aux attaques des ordinateurs quantiques via l'algorithme de Shor. Bien que des solutions basées sur les réseaux (lattices) aient récemment émergé, elles nécessitent le modèle de l'oracle aléatoire (ROM) et n'offrent pas toujours une transparence parfaite. À ce jour, aucune solution post-quantique basée sur les codes (code-based) n'avait été réalisée pour ce type de signature.

L'objectif de cet article est de combler ce vide en proposant le premier schéma de signature sanitizable post-quantique, transparent et basé sur la cryptographie à base de codes (spécifiquement le système de McEliece).

2. Méthodologie et Construction

L'approche proposée repose sur la construction d'une fonction de hachage caméléon (chameleon hash) dérivée du système de cryptographie McEliece (utilisant des codes de Goppa).

A. Hachage Caméléon de McEliece (ROM)

La fonction de hachage est définie comme suit :
$H_{pk}(m, r) = (G(m) \oplus r) \cdot H_{pub}^T$
Où :

$G$ est une fonction de hachage modélisée comme un oracle aléatoire (implémentée avec SHA-3).
$r$ est un vecteur aléatoire (randomizer) de poids de Hamming $t$ .
$H_{pub}$ est la matrice de parité publique du code de Goppa.

Innovation clé : Sans l'oracle aléatoire $G$ , une fonction linéaire simple serait vulnérable à des collisions triviales. L'utilisation de $G$ (prétraitement du message) rend la recherche de collisions impossible sans la clé secrète (trapdoor), car elle nécessite d'inverser $G$ , ce qui est computationnellement impossible.

B. Mécanisme de Sanitisation (Trapdoor)

L'assainisseur possède la clé secrète du code de Goppa (la trapdoor). Lorsqu'il doit modifier un bloc de message autorisé ( $m \to m'$ ), il doit trouver un nouveau randomizer $r'$ tel que le hachage reste identique.

Cela se traduit par la résolution d'un problème de décodage de syndrome : trouver un vecteur d'erreur $f$ de poids $\le t$ tel que $f \cdot H_{sec}^T = s_{target}$ .
L'assainisseur utilise l'algorithme de décodage de Patterson pour résoudre ce problème efficacement en $O(n \cdot t)$ opérations.

C. Schéma de Signature Complet

Le schéma utilise deux hachages caméléons indépendants (un pour les blocs immuables, un pour les blocs modifiables) chaînés sur les blocs du message. Le digest final est signé par une signature classique (basée sur Dilithium2 pour la sécurité post-quantique, bien que le cœur du schéma soit McEliece).

3. Contributions Clés

Premier schéma post-quantique basé sur les codes : C'est la première réalisation d'une signature sanitizable transparente utilisant des hypothèses de cryptographie à base de codes (McEliece), offrant une alternative aux schémas basés sur les réseaux (lattices).
Transparence Parfaite ( $\delta = 0$ ) : L'article démontre que si le signataire contraint le choix des randomizers à un poids de Hamming exactement égal à $t$ , la distribution des signatures fraîches est statistiquement identique à celle des signatures assainies. Cela élimine toute possibilité de distinguer l'origine de la signature (signataire ou assainisseur), offrant une garantie de confidentialité parfaite.
Preuves de Sécurité Rigoureuses :
- Résistance aux collisions : Prouvée dans le modèle de l'oracle aléatoire (ROM) en se réduisant au problème de décodage de syndrome (Syndrome Decoding - SD), un problème NP-complet.
- Immuabilité et Non-falsification (EUF-CMA) : Prouvées en montrant qu'attaquer l'immuabilité ou falsifier une signature équivaut à résoudre le problème de décodage de syndrome ou à casser la signature de base.
Implémentation et Benchmarks : Un prototype en Python a été développé et testé avec les paramètres de sécurité de la catégorie 1 du NIST (Classic-McEliece : $n=3488, k=2720, t=64$ ).

4. Résultats et Performances

Taille des clés et signatures :
- Taille de la clé publique : $\approx 655,3$ Ko (dominée par les deux matrices de parité publiques).
- Taille de la signature (pour 10 blocs) : $\approx 6,75$ Ko.
- Comparé à la solution basée sur les réseaux (Clermont et al.), la clé publique est plus petite (655 Ko vs 850 Ko), bien que la signature soit légèrement plus grande en raison des vecteurs de randomisation.
Temps de calcul :
- Le temps théorique pour le décodage de Patterson (opération de sanitisation) est d'environ 8 ms par bloc modifié pour les paramètres de sécurité NIST Cat. 1.
- La signature et la vérification croissent linéairement avec le nombre de blocs $L$ .
Transparence :
- Sans contrainte de poids : distance statistique $\delta \approx 0,0187$ .
- Avec contrainte de poids $t$ : distance statistique $\delta = 0$ (Transparence parfaite).

5. Signification et Limites

Signification :
Ce travail établit un nouveau standard pour la confidentialité des données à long terme dans un monde post-quantique. En s'appuyant sur le problème du décodage de syndrome (étudié depuis plus de 45 ans), il offre une base de sécurité plus conservative et mature que les hypothèses récentes basées sur les réseaux (Module-LWE). La capacité à atteindre une transparence parfaite est un avantage majeur pour la vie privée, rendant les modifications cryptographiquement indétectables.

Limites :

Modèle de l'Oracle Aléatoire (ROM) : La résistance aux collisions du hachage caméléon repose sur le ROM. Aucune construction basée sur les codes n'est actuellement connue pour être sûre dans le modèle standard pour cette propriété.
Taille des clés : Bien que compétitive par rapport aux schémas basés sur les réseaux, la clé publique de 655 Ko reste importante pour des environnements à ressources très limitées (IoT).
Absence de « Policy Hiding » : Le masque d'admissibilité (quels blocs sont modifiables) est public.
Absence de « Exposure-freeness » : Un observateur voyant plusieurs collisions pourrait potentiellement extraire des informations sur la trapdoor (bien que cela nécessite de nombreuses opérations).

Perspectives futures :
Les auteurs suggèrent l'utilisation de codes MDPC/LDPC pour réduire la taille des clés, l'implémentation de versions à temps constant du décodeur de Patterson pour résister aux canaux auxiliaires, et la recherche de preuves de sécurité dans le modèle standard.

En conclusion, cet article propose une solution robuste, théoriquement prouvée et pratiquement réalisable pour la gestion sécurisée et modifiable de documents sensibles à l'ère post-quantique.