💻 computer science

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

Diese Arbeit etabliert ein praktisches und informationstheoretisch sicheres Framework für die Konvertierung von roter binärer Entropie aus Quellen der Quantenschlüsselverteilung in uniforme Mixed-Radix-Schlüssel für das Mixed-Radix One-Time Pad unter Verwendung der Horner-Methode zur Abbildung, Rejection Sampling zur Eliminierung von Bias sowie strenger Beweise für Sicherheit und Effizienz.

Ursprüngliche Autoren: Fabio F. G. Buono

Veröffentlicht 2026-06-19

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Fabio F. G. Buono

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Eine neue Art von „unknackbarem“ Schloss

Stellen Sie sich vor, Sie möchten eine geheime Nachricht versenden. Der Goldstandard für Geheimhaltung ist das Einmalige Pad (One-Time Pad, OTP). Betrachten Sie dies als ein Schloss, bei dem der Schlüssel eine zufällige Zahlenfolge ist, die exakt so lang wie Ihre Nachricht ist. Wenn der Schlüssel wirklich zufällig ist und niemals wiederverwendet wird, ist die Nachricht mathematisch unmöglich zu knacken, egal wie leistungsstark der Computer ist, der versucht, sie zu brechen.

Herkömmliche OTPs haben jedoch einen Nachteil: Sie sprechen nur „Binär“ (0 und 1). Wenn Sie einen Buchstaben wie „A“ senden wollen (was natürlich ein Symbol und keine 0 oder 1 ist), müssen Sie ihn zuerst in Binärzahlen übersetzen. Diese Übersetzung verschwendet Platz und ist ineffizient.

Dieses Papier stellt das Mixed-Radix One-Time Pad (MR-OTP) vor. Betrachten Sie dies als ein Schloss, das die Muttersprache Ihrer Daten spricht.

Wenn Sie DNA senden (4 Buchstaben), verwendet das Schloss einen vierseitigen Würfel.
Wenn Sie englischen Text senden (26 Buchstaben), verwendet es einen 26-seitigen Würfel.
Wenn Sie Zahlen senden (10 Ziffern), verwendet es einen 10-seitigen Würfel.

Dieses Papier löst das praktische Problem, wie man dieses Schloss mit einer Quantenschlüsselverteilungs-Maschine (Quantum Key Distribution, QKD) baut, die lediglich einen Strom von 0 und 1 erzeugt.

Das Kernproblem: Der „grobe Zuschnitt“ der Zufälligkeit

Die Analogie:
Stellen Sie sich vor, Sie haben eine Maschine, die perfekte, faire Würfelwürfe eines 6-seitigen Würfels (0–5) ausspuckt. Aber Ihr Schloss erfordert einen 7-seitigen Würfel (0–6).

Der naive Fehler: Sie könnten denken: „Ich nehme einfach einen 6-seitigen Wurf, addiere eine 1, und wenn ich eine 7 erhalte, springe ich einfach zurück auf 0.“
Das Problem: Dies erzeugt eine „Verzerrung“ (Bias). Einige Zahlen (wie 0 und 1) würden häufiger vorkommen als andere (wie 6). In der Welt der perfekten Geheimhaltung ist selbst eine winzige Verzerrung wie ein Spalt in der Tür. Es ruiniert das Versprechen der „Unknackbarkeit“.

Die Lösung des Papers:
Die Autoren schlagen eine strikte „Rejection Sampling“-Regel (Verwerfendes Sampling) vor.

Die Maschine generiert eine Zahl.
Wenn die Zahl in Ihren 7-seitigen Bereich passt, behalten Sie sie.
Wenn sie zu groß ist (z. B. wenn Sie eine 7 oder 8 würfeln), werfen Sie sie weg und versuchen es erneut.
Sie wiederholen dies, bis Sie eine gültige Zahl erhalten.

Dies stellt sicher, dass jede Zahl von 0 bis 6 exakt die gleiche Chance hat, gewählt zu werden. Das Papier beweist, dass diese Methode effizient genug ist, um praktikabel zu sein, und nur sehr wenig Material aus dem Quantenstrom verschwendet.

