💻 computer science

From Bits to Mixed-Radix Keys: Horner Decomposition, Uniform Sampling, and the Information-Theoretic QKD Interface of the MR-OTP

Cet article établit un cadre pratique et informationnellement sécurisé pour convertir l'entropie binaire brute provenant de sources de distribution de clés quantiques en clés à base mixte uniformes pour le masque jetable à base mixte, en utilisant la méthode de Horner pour le mappage, l'échantillonnage par rejet pour éliminer le biais, ainsi que des preuves rigoureuses de sécurité et d'efficacité.

Auteurs originaux : Fabio F. G. Buono

Publié 2026-06-19

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Fabio F. G. Buono

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 : Un nouveau type de verrou « incassable »

Imaginez que vous vouliez envoyer un message secret. L'étalon-or de la confidentialité est le Masque jetable (One-Time Pad - OTP). Voyez cela comme un verrou dont la clé est une suite de nombres aléatoires aussi longue que votre message. Si la clé est véritablement aléatoire et n'est jamais réutilisée, le message est mathématiquement impossible à déchiffrer, peu importe la puissance de l'ordinateur qui tente de le casser.

Cependant, les OTP traditionnels ont un défaut : ils ne parlent que le « binaire » (0 et 1). Si vous voulez envoyer une lettre comme « A » (qui est naturellement un symbole, et non un 0 ou un 1), vous devez d'abord la traduire en binaire. Cette traduction gaspille de l'espace et est inefficace.

Ce document présente le Masque jetable à base mixte (Mixed-Radix One-Time Pad - MR-OTP). Voyez cela comme un verrou qui parle la langue native de vos données.

Si vous envoyez de l'ADN (4 lettres), le verrou utilise un dé à 4 faces.
Si vous envoyez du texte anglais (26 lettres), il utilise un dé à 26 faces.
Si vous envoyez des nombres (10 chiffres), il utilise un dé à 10 faces.

Ce document résout le problème pratique de la construction de ce verrou à l'aide d'une machine de Distribution Quantique de Clés (QKD), qui ne produit qu'un flux de 0 et de 1.

Le problème central : Le « découpage brut » de l'aléatoire

L'analogie :
Imaginez que vous avez une machine qui recrache des lancers de dés parfaits et équilibrés à 6 faces (0–5). Mais votre verrou nécessite un dé à 7 faces (0–6).

L'erreur naïve : Vous pourriez vous dire : « Je vais prendre un lancer à 6 faces, ajouter 1, et si j'obtiens un 7, je le ferai simplement boucler vers 0. »
Le problème : Cela crée un « biais ». Certains nombres (comme 0 et 1) apparaîtraient plus souvent que d'autres (comme 6). Dans le monde de la sécurité parfaite, même un infime biais est comme laisser une fente dans une porte. Cela ruine la garantie d'être « incassable ».

La solution du document :
Les auteurs proposent une règle stricte d'« Échantillonnage par rejet » (Rejection Sampling).

La machine génère un nombre.
Si le nombre rentre dans votre plage de 7 faces, vous le gardez.
S'il est trop grand (par exemple, si vous obtenez un 7 ou un 8), vous le jetez et vous réessayez.
Vous répétez l'opération jusqu'à obtenir un nombre valide.

Cela garantit que chaque nombre de 0 à 6 a exactement la même chance d'être choisi. Le document prouve que cette méthode est suffisamment efficace pour être pratique, gaspillant très peu de bits du flux quantique.

La recette secrète : « La méthode de Horner »

Comment transformer une longue chaîne de bits binaires (provenant de la machine quantique) en un ensemble spécifique de lancers de dés à bases mixtes (par exemple, un dé à 7 faces, un dé à 13 faces, un dé à 5 faces) ?

L'analogie :
Pensez à une poupée russe imbriquée ou à un ensemble d'instructions pour construire une tour.

