💻 computer science

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

Dit artikel vestigt een praktisch en informatie-theoretisch veilig kader voor het converteren van ruwe binaire entropie van Quantum Key Distribution-bronnen naar uniforme mixed-radix sleutels voor de Mixed-Radix One-Time Pad door gebruik te maken van de methode van Horner voor mapping, rejection sampling om bias te elimineren, en strikte bewijzen van veiligheid en efficiëntie.

Oorspronkelijke auteurs: Fabio F. G. Buono

Gepubliceerd 2026-06-19

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Fabio F. G. Buono

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: Een Nieuw Soort "Onkraakbaar" Slot

Stel je voor dat je een geheim bericht wilt versturen. De gouden standaard voor geheimhouding is de One-Time Pad (OTP). Zie dit als een slot waarbij de sleutel een willekeurige reeks getallen is die precies even lang is als je bericht. Als de sleutel echt willekeurig is en nooit wordt hergebruikt, is het bericht wiskundig gezien onmogelijk te kraken, ongeacht hoe krachtig de computer die het probeert te breken ook is.

Traditionele OTP's hebben echter een gebrek: ze spreken alleen "Binair" (0'en en 1'en). Als je een letter zoals "A" wilt versturen (wat van nature een symbool is, geen 0 of 1), moet je deze eerst naar binair vertalen. Deze vertaling verspilt ruimte en is inefficiënt.

Dit artikel introduceert de Mixed-Radix One-Time Pad (MR-OTP). Zie dit als een slot dat de natuurlijke taal van je gegevens spreekt.

Als je DNA verstuurt (4 letters), gebruikt het slot een 4-zijdige dobbelsteen.
Als je Engelse tekst verstuurt (26 letters), gebruikt het een 26-zijdige dobbelsteen.
Als je getallen verstuurt (10 cijfers), gebruikt het een 10-zijdige dobbelsteen.

Dit artikel lost het praktische probleem op van hoe je dit slot bouwt met een Quantum Key Distribution (QKD) machine, die alleen een stroom van 0'en en 1'en produceert.

Het Kernprobleem: De "Ruwe Snede" van Willekeur

De Analogie:
Stel je voor dat je een machine hebt die perfecte, eerlijke worpen van een 6-zijdige dobbelsteen (0–5) uitspuugt. Maar jouw slot vereist een 7-zijdige dobbelsteen (0–6).

De Naïeve Fout: Je zou kunnen denken: "Ik neem gewoon een 6-zijdige worp, tel er een 1 bij op, en als ik een 7 krijg, laat ik het weer teruglopen naar 0."
Het Probleem: Dit creëert een "bias" (afwijking). Sommige getallen (zoals 0 en 1) zouden vaker voorkomen dan andere (zoals 6). In de wereld van perfecte geheimhouding is zelfs een kleine afwijking als een kier in de deur. Het ruïneert de garantie van "onkraakbaarheid".

De Oplossing van het Artikel:
De auteurs stellen een strikte "Rejection Sampling"-regel voor.

De machine genereert een getal.
Als het getal binnen jouw 7-zijdige bereik past, houd je het.
Als het te groot is (bijv. je gooit een 7 of 8), gooi je het weg en probeer je het opnieuw.
Je herhaalt dit totdat je een geldig getal krijgt.

Dit zorgt ervoor dat elk getal van 0 tot 6 een exact gelijke kans heeft om gekozen te worden. Het artikel bewijst dat deze methode efficiënt genoeg is om praktisch bruikbaar te zijn, waarbij er zeer weinig bits van de quantumstroom verloren gaan.

Het Geheime Ingrediënt: "Horner's Methode"

Hoe verander je een lange reeks binaire bits (van de quantummachine) in een specifieke set mixed-radix dobbelsteenworpen (bijv. één 7-zijdige, één 13-zijdige, één 5-zijdige)?

De Analogie:
Denk aan een set Russische matroesjka-poppen of een reeks instructies voor het bouwen van een toren.

Vooruit (Bouwen): Je begint met het eerste cijfer, vermenigvuldigt het met de grootte van de volgende dobbelsteen, tel het volgende cijfer erbij op, vermenigvuldig met de volgende dobbelsteen grootte, enzovoort. Dit wordt Horner's Methode genoemd. Het is een slimme wiskundige truc om verschillende getalformaten in één groot getal te verpakken.
Achteruit (Uitpakken): Om de sleutels terug te krijgen, doe je het omgekeerde. Je neemt het grote getal, deelt het door de grootte van de laatste dobbelsteen om de restwaarde te krijgen (de laatste sleutel), deelt het resultaat vervolgens door de grootte van de volgende dobbelsteen, enzovoort.

