🔢 mathematics

Canonical Byte-String Encoding for Finite-Ring Cryptosystems

Dieses Papier stellt einen kanonischen Base-m-Codec vor, der Byte-Strings in Restklassen für Ring-basierte Kryptosysteme umwandelt, und liefert dazu eine Rust-Implementierung sowie eine in Lean 4 formalisierte und maschinell verifizierte Korrektheitsnachweise.

Ursprüngliche Autoren: Kyrylo Riabov, Serhii Kryvyi

Veröffentlicht 2026-03-25

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Kyrylo Riabov, Serhii Kryvyi

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

Stell dir vor, du möchtest eine geheime Nachricht an einen Freund schicken, aber ihr habt eine sehr seltsame Regel: Ihr dürft nur Zahlen verwenden, die kleiner als eine bestimmte Grenze sind (sagen wir, nur Zahlen von 0 bis 49). Deine Nachricht besteht aber aus Buchstaben und Bildern (Bytes), die viel größer und komplexer sind.

Das ist das Problem, das dieses Papier löst. Es beschreibt einen perfekten Übersetzer, der deine normalen Daten in diese speziellen Zahlen verwandelt und sie später wieder exakt zurückverwandelt, ohne dass auch nur ein einziges Bit verloren geht.

Hier ist die Erklärung in einfachen Worten:

1. Das Problem: Der "Zahlen-Only"-Klub

In der modernen Kryptografie (Verschlüsselung) gibt es Systeme, die nur mit Zahlen in einem bestimmten Bereich (einem "Ring") arbeiten können. Sie verstehen keine Buchstaben, keine Bilder und keine Texte.

Das Dilemma: Wenn du eine E-Mail oder ein Foto verschlüsseln willst, musst du es erst in eine Form bringen, die diese Zahlen-Maschine versteht.
Die alte Lösung: Bisher haben Leute das oft "auf die Schnelle" gelöst, mit kleinen, starren Tabellen. Das funktioniert für einfache Beispiele, aber nicht für echte, große Datenmengen.

2. Die Lösung: Der "Base-m-len" Übersetzer

Die Autoren (Kyrylo Riabov und Serhii Kryvyi) haben einen neuen, standardisierten Weg erfunden, wie man Daten in diese Zahlen verwandelt. Sie nennen es "Base-m-len".

Stell dir diesen Prozess wie einen Zug vor, der durch einen Tunnel fährt:

Der Kopf des Zuges (Der Header):
Bevor der Zug losfährt, hat er zwei wichtige Schilder an der Front:
1. Wie viele Waggons kommen? (Die Länge deiner Nachricht).
2. Wie ist der aktuelle Zustand? (Eine Art Startcode für die Maschine).
  Diese Schilder haben immer exakt die gleiche Größe, egal ob du nur ein Wort oder ein ganzes Buch verschickst. Das ist wie ein festes Formular, das immer gleich aussieht.
Der Zug selbst (Die Nutzlast):
Jetzt kommt der eigentliche Transport. Der Übersetzer nimmt deine Buchstaben, wandelt sie Schritt für Schritt in die erlaubten Zahlen um und schiebt sie hintereinander auf das Gleis.
- Der Trick: Er arbeitet nicht von vorne nach hinten, sondern von hinten nach vorne (wie beim Lesen eines Buches von der letzten Seite zur ersten). Das klingt verrückt, ist aber der Schlüssel, damit am Ende alles perfekt passt und keine Information verloren geht.
Der Abzweig (Die Dekodierung):
Wenn dein Freund die Zahlen empfängt, liest er zuerst die Schilder am Kopf. Er weiß sofort: "Ah, es kommen genau 100 Waggons."
Er zählt 100 Waggons ab, wandelt sie zurück in Buchstaben und stoppt dann sofort.
- Der Clou: Wenn jemand hinterher noch zufällige Zahlen an den Zug geklebt hat (ein "Suffix"), ignoriert dein Freund sie einfach. Er weiß genau, wo die echte Nachricht aufhört. Das macht das System sehr robust gegen Fehler oder Manipulationen am Ende der Nachricht.

3. Warum ist das so besonders? (Die Magie dahinter)

