🔢 mathematics

Canonical Byte-String Encoding for Finite-Ring Cryptosystems

Cet article présente un codec canonique basé sur rANS pour mapper des chaînes d'octets vers des résidus modulo $m$ dans les cryptosystèmes à anneaux finis, en validant sa correction et ses bornes de complexité via une implémentation Rust et une preuve formelle en Lean 4.

Auteurs originaux : Kyrylo Riabov, Serhii Kryvyi

Publié 2026-03-25

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Kyrylo Riabov, Serhii Kryvyi

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 voulez envoyer un message secret à un ami, mais vous avez un problème : votre ami ne parle que le langage des "chiffres restes" (des nombres qui tournent en rond, comme les heures sur une montre), tandis que vous écrivez en "bytes" (le langage standard des ordinateurs, comme du texte ou des images).

Ce papier est comme un traducteur universel et infaillible conçu pour résoudre exactement ce problème. Voici l'explication simple de ce que les auteurs (Kyrylo et Serhii) ont créé :

1. Le Problème : Deux langues qui ne se comprennent pas

Dans le monde de la cryptographie moderne (les systèmes qui protègent vos données), on utilise souvent des mathématiques basées sur des "anneaux finis" (des cercles de nombres). Pour chiffrer un message, il faut d'abord transformer votre texte en une liste de chiffres qui rentrent dans ce cercle.
Avant ce papier, les gens inventaient leurs propres traductions à la main, un peu comme si chaque personne dessinait sa propre carte pour traverser une rivière. C'était pratique pour de petits exemples, mais pas fiable pour de vraies applications.

2. La Solution : Le "Traducteur Magique" (Base-m-len)

Les auteurs ont créé un protocole standardisé, qu'ils appellent Base-m-len. C'est une machine à traduire qui transforme n'importe quel fichier (texte, image, vidéo) en une liste de chiffres "restes" propres à la cryptographie.

Voici comment cela fonctionne, avec une analogie :

L'Enveloppe (Le Format de Fil)

Imaginez que vous envoyez un colis. Ce traducteur ne jette pas juste les chiffres au hasard. Il met tout dans une enveloppe très structurée avec trois compartiments :

L'étiquette de longueur (Le Header) : Avant même de commencer à traduire le message, le traducteur écrit sur l'enveloppe : "Il y a exactement 100 mots à l'intérieur". C'est comme un compteur qui dit au destinataire : "Arrête-toi après 100 mots".
Le mot de passe de fin (L'état final) : Il écrit aussi un code spécial qui dit : "Voici où nous étions sur le cercle de nombres quand nous avons fini". C'est une garantie que la traduction s'est bien terminée.
Le message (La charge utile) : Ensuite, il traduit le vrai message, mot par mot, en chiffres restes.

La Magie de la Traduction (Le Codec)

Le cœur du système utilise une technique inspirée de la compression de données (appelée rANS), mais simplifiée pour être déterministe.

Analogie du Moulin à Café : Imaginez que vous mettez des grains de café (vos bytes) dans un moulin. Le moulin tourne, écrase les grains et les transforme en une poudre fine (les chiffres restes).
Ce qui est génial ici, c'est que le moulin est réversible. Si vous avez la poudre, le mot de passe de fin et l'étiquette de longueur, vous pouvez remettre le moulin en marche à l'envers pour retrouver exactement les mêmes grains de café, sans aucune erreur.

3. Pourquoi c'est génial ? (Les Super-Pouvoirs)

La tolérance aux "bruits" : Imaginez que quelqu'un colle un petit autocollant à la fin de votre enveloppe. Comme le traducteur sait exactement combien de mots il y a (grâce à l'étiquette de longueur), il lit son message, s'arrête, et ignore l'autocollant. Il ne panique pas, il ne se trompe pas. C'est ce qu'on appelle la "tolérance aux suffixes".
La preuve mathématique (Le Sceau de Garantie) : Les auteurs ne se contentent pas de dire "ça marche". Ils ont utilisé un logiciel appelé Lean 4 pour écrire une preuve mathématique formelle. C'est comme si un juge suprême avait vérifié chaque étape de la recette et confirmé : "Oui, pour n'importe quel message de moins de 264 octets, la traduction est parfaite et réversible". C'est une garantie absolue, pas juste une supposition.
La rapidité : Ils ont aussi codé cela en langage informatique (Rust) et ont prouvé que c'est très rapide, même pour de gros fichiers.