Das Geheimrezept: „Horners Methode“

Wie verwandelt man eine lange Folge von Binärbits (aus der Quantenmaschine) in einen spezifischen Satz von Mixed-Radix-Würfeln (z. B. einen 7-seitigen, einen 13-seitigen, einen 5-seitigen)?

Die Analogie:
Denken Sie an eine verschachtelte Matroschka-Puppe oder eine Anleitung zum Bau eines Turms.

Vorwärts (Aufbau): Sie beginnen mit der ersten Ziffer, multiplizieren sie mit der Größe des nächsten Würfels, addieren die nächste Ziffer, multiplizieren mit der Größe des nächsten Würfels und so weiter. Dies wird Horners Methode genannt. Es ist ein cleverer mathematischer Trick, um verschiedene Zahlen in eine einzige große Ganzzahl zu verpacken.
Rückwärts (Entpacken): Um die Schlüssel zurückzuerhalten, machen Sie das Gegenteil. Sie nehmen die große Zahl, teilen sie durch die Größe des letzten Würfels, um den Rest zu erhalten (den letzten Schlüssel), teilen das Ergebnis dann durch die Größe des nächsten Würfels und so weiter.

Das Papier beweist, dass dieses „Verpacken und Entpacken“ eine perfekte, eins-zu-eins Übereinstimmung ist. Es ist die algebraische Brücke, die es ermöglicht, einen Strom von 0 und 1 in einen perfekten, unverzerrten Satz von Mixed-Radix-Schlüsseln zu verwandeln.

Die Sicherheitsgarantie: „Der zweischichtige Schutzschild“

Das Papier geht der beängstigenden Frage nach: Was ist, wenn ein Hacker die „Form“ der Würfel (die Basenfolge) herausfindet, die wir verwenden?

Die Autoren beweisen einen „Zwei-Schichten-Schutzschild“:

Schicht 1: Die Form ist verborgen (rechnerisch schwer zu knacken).
Wenn der Hacker nicht weiß, dass wir einen 7-seitigen oder einen 13-seitigen Würfel verwenden, muss er raten. Das Papier zeigt, dass das Raten der Sequenz der Würfelgrößen unglaublich schwierig ist, besonders wenn der Hacker nur die verschlüsselte Nachricht (den Geheimtext) sieht, ohne den ursprünglichen Text. Tatsächlich ist es mathematisch unmöglich, die Größen der Würfel zu kennen, wenn man nur den Geheimtext sieht.
Schicht 2: Der Schlüssel ist unknackbar (informationstheoretisch).
Selbst wenn der Hacker die Größen der Würfel (die „Form“) herausfindet, kann er die Nachricht immer noch nicht lesen. Warum? Weil der eigentliche Schlüssel (die zufälligen Zahlen, die auf diesen Würfeln gewürfelt wurden) für jede Nachricht neu generiert wird.
- Die Analogy: Stellen Sie sich vor, der Hacker findet heraus, dass Sie einen 26-seitigen Würfel verwenden. Das ist großartig für ihn! Aber er weiß immer noch nicht, welche Zahl (A–Z) Sie für diese spezifische Nachricht gewürfelt haben. Da der Wurf wirklich zufällig war und niemals wiederverwendet wurde, sagt das Wissen über die Größe des Würfels nichts über den Buchstaben aus.

Das große Fazit: Die Sicherheit der Nachricht hängt nicht davon ab, dass der Hacker zu langsam ist, um die Würfelgrößen zu erraten. Selbst wenn er die Größen sofort errät, bleibt die Nachricht perfekt geheim, weil der Schlüssel zufällig ist.

Effizienz: Platz sparen

Das Papier weist auch auf einen angenehmen Nebeneffekt hin.