Perfekte Genauigkeit: In der Informatik gibt es oft "Verluste" beim Umrechnen. Hier ist es mathematisch bewiesen, dass niemals etwas verloren geht. Wenn du "Hallo" hineinsteckst, kommt exakt "Hallo" wieder heraus. Nicht "Halo", nicht "Hallo!".
Der Beweis (Lean 4): Die Autoren haben nicht nur Code geschrieben, sondern die Mathematik dahinter von einem Computer-Verifizierer (einem "Roboter-Mathematiker" namens Lean 4) prüfen lassen. Der Roboter hat Schritt für Schritt nachgerechnet und bestätigt: "Ja, das funktioniert immer, für jede erlaubte Zahlengrenze."
Schnelligkeit: Der Code ist so geschrieben, dass er extrem schnell läuft. Er ist viel schneller als alte Methoden, die ganze riesige Zahlen auf einmal umrechnen mussten.

4. Ein konkretes Beispiel

Stell dir vor, du möchtest das Wort "Hi" (2 Buchstaben) verschicken, und die Regel ist: "Du darfst nur Zahlen von 0 bis 49 benutzen".

Versand: Der Übersetzer schreibt zuerst auf das Schild: "2 Buchstaben". Dann wandelt er "H" und "i" in eine Kette von Zahlen um, die alle kleiner als 50 sind.
Empfang: Dein Freund sieht das Schild "2". Er liest die Zahlen, rechnet sie zurück und erhält "H" und "i".
Sicherheitsnetz: Wenn jemand daneben noch eine "99" an die Nachricht klebt, ignoriert dein Freund sie, weil er nach dem zweiten Buchstaben aufhört zu lesen.

Zusammenfassung für den Alltag

Dieses Papier liefert das fundamentale Werkzeug, damit Computer sicher und effizient Daten in die Sprache der modernen Verschlüsselung übersetzen können.

Es ist wie ein universeller Adapter für Steckdosen: Egal, welche Art von Daten (Text, Bild, Code) du hast, dieser Adapter macht sie kompatibel mit den strengsten Sicherheits-Systemen.
Es ist bewiesen sicher (mathematisch), schnell und tolerant gegenüber kleinen Fehlern am Ende der Nachricht.

Die Autoren haben diesen Adapter nicht nur gebaut, sondern auch die Bauanleitung von einem Computer auf Herz und Nieren prüfen lassen, damit wir uns darauf verlassen können.

1. Problemstellung

Ring-basierte Verschlüsselungssysteme (Ring-Mapping Cryptosystems) operieren auf algebraischen Strukturen, typischerweise Restklassenringen $\mathbb{Z}_m$ . Ein fundamentales, aber oft vernachlässigtes Problem besteht darin, wie beliebige Eingabedaten (wie UTF-8-Text oder Binärdaten) vor der eigentlichen Verschlüsselung in Elemente von $\mathbb{Z}_m$ (Residuen) umgewandelt werden müssen.

Bisherige Arbeiten behandelten diese Umwandlung oft nur ad-hoc durch handgefertigte Alphabete oder kleine Symboltabellen, was für algebraische Demonstrationen ausreicht, aber keine allgemeine, kanonische Lösung für beliebige Byte-Strings bietet. Es fehlte eine standardisierte Schicht, die Byte-Strings deterministisch, verlustfrei und selbst-delimitierend (selbsttrennend) in einen Strom von Residuen modulo $m$ übersetzt, ohne dabei die Sicherheitseigenschaften des zugrunde liegenden Kryptosystems zu beeinträchtigen.

2. Methodik: Der Base- $m$ -Len Codec

Die Autoren stellen einen neuen Codec vor, den Base- $m$ -Len Codec, der Byte-Strings der Länge $< 2^{64}$ in eine Liste von Residuen modulo $m$ abbildet. Das Design basiert auf folgenden Kernkonzepten:

Wire-Format (Übertragungsformat): Die Ausgabe besteht aus drei Teilen:
1. Länge-Präfix: Eine feste Breite von $k$ Ziffern im Basis- $m$ -System, die die Länge des ursprünglichen Byte-Strings kodiert.
2. Zustands-Präfix: Eine weitere feste Breite von $k$ Ziffern, die den finalen Zustand des Payload-Transducers kodiert.
3. Payload-Strom: Ein FIFO-Strom von Residuen, der durch eine uniforme Transformation der Eingabebytes entsteht.
Algorithmus (Encoder):
- Der Encoder verarbeitet die Eingabebytes von rechts nach links (Reverse Scan).
- Er nutzt einen Zustand $x$ , der initialisiert wird. Vor jedem Byte-Update ( $x \leftarrow 256x + b$ ) werden Ziffern emittiert, solange der Zustand einen bestimmten Schwellenwert überschreitet (Renormalisierung).
- Dies ähnelt dem Prinzip von rANS (range Asymmetric Numeral Systems) von Duda, wird hier jedoch nicht zur Entropiekodierung, sondern zur deterministischen Umwandlung genutzt.
Algorithmus (Decoder):
- Der Decoder liest zuerst die Länge ( $\ell$ ) und den initialen Zustand.
- Er rekonstruiert die Bytes durch inverse Operationen ( $x \leftarrow \lfloor x/256 \rfloor$ , Ausgabe von $x \mod 256$ ) und füllt den Zustand durch Konsumieren weiterer Residuen auf, falls er unter die Decoder-Schwelle fällt.
- Suffix-Toleranz: Da die Länge explizit kodiert ist, ignoriert der Decoder gültige Ziffern, die nach der Rekonstruktion der $\ell$ Bytes noch im Stream vorhanden sind. Dies ermöglicht das Anhängen von gültigen Suffixen ohne Fehler.