Het artikel bewijst dat dit "verpakken en uitpakken" een perfecte, één-op-één overeenkomst is. Het is de algebraïsche brug die je in staat stelt om een stroom van 0'en en 1'en om te zetten in een perfecte, ongeëvenaarde set mixed-radix sleutels.

De Veiligheidsgarantie: "Het Twee-Lagen Schild"

Het artikel behandelt een angstaanjagende vraag: Wat als een hacker de "vorm" van de dobbelstenen (de basissequentie) ontdekt die wij gebruiken?

De auteurs bewijzen een "Twee-Lagen Schild":

Laag 1: De Vorm is Verborgen (Computationeel Moeilijk).
Als de hacker niet weet dat we een 7-zijdige of een 13-zijdige dobbelsteen gebruiken, moet hij gokken. Het artikel laat zien dat het raden van de sequentie van dobbelsteenformaten ongelooflijk moeilijk is, vooral als de hacker alleen de versleutelde tekst (ciphertext) ziet zonder de originele tekst. Sterker nog, als ze alleen de ciphertext zien, is het wiskundig onmogelijk om de grootte van de dobbelstenen überhaupt te weten.
Laag 2: De Sleutel is Onkraakbaar (Informatie-theoretisch).
Zelfs als de hacker de dobbelsteenformaten (de "vorm") wel ontdekt, kunnen ze de boodschap nog steeds niet lezen. Waarom? Omdat de werkelijke sleutel (de willekeurige getallen die op die dobbelstenen worden gegooid) voor elke boodschap opnieuw wordt gegenereerd.
- De Analogie: Stel je voor dat de hacker ontdekt dat je een 26-zijdige dobbelsteen gebruikt. Dat is geweldig voor hen! Maar ze weten nog steeds niet welk nummer (A–Z) je voor deze specifieke boodschap hebt gegooid. Omdat de worp echt willekeurig was en nooit wordt hergebruikt, zegt het weten van de grootte van de dobbelsteen hen niets over de letter.

De Grote Conclusie: De veiligheid van het bericht hangt niet af van het feit of de hacker te traag is om de dobbelsteenformaten te raden. Zelfs als de hacker de formaten direct raadt, blijft het bericht perfect geheim omdat de sleutel willekeurig is.

Efficiëntie: Ruimte Besparen

Het artikel wijst ook op een prettig neveneffect.

Oude Manier (Binaire OTP): Om een letter "A" (1 van de 26) te versturen, heb je 5 bits nodig (omdat $2^5 = 32$ ). Je verspilt 6 bits aan ruimte omdat 32 groter is dan 26.
Nieuwe Manier (MR-OTP): Je gebruikt exact de ruimte die nodig is voor 26 opties.
Het Resultaat: Over miljoenen berichten heen bespaart dit een enorme hoeveelheid "sleutelmateriaal" (de willekeurige bits die nodig zijn van de quantummachine). Het is als het inpakken van een koffer: de oude manier dwong je om een gigantische doos voor een klein T-shirt te gebruiken; de nieuwe manier gebruikt een doos die precies past bij het T-shirt.

Samenvatting van Claims

Hoe te converteren: Je kunt quantum willekeurige bits omzetten in mixed-radix sleutels met behruik van een "reject and retry"-methode gecombineerd met een wiskundige truc genaamd Horner's decompositie.
Geen Afwijking: Deze methode creëert een perfect uniforme sleutel, wat vereist is voor de "onkraakbare" garantie.
Einde-tot-Einde Veiligheid: Het hele proces (Quantum Machine $\to$ Conversie $\to$ Versleuteling) is wiskundig bewezen onkraakbaar.
Toekomstbestendig: Zelfs als een supercomputer in de toekomst de "dobbelsteenformaten" (de basissequentie) direct kan raden, blijven de berichten veilig omdat de sleutels vers en willekeurig zijn.
Efficiëntie: Het bespaart ruimte vergeleken met traditionele binaire methoden, vooral voor natuurlijke talen en biologische gegevens.

Het artikel beweert niet dat dit een commercieel product is dat vandaag de dag klaar is voor verkoop, noch beweert het alle cryptografische problemen op te lossen. Het bewijst strikt de wiskundige fundamenten en algoritmen die nodig zijn om dit specifieke type "perfecte geheimhouding" werkend te krijgen met echte quantumhardware.