4. En résumé, à quoi ça sert ?

Ce papier fournit la brique de base manquante pour construire des systèmes de sécurité très avancés.

Si vous voulez faire de la cryptographie sur des anneaux (pour le calcul privé, les votes électroniques, ou les données sensibles), vous avez besoin de transformer vos données en chiffres restes.
Ce papier dit : "Utilisez ce traducteur précis. Il est rapide, il a été prouvé mathématiquement, et il ne se trompera jamais."

C'est un peu comme si les auteurs avaient créé le standard ISO pour transformer du texte en chiffres magiques, en s'assurant que tout le monde utilise la même règle du jeu pour que les communications soient sûres et fiables.

1. Problématique

Les cryptosystèmes basés sur les anneaux (Ring-mapping cryptosystems), tels que ceux utilisés dans les primitives de chiffrement préservant le format, le calcul multipartite ou le chiffrement totalement homomorphe, nécessitent que les messages soient représentés comme des éléments de l'anneau $\mathbb{Z}_m$ (entiers modulo $m$ ) avant toute opération d'encryption ou de décryption.

Le problème central identifié par les auteurs est l'absence d'une couche de représentation standardisée et canonique pour convertir des données arbitraires (texte UTF-8 ou données binaires) en flux de résidus dans $\mathbb{Z}_m$ . Les travaux antérieurs utilisaient souvent des alphabets sur mesure ou des tables de symboles fixes, ce qui est insuffisant pour une généralisation robuste. Il est nécessaire de définir une méthode déterministe, auto-délimitante et vérifiable formellement pour mapper des chaînes d'octets vers des listes de résidus, tout en garantissant une décodage exact et une tolérance aux suffixes valides.

2. Méthodologie : Le Codec Base- $m$ -Len

Les auteurs proposent un codec nommé base- $m$ -len, conçu comme une couche de représentation plutôt qu'un compresseur. Ce codec transforme une chaîne d'octets de longueur inférieure à $2^{64}$ en un flux de résidus modulo $m$ .

Structure du format de transmission (Wire Format)

Le flux codé est composé de trois parties concaténées :

Préfixe de longueur (Fixed-width length prefix) : La longueur de la chaîne d'octets originale est encodée sous forme de $k$ chiffres en base $m$ (little-endian), où $k$ est le plus petit entier tel que $m^k \ge 2^{64}$ .
Préfixe d'état (State prefix) : L'état final du processus de transduction est encodé de manière similaire avec $k$ chiffres.
Charge utile (Payload) : Un flux de chiffres en base $m$ produit par une transduction uniforme des octets.

Algorithme d'encodage et de décodage