3. Wichtige Beiträge

Das Paper liefert drei wesentliche Beiträge:

Definition eines kanonischen Codecs: Einführung des Base- $m$ -Len Formats als standardisierte Schnittstelle für Finite-Ring-Protokolle, die beliebige Byte-Strings (bis $2^{64}$ Bytes) in $\mathbb{Z}_m$ abbildet.
Formale Verifikation: Die Autoren haben den Codec in Lean 4 formalisiert und maschinengeprüfte Beweise für folgende Eigenschaften erbracht:
- Exakte Dekodierung: Für jeden unterstützten Modul $m$ und jeden zulässigen Byte-String gilt: Decode(Encode(bytes)) = bytes.
- Inversion des Headers: Die festen Präfixe (Länge und Zustand) können eindeutig zurückgerechnet werden.
- Zustandsgrenzen: Der Payload-Zustand bleibt innerhalb definierter Grenzen ( $L \le x < L \cdot m$ ), was die Korrektheit sicherstellt.
- Suffix-Toleranz: Gültige Suffixe werden korrekt ignoriert.
Referenzimplementierung und Benchmarks:
- Eine Rust-Bibliothek (sym-adv-encoding) als praktische Implementierung.
- Leistungstests, die zeigen, dass der Streaming-Ansatz deutlich effizienter ist als herkömmliche Ganzzahl-Konvertierungen (BigUint) für große Eingaben.

4. Ergebnisse und Evaluation

Komplexität: Der Algorithmus hat eine lineare Zeitkomplexität $O(n)$ bezüglich der Eingabelänge $n$ und benötigt nur konstanten Arbeitspeicher ( $O(1)$ ) neben den I/O-Puffern.
Effizienz: Die Benchmarks auf einem Apple M3 Pro zeigen, dass die native Implementierung (z. B. für $m=257$ ) bei der Dekodierung von 1 KiB Daten eine Geschwindigkeit von ca. 640 MiB/s erreicht. Im Vergleich dazu liegt eine exakte BigUint-Konvertierung bei nur ca. 125 MiB/s.
Overhead: Der Overhead durch die festen Header (Länge + Zustand) hängt vom Modul $m$ ab. Für $m=257$ beträgt der Header 16 Ziffern, während der Payload-Rate fast 1 Ziffer pro Byte entspricht (nahezu verlustfreie Kompression im Sinne der Darstellung). Für kleinere Moduli (z. B. $m=25$ ) steigt der Header-Overhead signifikant an.

5. Bedeutung und Anwendungsbereiche

Sicherheitsrolle: Der Codec ist keine Sicherheitsprimitive. Er bietet keine Vertraulichkeit, Integrität oder Authentizität. Er dient ausschließlich als deterministische Serialisierungsschicht. Die Sicherheit muss durch das übergeordnete kryptografische Protokoll gewährleistet werden.
Anwendung: Der Codec ist essenziell für Projekte wie SYMPZON, die symmetrische Primitive über Integer-Ringen für Anwendungen wie Format-Erhaltende Verschlüsselung, Multi-Party-Computation (MPC), Fully Homomorphic Encryption (FHE) und Zero-Knowledge-Beweise untersuchen.
Interoperabilität: Da das Format kanonisch ist, kann es direkt mit den Transportebenen ( $\mathbb{Z}_m \leftrightarrow G_m$ ) bestehender Ring-Mapping-Kryptosysteme (wie in [2], [3] beschrieben) kombiniert werden.

Fazit

Das Paper schließt eine Lücke in der Implementierung von Ring-basierten Kryptosystemen, indem es eine rigoros bewiesene, effiziente und praktische Methode zur Umwandlung von Byte-Strings in Residuen bereitstellt. Durch die Kombination aus formaler Verifikation (Lean 4) und hochoptimierter Implementierung (Rust) bietet es eine vertrauenswürdige Basis für zukünftige kryptografische Protokolle, die auf Restklassenringen operieren.