Technische Samenvatting: Van Bits naar Mixed-Radix Sleutels

Probleemstelling
De Mixed-Radix One-Time Pad (MR-OTP), geïntroduceerd in een voorafgaand werk [1], generaliseert de klassieke binaire One-Time Pad naar digit-ruimtes met niet-uniforme bases. Het maakt het inheemse coderen van heterogene alfabetten (bijv. DNA-sequenties, Latijnse tekst) mogelijk zonder tussenliggende binaire conversie, terwijl de Shannon-perfecte geheimhouding behouden blijft. Een praktische implementatie vereist echter een mechanisme om de ruwe binaire entropie-output van een Quantum Key Distribution (QKD) bron te converteren naar een sleutel-tuple die uniform verdeeld is over de mixed-radix sleutelruimte.

Een naïeve benadering—het lezen van $k = \lceil \log_2 P \rceil$ bits (waarbij $P$ het product van de bases is) en het reduceren van het resulterende geheel getal modulo $P$ —introduceert een statistische vervorming die bekend staat als "modulo-bias". In de informatie-theoretische setting schendt elke niet-uniformiteit in de sleutelverdeling de hypothese van de stelling van perfecte geheimhouding, wat het systeem onveilig maakt, ongeacht de omvang van de bias. Het artikel behandelt de algoritmische uitdaging om een uniforme binaire stroom te converteren naar een uniforme mixed-radix sleutel-tuple zonder deze bias te introduceren, terwijl de end-to-end informatie-theoretische veiligheid behouden blijft.

Methodologie
Het artikel stelt een structurele equivalentie vast tussen mixed-radix positiewichten en de geneste vorm van polynoom-evaluatie.

Algebraïsche Correspondentie: De auteurs identificeren Horner's methode en de inverse ervan als de canonieke algebraïsche dualiteit voor deze conversie. De voorwaartse kaart (Horner-evaluatie) componeert een digit-tuple tot een enkel geheel getal, terwijl de inverse kaart (Inverse Horner-decompositie) de digits herstelt uit een geheel getal via opeenvolgende modulaire reductie. Dit vestigt een bijstelling tussen de sleutelruimte $\mathcal{K}$ en het gehele getal-interval $\{0, \dots, P-1\}$ .
Rejection Sampling: Om modulo-bias te elimineren, stelt het artikel een rejection sampling-algoritme voor (Algoritme 1). Het algoritme trekt $k$ bits om een geheel getal $V$ te vormen. Als $V \ge P$ , wordt de steekproef verworpen en wordt het proces herhaald. Als $V < P$ , wordt de inverse Horner-decompositie toegepast om de sleutel-tuple te genereren.
Veiligheidsanalyse Framework: Het artikel analyseert de volledige pijplijn (QKD $\to$ Key Extraction $\to$ MR-OTP Encryption) over enkelvoudige en meerdere sessies. Het gebruikt een partitie key-rolling schema waarbij disjuncte blokken van de QKD-stroom worden gebruikt voor de sleutel en de base-sequentie van elke sessie.
Adversary Taxonomie: De veiligheidsanalyse onderscheidt vier klassen van tegenstanders (adversaries): testing-based, algebraic, unbounded, en ciphertext-only. Het scheidt de "computationele geheimen" (de base-sequentie $B$ ) van het "informatie-theoretische geheim" (de pad $K$ ).

Kernbijdragen en Resultaten