Alter Weg (Binäres OTP): Um einen Buchstaben „A“ (1 von 26) zu senden, müssen Sie 5 Bits verwenden (da $2^5 = 32$ ). Sie verschwenden 6 Bits Platz, da 32 größer als 26 ist.
Neuer Weg (MR-OTP): Sie nutzen exakt den Platz, der für 26 Optionen benötigt wird.
Das Ergebnis: Über Millionen von Nachrichten hinweg spart dies eine enorme Menge an „Schlüsselmaterial“ (den zufälligen Bits, die von der Quantenmaschine benötigt werden). Es ist wie das Packen eines Koffers: Der alte Weg zwang einen dazu, einen riesigen Karton für ein kleines Hemd zu benutzen; der neue Weg nutzt einen Karton, der genau auf das Hemd passt.

Zusammenfassung der Behauptungen

Wie man konvertiert: Man kann Quanten-Zufallsbits unter Verwendung einer „Ablehnungs-und-Wiederholungs“-Methode kombiniert mit einem mathematischen Trick namens Horners Dekomposition in Mixed-Radix-Schlüssel umwandeln.
Keine Verzerrung: Diese Methode erzeugt einen perfekt gleichmäßigen Schlüssel, der für die „Unknackbarkeit“ erforderlich ist.
End-to-End-Sicherheit: Der gesamte Prozess (Quantenmaschine $\to$ Konvertierung $\to$ Verschlüsselung) ist mathematisch als unknackbar bewiesen.
Zukunftssicher: Selbst wenn ein Supercomputer in der Zukunft die Würfelgrößen (die Basenfolge) augenblicklich erraten kann, bleiben die Nachrichten sicher, da die Schlüssel frisch und zufällig sind.
Effizienz: Es spart im Vergleich zu traditionellen binären Methoden Platz, insbesondere bei natürlichen Sprachen und biologischen Daten.

Das Papier behauptet nicht, dass dies ein kommerzielles Produkt ist, das heute verkaufsbereit ist, und es behauptet auch nicht, alle kryptographischen Probleme zu lösen. Es beweist streng die mathematischen Grundlagen und Algorithmen, die erforderlich sind, um diese spezifische Art der „perfekten Geheimhaltung“ mit realer Quantenhardware funktionsfähig zu machen.

Technische Zusammenfassung: Von Bits zu gemischtradix-basierten Schlüsseln

Problemstellung
Das Mixed-Radix One-Time Pad (MR-OTP), das in einer vorangegangenen Arbeit [1] eingeführt wurde, verallgemeinert das klassische binäre One-Time Pad auf Digitalsysteme mit nicht-uniformen Basen. Es ermöglicht die native Kodierung heterogener Alphabeten (z. B. DNA-Sequenzen, lateinischer Text), ohne eine zwischenzeitliche Binärkonvertierung, während die Shannon’sche perfekte Geheimhaltung gewahrt bleibt. Eine praktische Implementierung erfordert jedoch einen Mechanismus, um den rohen binären Entropie-Output einer Quantenschlüsselerzeugung (QKD-Quelle) in ein Schlüssel-Tupel zu konvertieren, das gleichverteilt über den gemischtradix-basierten Schlüsselraum ist.

Ein naiver Ansatz – das Einlesen von $k = \lceil \log_2 P \rceil$ Bits (wobei $P$ das Produkt der Basen ist) und die Reduktion des resultierenden Integers modulo $P$ – führt zu einer statistischen Verzerrung, die als „Modulo-Bias“ bekannt ist. Im informationstheoretischen Kontext verletzt jede Nicht-Uniformität in der Schlüsselverteilung die Hypothese des Theorems der perfekten Geheimhaltung, was das System unsicher macht, unabhängig von der Größenordnung des Bias. Die Arbeit adressiert die algorithmische Herausforderung, einen uniformen binären Strom in ein uniformes gemischtradix-basiertes Schlüssel-Tupel zu konvertieren, ohne dabei diesen Bias einzuführen und gleichzeitig die durchgängige informationstheoretische Sicherheit zu gewährleisten.

Methodik
Die Arbeit etabliert eine strukturelle Äquivalenz zwischen gemischtradix-basierten Positionsgewichten und der verschachtelten Form der Polynomauswertung.