Vers l'avant (Construction) : Vous commencez par le premier chiffre, vous le multipliez par la taille du dé suivant, vous ajoutez le chiffre suivant, vous multipliez par la taille du dé suivant, et ainsi de suite. C'est la méthode de Horner. C'est une astuce mathématique ingénieuse pour emballer différents nombres de tailles différentes dans un seul grand entier.
Vers l'arrière (Déballage) : Pour récupérer les clés, vous faites l'inverse. Vous prenez le grand nombre, vous le divisez par la taille du dernier dé pour obtenir le reste (la dernière clé), puis vous divisez le résultat par la taille du dé suivant, et ainsi de suite.

Le document prouve que ce processus d'« emballage et de déballage » est une correspondance parfaite, un pour un. C'est le pont algébrique qui vous permet de transformer un flux de 0 et de 1 en un ensemble parfait et non biaisé de clés à base mixte.

La garantie de sécurité : « Le bouclier à deux couches »

Le document aborde une question effrayante : Et si un pirate découvrait la « forme » des dés (la séquence de bases) que nous utilisons ?

Les auteurs prouvent l'existence d'un « Bouclier à deux couches » :

Couche 1 : La forme est cachée (Complexité de calcul).
Si le pirate ne sait pas que nous utilisons un dé à 7 faces ou un dé à 13 faces, il doit deviner. Le document montre que deviner la séquence des tailles de dés est incroyablement difficile, surtout si le pirate ne voit que le message chiffré (le texte chiffré) sans le texte original. En fait, s'il ne voit que le texte chiffré, il est mathématiquement impossible de connaître les tailles de dés.
Couche 2 : La clé est incassable (Théorie de l'information).
Même si le pirate découvre les tailles de dés (la « forme »), il ne peut toujours pas lire le message. Pourquoi ? Parce que la clé réelle (les nombres aléatoires lancés sur ces dés) est générée de façon inédite pour chaque message.

L'analogie : Imaginez que le pirate découvre que vous utilisez un dé à 26 faces. C'est une excellente nouvelle pour lui ! Mais il ne sait toujours pas quel nombre (A–Z) vous avez lancé pour ce message spécifique. Comme le lancer était véritablement aléatoire et n'a jamais été réutilisé, savoir la taille du dé ne lui apprend rien sur la lettre.

La conclusion majeure : La sécurité du message ne dépend pas de la lenteur du pirate à deviner les tailles de dés. Même si le pirate devine les tailles instantanément, le message reste parfaitement secret car la clé est aléatoire.

Efficacité : Économiser de l'espace

Le document souligne également un effet secondaire bénéfique.

Ancienne méthode (OTP binaire) : Pour envoyer une lettre « A » (1 sur 26), vous devez utiliser 5 bits (puisque $2^5 = 32$ ). Vous gaspillez 6 bits d'espace car 32 est plus grand que 26.
Nouvelle méthode (MR-OTP) : Vous utilisez exactement l'espace nécessaire pour 26 options.
Le résultat : Sur des millions de messages, cela économise une quantité massive de « matériel de clé » (les bits aléatoires nécessaires provenant de la machine quantique). C'est comme emballer une valise : l'ancienne méthode vous obligeait à utiliser une boîte géante pour une petite chemise ; la nouvelle méthode utilise une boîte qui s'adapte parfaitement à la chemise.

Résumé des affirmations

Comment convertir : Vous pouvez transformer des bits aléatoires quantiques en clés à base mixte en utilisant une méthode de « rejet et de nouvel essai » combinée à une astuce mathématique appelée décomposition de Horner.
Aucun biais : Cette méthode crée une clé parfaitement uniforme, ce qui est requis pour la garantie d'être « incassable ».
Sécurité de bout en bout : Tout le processus (Machine Quantique $\to$ Conversion $\to$ Chiffrement) est mathématiquement prouvé comme étant incassable.
Prêt pour l'avenir : Même si un supercalculateur du futur parvient à deviner les « tailles de dés » (la séquence de base) instantanément, les messages restent sécurisés car les clés sont fraîches et aléatoires.
Efficacité : Cela économise de l'espace par rapport aux méthodes binaires traditionnelles, particulièrement pour les langages naturels et les données biologiques.

Le document ne prétend pas qu'il s'agit d'un produit commercial prêt à la vente aujourd'hui, ni qu'il résout tous les problèmes cryptographiques. Il prouve strictement les fondements mathématiques et les algorithmes nécessaires pour faire fonctionner ce type spécifique de « sécurité parfaite » avec du matériel quantique réel.

Résumé Technique : Des Bits aux Clés à Radix Mixte

Énoncé du Problème
Le Masque Jetable à Radix Mixte (MR-OTP), introduit dans un travail précédent [1], généralise le masque jetable binaire classique aux espaces de chiffres à bases non uniformes. Il permet l'encodage natif d'alphabets de données hétérogènes (ex. séquences d'ADN, texte latin) sans conversion binaire intermédiaire tout en préservant le secret parfait de Shannon. Cependant, un déploiement pratique nécessite un mécanisme pour convertir la sortie d'entropie binaire brute d'une source de Distribution Quantique de Clés (QKD) en un tuple de clés uniformément distribué sur l'espace de clés à radix mixte.

Une approche naïve — lire $k = \lceil \log_2 P \rceil$ bits (où $P$ est le produit des bases) et réduire l'entier résultant modulo $P$ — introduit une distorsion statistique connue sous le nom de « biais de modulo ». Dans le cadre de l'information théorique, toute non-uniformité dans la distribution de la clé viole l'hypothèse du théorème de secret parfait, rendant le système non sécurisé quelle que soit l'ampleur du biais. L'article traite le défi algorithmique consistant à convertir un flux binaire uniforme en un tuple de clés à radix mixte uniforme sans introduire ce biais, tout en maintenant une sécurité informationnelle de bout en bout.

Méthodologie
L'article établit une équivalence structurelle entre les poids positionnels à radix mixte et la forme imbriquée de l'évaluation polynomiale.

Correspondance Algébrique : Les auteurs identifient la méthode de Horner et son inverse comme la dualité algébrique canonique pour cette conversion. La carte directe (évaluation de Horner) compose un tuple de chiffres en un entier unique, tandis que la carte inverse (décomposition de Horner inverse) récupère les chiffres à partir d'un entier via une réduction modulaire successive. Cela établit une bijection entre l'espace des clés $\mathcal{K}$ et l'intervalle d'entiers $\{0, \dots, P-1\}$ .
Échantillonnage par Rejet : Pour éliminer le biais de modulo, l'article propose un algorithme d'échantillonnage par rejet (Algorithme 1). L'algorithme tire $k$ bits pour former un entier $V$ . Si $V \ge P$ , l'échantillon est rejeté et le processus se répète. Si $V < P$ , la décomposition de Horner inverse est appliquée pour générer le tuple de clés.
Cadre d'Analyse de Sécurité : L'article analyse l'ensemble du pipeline (QKD $\to$ Extraction de Clé $\to$ Chiffrement MR-OTP) sur des sessions uniques et multiples. Il emploie un schéma de partitionnement par roulement de clé (key-rolling) où des blocs disjoints du flux QKD sont utilisés pour la clé et la séquence de bases de chaque session.
Taxonomie des Adversaires : L'analyse de sécurité distingue quatre classes d'adversaires : basées sur le test, algébriques, illimités et de type « ciphertext-only ». Elle sépare le « secret computationnel » (la séquence de bases $B$ ) du « secret informationnel » (le masque $K$ ).

Contributions Clés et Résultats

Échantillonnage de Clés Uniforme : L'article prouve que la réduction modulaire naïve brise le secret parfait (Proposition 3.1). Il démontre que l'échantillonnage par rejet combiné à la décomposition de Horner inverse restaure une distribution uniforme sur l'espace des clés (Théorème 3.4). Le coût binaire attendu de ce processus est borné par $2\lceil \log_2 P \rceil$ , avec un nombre attendu de cycles de rejet au maximum de 2 (Proposition 3.5).
Sécurité de Bout en Bout : La composition d'une source QKD idéale, de l'algorithme d'échantillonnage par rejet et du MR-OTP atteint le secret parfait de Shannon pour une session unique (Théorème 4.2) et à travers $N$ sessions sous un schéma de roulement de clé par partition (Théorème 6.2). Cela est valable sans hypothèses computationnelles.
Efficacité de Représentation : L'article quantifie le gain d'efficacité du MR-OTP par rapport au OTP binaire pour les alphabets naturels. En opérant dans l'espace de symboles natif, le MR-OTP élimine la « surcharge binaire » ( $\lceil \log_2 b \rceil - \log_2 b$ ) inhérente à l'encodage binaire. Par exemple, il offre une réduction de $\approx 16,9\%$ du matériel de clé pour les chiffres décimaux et de $\approx 6,0\%$ pour l'alphabet latin (Proposition 5.3).
Problème de Récupération de la Base (BRP) :
- Ciphertext-Only : L'article prouve que la récupération de la séquence de bases $B$ à partir du seul texte chiffré est informationnellement insoluble (Corollaire 8.2). Le texte chiffré fournit une information nulle sur $B$ au-delà de la contrainte $b_i > c_i$ .
- Known-Plaintext : Dans le contexte du texte clair connu, l'article établit une borne inférieure inconditionnelle sur la complexité de requête pour les adversaires basés sur le test, montrant que l'identification de $B$ nécessite au moins $|F_T| - 1$ requêtes, où $|F_T|$ reste exponentiel par rapport à la longueur du message $L$ pour un petit $T$ (Théorème 8.10).
- Invariance de la Sécurité : Un résultat central (Théorème 8.15) prouve que même si un adversaire (limité ou illimité) réussit à récupérer la séquence de bases $B$ à partir de données de texte clair connu, il obtient aucune information sur tout futur message chiffré sous une nouvelle clé. La sécurité informationnelle du masque est préservée indépendamment du statut computationnel du problème de récupération de la base.
Extraction par Lots (Batched Extraction) : L'article introduit un algorithme d'extraction par lots (Section 9) qui tire un grand entier pour générer $N$ chiffres de clé simultanément. Cela réduit le surcoût du rejet par rapport à l'échantillonnage séquentiel, approchant la limite théorique d'entropie de $\log_2 b$ bits par symbole lorsque $N \to \infty$ (Théorème 9.2).
Sources Non Idéales : L'article étend les garanties de sécurité aux sources QKD non idéales qui sont $\epsilon$ -proches de l'uniformité en distance de variation totale. Il montre que la dégradation de la sécurité de bout en bout est bornée par $2N\epsilon$ pour $N$ sessions (Théorème 10.3).

Signification et Revendications
L'article affirme fournir le fondement algorithmique complet pour le déploiement du MR-OTP avec des sources QKD tout en maintenant une sécurité strictement informationnelle. Sa signification primaire réside dans :

Résolution du Problème de Biais : Il fournit une méthode prouvable (échantillonnage par rejet + inversion de Horner) pour convertir l'entropie binaire en clés à radix mixte sans violer l'exigence d'uniformité du secret parfait.
Sécurité Temporelle Inconditionnelle : Il établit que la sécurité des messages futurs est indépendante de la difficulté computationnelle de la récupération de la séquence de bases. Même si la séquence de bases est récupérée, le système conserve le secret parfait pour les nouveaux chiffrements. Cela crée une structure de sécurité à « deux couches » où la couche computationnelle (cachant la base) et la couche informationnelle (cachant le message) sont indépendantes.
Efficacité : Il démontre que le MR-OTP est non seulement théoriquement sain mais aussi pratiquement plus efficace que le OTP binaire pour les alphabets dont la base n'est pas une puissance de deux, réduisant la consommation de clés sans sacrifier la sécurité.
Classification des Adversaires : Il sépare rigoureusement les capacités des adversaires, prouvant que la garantie informationnelle est inconditionnelle pour toutes les classes d'adversaires, tandis que les résultats de dureté computationnelle ne s'appliquent qu'à des sous-ensembles spécifiques (test vs algébrique) dans le contexte du texte clair connu.

L'article conclut en identifiant des problèmes ouverts, spécifiquement concernant la variante de roulement de clé dynamique (où la séquence de bases dépend des textes chiffrés précédents) et la dureté computationnelle en moyenne du Problème de Récupération de la Base pour les adversaires algébriques.