Uniforme Sleutel Sampling: Het artikel bewijst dat naïeve modulaire reductie perfecte geheimhouding doorbreekt (Propositie 3.1). Het demonstreert dat rejection sampling in combinatie met inverse Horner-decompositie een uniforme verdeling over de sleutelruimte herstelt (Theorem 3.4). De verwachte bit-kosten van dit proces zijn begrensd door $2\lceil \log_2 P \rceil$ , met een verwacht aantal rejection-rondes van maximaal 2 (Propositie 3.5).
End-to-End Veiligheid: De compositie van een ideale QKD-bron, het rejection sampling-algoritme en de MR-OTP bereikt Shannon-perfecte geheimhouding voor een enkele sessie (Theorem 4.2) en over $N$ sessies onder een partitie key-rolling schema (Theorem 6.2). Dit houdt stand zonder computationele aannames.
Representatieve Efficiëntie: Het artikel kwantificeert de efficiëntiewinst van MR-OTP ten opzichte van binaire OTP voor natuurlijke alfabetten. Door te opereren in de inheemse symboolruimte, elimineert MR-OTP de "binaire overhead" ( $\lceil \log_2 b \rceil - \log_2 b$ ) die inherent is aan binaire codering. Bijvoorbeeld, het biedt een reductie van $\approx 16,9\%$ in sleutelmateriaal voor decimale cijfers en $\approx 6,0\%$ voor het Latijnse alfabet (Propositie 5.3).
Base Recovery Problem (BRP):
- Ciphertext-Only: Het artikel bewijst dat het herstellen van de base-sequentie $B$ uit enkel de ciphertext informatie-theoretisch onoplosbaar is (Corollary 8.2). De ciphertext biedt nul informatie over $B$ buiten de beperking $b_i > c_i$ .
- Known-Plaintext: In de known-plaintext setting stelt het artikel een onvoorwaardelijke ondergrens vast op de query-complexiteit voor testing-based tegenstanders, waarbij het identificeren van $B$ ten minste $|F_T| - 1$ queries vereist, waarbij $|F_T|$ exponentieel blijft in de berichtlengte $L$ voor kleine $T$ (Theorem 8.11).
- Invariantie van Veiligheid: Een centraal resultaat (Theorem 8.15) bewijst dat zelfs als een tegenstander (bounded of unbounded) er succesvol in slaagt de base-sequentie $B$ te herstellen uit known-plaintext data, zij nul informatie verkrijgt over elk toekomstig bericht dat onder een verse sleutel wordt versleuteld. De informatie-theoretische veiligheid van de pad blijft behouden, ongeacht de computationele status van het base recovery probleem.
Batched Extraction: Het artikel introduceert een batched key extraction algoritme (Sectie 9) dat één groot geheel getal trekt om $N$ sleutel-digits gelijktijdig te genereren. Dit vermindert de rejection-overhead vergeleken met sequentiële sampling, waarbij de theoretische entropie-limiet van $\log_2 b$ bits per symbool wordt benaderd als $N \to \infty$ (Theorem 9.2).
Niet-Ideale Bronnen: Het artikel breidt de veiligheidsgaranties uit naar niet-ideale QKD-bronnen die $\epsilon$ -dicht bij uniform zijn in totale variatieafstand. Het toont aan dat de end-to-end veiligheidsdegradatie begrensd is door $2N\epsilon$ voor $N$ sessies (Theorem 10.3).

Significantie en Claims
Het artikel beweert het volledige algoritmische fundament te bieden voor de inzet van de MR-OTP met QKD-bronnen, terwijl strikte informatie-theoretische veiligheid wordt gewaarborgd. De primaire significantie ligt in:

Oplossen van het Bias-Probleem: Het biedt een bewezen correcte methode (rejection sampling + Horner-inversie) om binaire entropie te converteren naar mixed-radix sleutels zonder de uniformiteitseis van perfecte geheimhouding te schenden.
Onvoorwaardelijke Temporele Veiligheid: Het stelt vast dat de veiligheid van toekomstige berichten onafhankelijk is van de computationele moeilijkheid van het herstellen van de base-sequentie. Zelfs als de base-sequentie wordt hersteld, behoudt het systeem perfecte geheimhouding voor verse encrypties. Dit creëert een "twee-lagen" veiligheidsstructuur waarbij de computationele laag (het verbergen van de base) en de informatie-theoretische laag (het verbergen van het bericht) onafhankelijk zijn.
Efficiëntie: Het demonstreert dat MR-OTP niet alleen theoretisch solide is, maar ook praktisch efficiënter dan binaire OTP voor niet-machts-van-twee alfabetten, waardoor het sleutelverbruik wordt verminderd zonder de veiligheid op te offeren.
Adversary Classificatie: Het classificeert de mogelijkheden van tegenstanders rigoureus, waarbij bewezen wordt dat de informatie-theoretische garantie onvoorwaardelijk geldt voor alle klassen van tegenstanders, terwijl de computationele hardheid-resultaten alleen van toepassing zijn op specifieke subsets (testing vs. algebraic) in de known-plaintext setting.

Het artikel sluit af door openstaande problemen te identificeren, specifiek met betrekking tot de dynamische key-rolling variant (waarbij de base-sequentie afhankelijk is van voorgaande ciphertexts) en de gemiddelde-geval computationele hardheid van het Base Recovery Problem voor algebraïsche tegenstanders.