Algebraische Korrespondenz: Die Autoren identifizieren die Horner-Methode und deren Inverse als die kanonische algebraische Dualität für diese Konvertierung. Die Vorwärtsabbildung (Horner-Auswertung) setzt ein Digitus-Tupel zu einer einzelnen Ganzzahl zusammen, während die Rückwärtsabbildung (Inverse Horner-Dekomposition) die Digiti aus einer Ganzzahl mittels sukzessiver Modulo-Reduktion zurückgewinnt. Dies etabliert eine Bijektion zwischen dem Schlüsselraum $\mathcal{K}$ und dem Intervall der Ganzzahlen $\{0, \dots, P-1\}$ .
Rejection Sampling (Verwerfendes Sampling): Um den Modulo-Bias zu eliminieren, schlägt die Arbeit einen Rejection-Sampling-Algorithmus vor (Algorithmus 1). Der Algorithmus zieht $k$ Bits, um eine Ganzzahl $V$ zu bilden. Wenn $V \ge P$ , wird die Stichprobe verworfen und der Prozess wiederholt. Wenn $V < P$ , wird die inverse Horner-Dekomposition angewendet, um das Schlüssel-Tupel zu generieren.
Sicherheitsanalyse-Framework: Die Arbeit analysiert die vollständige Pipeline (QKD $\to$ Schlüsselextraktion $\to$ MR-OTP-Verschlüsselung) über einzelne sowie mehrere Sitzungen hinweg. Sie verwendet ein Partitionierungs-Key-Rolling-Schema, bei dem disjunkte Blöcke des QKD-Stroms für den Schlüssel und die Basensequenz jeder Sitzung verwendet werden.
Adversary-Taxonomie: Die Sicherheitsanalyse unterscheidet zwischen vier Adversary-Klassen: testing-basiert, algebraisch, unbeschränkt (unbounded) und ciphertext-only. Sie trennt das „komputationale Geheimnis“ (die Basensequenz $B$ ) vom „informationstheoretischen Geheimnis“ (das Pad $K$ ).

Wesentliche Beiträge und Ergebnisse

Uniforme Schlüssel-Sampling: Die Arbeit beweist, dass naive Modulo-Reduktion die perfekte Geheimhaltung bricht (Proposition 3.1). Sie demonstriert, dass Rejection Sampling in Kombination mit der inversen Horner-Dekomposition eine Gleichverteilung über den Schlüsselraum wiederherstellt (Theorem 3.4). Die erwarteten Bit-Kosten dieses Prozesses sind auf $2\lceil \log_2 P \rceil$ begrenzt, wobei die erwartete Anzahl der Rejection-Runden höchstens 2 beträgt (Proposition 3.5).
End-to-End-Sicherheit: Die Komposition einer idealen QKD-Quelle, des Rejection-Sampling-Algorithmus und des MR-OTP erreicht die Shannon’sche perfekte Geheimhaltung für eine einzelne Sitzung (Theorem 4.2) sowie über $N$ Sitzungen unter einem Partition-Key-Rolling-Schema (Theorem 6.2). Dies gilt ohne komputationale Annahmen.
Repräsentations-Effizienz: Die Arbeit quantifiziert den Effizienzgewinn von MR-OTP gegenüber binärem OTP für natürliche Alphabete. Durch den Betrieb im nativen Symbolraum eliminiert MR-OTP den inhärenten „Binär-Overhead“ ( $\lceil \log_2 b \rceil - \log_2 b$ ) der binären Kodierung. Beispielsweise bietet es eine Reduktion des Schlüsselmaterials um $\approx 16,9\%$ für Dezimalziffern und $\approx 6,0\%$ für das lateinische Alphabet (Proposition 5.3).
Base Recovery Problem (BRP):
- Ciphertext-Only: Die Arbeit beweist, dass die Rekonstruktion der Basensequenz $B$ allein aus dem Ciphertext informationstheoretisch unlösbar ist (Corollary 8.2). Der Ciphertext liefert außer der Beschränkung $b_i > c_i$ keinerlei Information über $B$ .
- Known-Plaintext: Im Known-Plaintext-Szenario etabliert die Arbeit eine bedingungslose untere Schranke für die Query-Komplexität für testing-basierte Adversaries und zeigt, dass die Identifizierung von $B$ mindestens $|F_T| - 1$ Abfragen erfordert, wobei $|F_T|$ für kleine $T$ exponentiell in der Nachrichtenlänge $L$ bleibt (Theorem 8.10).
- Invarianz der Sicherheit: Ein zentrales Ergebnis (Theorem 8.15) beweist, dass selbst wenn ein Adversary (bounded oder unbounded) die Basensequenz $B$ erfolgreich aus Known-Plaintext-Daten rekonstruiert, er keinerlei Information über eine zukünftige Nachricht erhält, die unter einem frischen Schlüssel verschlüsselt wurde. Die informationstheoretische Sicherheit des Pads bleibt unabhängig von der komputationalen Komplexität des Base-Recovery-Problems gewahrt.
Batched Extraction (Gebündelte Extraktion): Die Arbeit führt einen Algorithmus zur gebündelten Schlüsselextraktion ein (Abschnitt 9), der eine einzige große Ganzzahl zieht, um $N$ Schlüssel-Digiti simultan zu generieren. Dies reduziert den Rejection-Overhead im Vergleich zum sequentiellen Sampling und nähert sich dem theoretischen Entropie-Limit von $\log_2 b$ Bits pro Symbol an, wenn $N \to \infty$ (Theorem 9.2).
Nicht-ideale Quellen: Die Arbeit erweitert die Sicherheitsgarantien auf nicht-ideale QKD-Quellen, die in der Total Variation Distance $\epsilon$ -nah an einer Gleichverteilung liegen. Sie zeigt, dass die Verschlechterung der End-to-End-Sicherheit über $N$ Sitzungen durch $2N\epsilon$ begrenzt ist (Theorem 10.3).