Encodage : L'encodeur parcourt les octets d'entrée de droite à gauche. Il maintient un état interne $x$ initialisé à une borne inférieure ( $L$ ). Pour chaque octet $b$ , il met à jour l'état selon la formule $x \leftarrow 256x + b$ . Tant que $x$ dépasse un seuil d'encodeur, il émet le chiffre $x \mod m$ et met à jour $x \leftarrow \lfloor x/m \rfloor$ . Le flux émis est ensuite inversé pour être lu de gauche à droite.
Décodage : Le décodeur lit d'abord le préfixe de longueur pour connaître le nombre d'octets à reconstruire. Il lit ensuite le préfixe d'état initial. Il reconstruit les octets un par un en utilisant l'opération inverse ( $x \leftarrow \lfloor x/256 \rfloor$ pour obtenir l'octet, puis $x \leftarrow x \cdot m + d$ en consommant les chiffres du flux de charge utile).
Tolérance aux suffixes : Le décodeur s'arrête exactement après avoir reconstruit le nombre d'octets déclaré. Tout suffixe valide supplémentaire est ignoré, ce qui permet une robustesse dans les flux de données concaténés.

3. Contributions Clés

L'article apporte trois contributions majeures :

Définition d'un codec canonique : Introduction d'un format de fil (wire format) paramétré par le module $m$ , garantissant une représentation unique et auto-délimitante pour les chaînes d'octets de longueur $< 2^{64}$ .
Garanties de correction formelle : Utilisation de la preuve assistée par ordinateur (Lean 4) pour établir rigoureusement :
- L'inversion exacte des préfixes de largeur fixe.
- Les bornes de l'état de la charge utile (garantissant qu'il reste dans une fenêtre de normalisation).
- La correction de bout en bout du flux (roundtrip correctness).
- La tolérance aux suffixes valides.
Implémentation de référence et benchmarks : Fourniture d'une bibliothèque Rust (sym-adv-encoding) et d'une suite de benchmarks de performance, démontrant la viabilité pratique de l'approche.

4. Résultats et Évaluation

Preuves Formelles (Lean 4)

La formalisation dans Lean 4 couvre l'ensemble du spectre théorique :

Inversion des préfixes : Prouvé que tout entier $< 2^{64}$ peut être encodé et décodé sans perte avec $k$ chiffres.
Bornes de l'état : Prouvé que l'état interne reste toujours dans l'intervalle $[L, L \cdot m)$ , assurant que le processus ne diverge pas.
Correction du flux : Le théorème principal affirme que pour tout module supporté et toute chaîne admissible, Decode(Encode(bytes)) = bytes. De plus, Decode(Encode(bytes) ++ suffix) = bytes.

Performance et Complexité

Complexité : L'encodage et le décodage sont linéaires $O(n)$ par rapport à la longueur des données, avec un état de travail constant $O(1)$ .
Coût de représentation : Le nombre de chiffres de charge utile par octet est asymptotiquement $\log_m(256)$ $lo g_{m} (256)$ .
- Pour $m=257$ , le taux est proche de 1 chiffre par octet (0,9993).
- Pour $m=25$ , le taux est d'environ 1,723 chiffres par octet.
Benchmarks (M3 Pro) : Les implémentations natives en Rust surpassent significativement les conversions de radix basées sur BigUint (entiers arbitraires).
- Exemple : Pour 1 KiB avec $m=65$ , l'encodage natif atteint 163,6 MiB/s contre 25,2 MiB/s pour la méthode BigUint.
- Le décodage est encore plus rapide, atteignant 485,9 MiB/s pour $m=65$ .

5. Signification et Limites

Importance

Ce travail comble un vide critique dans les protocoles cryptographiques modernes basés sur les anneaux finis. En fournissant une couche de représentation standardisée, vérifiée formellement et performante, il permet d'intégrer plus facilement des données arbitraires dans des schémas de chiffrement homomorphe ou de calcul multipartite. Le format est conçu pour s'interfacer directement avec les couches de transport $\mathbb{Z}_m \leftrightarrow G_m$ utilisées dans des projets comme SYMPZON.

Limites et Considérations de Sécurité

Les auteurs précisent que ce codec n'est pas une primitive cryptographique en soi :

Il est déterministe et public : il n'offre ni confidentialité, ni intégrité, ni authenticité.
Il expose la longueur exacte des données (nécessitant un remplissage/padding au niveau du protocole supérieur si le masquage de longueur est requis).
La preuve formelle porte sur la spécification abstraite, pas sur l'implémentation Rust ligne par ligne (les problèmes de gestion de la mémoire ou de parsing bas niveau restent des responsabilités d'implémentation).

En conclusion, le codec base- $m$ -len offre une solution robuste, mathématiquement prouvée et performante pour la sérialisation de données dans les systèmes cryptographiques à anneaux finis, éliminant le besoin de tables de symboles ad hoc et facilitant l'interopérabilité.