Bedeutung und Ansprüche
Die Arbeit beansprucht, das vollständige algorithmische Fundament für den Einsatz von MR-OTP mit QKD-Quellen bereitzustellen, während die strikte informationstheoretische Sicherheit gewahrt bleibt. Ihre primäre Bedeutung liegt in:

Lösung des Bias-Problems: Sie liefert eine nachweislich korrekte Methode (Rejection Sampling + Horner-Inversion), um binäre Entropie in gemischtradix-basierte Schlüssel zu konvertieren, ohne die Uniformitätsanforderung der perfekten Geheimhaltung zu verletzen.
Unbedingte temporale Sicherheit: Sie stellt fest, dass die Sicherheit zukünftiger Nachrichten unabhängig von der komputationalen Schwierigkeit der Rekonstruktion der Basensequenz ist. Selbst wenn die Basensequenz rekonstruiert wird, behält das System die perfekte Geheimhaltung für frische Verschlüsselungen bei. Dies schafft eine „Zwei-Schichten“-Sicherheitsstruktur, in der die komputationale Schicht (Verbergen der Basis) und die informationstheoretische Schicht (Verbergen der Nachricht) unabhängig voneinander sind.
Effizienz: Sie demonstriert, dass MR-OTP nicht nur theoretisch fundiert, sondern für Nicht-Zweierpotenz-Alphabete auch praktisch effizienter als binäres OTP ist, wodurch der Schlüsselverbrauch ohne Verlust an Sicherheit reduziert wird.
Adversary-Klassifizierung: Sie trennt rigoros zwischen den Fähigkeiten der Adversaries und beweist, dass die informationstheoretische Garantie bedingungslos für alle Adversary-Klassen gilt, während die Ergebnisse zur komputationalen Härte nur für spezifische Teilmengen (Testing vs. Algebraisch) im Known-Plaintext-Szenario gelten.

Die Arbeit schließt mit der Identifizierung offener Probleme, insbesondere hinsichtlich der dynamischen Key-Rolling-Variante (bei der die Basensequenz von vorangegangenen Ciphertexts abhängt) und der Average-Case-Computational-Härte des Base-Recovery-Problems für algebraische Adversaries.