🔢 mathematics

Canonical Byte-String Encoding for Finite-Ring Cryptosystems

Dit paper introduceert een canonieke base-m codec voor het omzetten van byte-strings naar restklassen in eindige ringen, gebaseerd op een aangepast rANS-systeem, en ondersteunt deze met een Rust-implementatie, een in Lean 4 formeel geverifieerde specificatie en prestatiebenchmarks.

Oorspronkelijke auteurs: Kyrylo Riabov, Serhii Kryvyi

Gepubliceerd 2026-03-25

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Kyrylo Riabov, Serhii Kryvyi

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

Stel je voor dat je een geheim bericht wilt versturen naar een vriend die alleen in een heel speciale taal kan lezen: de taal van de "Resten" (wiskundig gezien: getallen modulo $m$ ). In deze wereld kunnen ze geen gewone letters of cijfers begrijpen; ze kunnen alleen werken met getallen die kleiner zijn dan een bepaald getal $m$ (bijvoorbeeld 50 of 257).

Het probleem is: hoe vertaal je een gewoon bericht (zoals "Hallo" of een bestand) naar deze vreemde taal, zodat je het later weer perfect kunt terugvertalen? En hoe weet je precies waar het bericht ophoudt?

Dit paper introduceert een slimme oplossing, een soort talenvertaler genaamd base- $m$ -len. Hier is hoe het werkt, uitgelegd in alledaagse termen:

1. De Verpakking: Een Strakke Doos met Labels

Stel je voor dat je een pakketje (jouw bericht) moet versturen. De ontvanger heeft een speciale sleutel (de modulus $m$ ) om het te openen. Maar voordat je het pakketje in de sleutelgaten past, moet je het eerst inpakken volgens een heel strikt recept.

Deze verpakking bestaat uit drie delen:

Het Label met de Lengte (De Header): Allereerst schrijf je op een label precies hoeveel letters er in het pakket zitten. Dit label is altijd even groot, ongeacht of je 1 letter of 1000 letters stuurt. Het is als een barcode die altijd even lang is, zodat de ontvanger precies weet hoe lang hij moet zoeken.
Het Startpunt (De State): Vervolgens geef je een startnummer mee. Dit is een soort "reset-knop" voor de vertaler, zodat hij weet waar hij moet beginnen met het omzetten.
Het Pakketje zelf (De Payload): Pas daarna komt het eigenlijke bericht, maar dan omgezet in de taal van de ontvanger (de "resten").

2. Hoe de Vertaling Werkt: De "Tandwiel" Methode

Hoe zet je nu een letter om in een "rest"?
Stel je voor dat je een reeks tandwielen hebt.

Bij het versturen (Encoderen): Je neemt je tekst van achter naar voren. Voor elke letter draai je het tandwiel een stukje (vermenigvuldig je met 256 en tel je de letterwaarde op). Zodra het tandwiel te zwaar wordt (te groot voor de ontvanger), schud je er een klein getaltje uit (de "rest") en leg je dat in het pakketje. Je herhaalt dit totdat je alle letters hebt verwerkt.
Bij het ontvangen (Decoderen): De ontvanger kijkt eerst naar het label om te weten hoeveel letters hij moet verwachten. Hij pakt het startnummer en begint het proces in omgekeerde richting. Hij haalt de letters er één voor één uit, totdat het aantal letters overeenkomt met wat er op het label staat.

3. De Magische Eigenschappen

Wat maakt deze methode zo speciaal?

Onverbrekelijk (Exact): Als je het pakketje opent, krijg je precies hetzelfde terug als je erin hebt gestopt. Geen enkele letter gaat verloren. De auteurs hebben dit niet alleen met de hand gecontroleerd, maar met een computerprogramma (Lean 4) dat wiskundig heeft bewezen dat het altijd werkt, zolang je binnen de regels speelt.
Ongevoelig voor "Aanhangsels": Stel dat er per ongeluk nog wat extra getallen achter je pakketje worden geplakt (bijvoorbeeld door een storing in de lijn). Omdat het label precies zegt waar het pakketje ophoudt, negeert de ontvanger die extra getallen gewoon. Hij stopt precies op het juiste moment. Het is alsof je een brief leest en stopt zodra je het woord "Einde" ziet, ook al staan er nog wat krabbels achteraan.
Snel en Efficiënt: De methode is zo ontworpen dat hij niet traag wordt als je grote bestanden stuurt. Het is als een lopende band: hoe langer de band, hoe langer het duurt, maar de snelheid per item blijft gelijk.

4. Waarom is dit belangrijk?

In de wereld van moderne cryptografie (zoals het beveiligen van internetverkeer of het berekenen van gegevens zonder ze te ontsleutelen) werken computers vaak met deze "Resten-talen". Tot nu toe moesten programmeurs zelf uitvinden hoe ze tekst omzetten, wat vaak leidde tot fouten of inefficiënte systemen.

De auteurs van dit paper zeggen eigenlijk: "Stop met het zelf uitvinden. Gebruik deze standaard, geteste en bewezen vertaler."

Ze hebben:

De theorie: Een wiskundig bewijs dat het werkt.
De code: Een werkend programma (in de programmeertaal Rust) dat je kunt gebruiken.
De tests: Bewijs dat het snel genoeg is voor echte toepassingen.

Samenvattend

Dit paper presenteert een standaardverpakking voor digitale berichten in een wereld die alleen met "restgetallen" kan werken. Het zorgt ervoor dat je berichten veilig, snel en foutloos van de ene wereld (onze tekst) naar de andere (de wiskundige wereld) kunnen reizen, met een label dat precies aangeeft waar het eindigt, zodat er nooit iets misgaat.

Titel: Canonieke Byte-String Encoding voor Eindige-Ring Cryptosystemen

Auteurs: Kyrylo Riabov en Serhii Kryvyi (Universiteit van Kiev)
Datum: 25 maart 2026

1. Het Probleem

Ring-mapping cryptosystemen (zoals die gebruikt worden in format-preserving encryption, multi-party computation en fully homomorphic encryption) vereisen dat berichten worden weergegeven als elementen van de ring $\mathbb{Z}_m$ (integers modulo $m$ ) voordat encryptie of decryptie kan plaatsvinden.

Huidige implementaties hanteren vaak handgemaakte alfabetten of kleine, vaste symboltabellen om dit te realiseren. Dit is voldoende voor theoretische illustraties, maar lost het algemene probleem niet op van hoe willekeurige UTF-8 tekst of binaire data correct en canoniek moet worden vertaald naar restklassen (residuen) in $\mathbb{Z}_m$ . Er ontbreekt een gestandaardiseerde, bewezen laag voor deze vertaling ("byte-to-residue layer") die onafhankelijk werkt van de specifieke cryptografische primitieven.

2. Methodologie: De Base- $m$ -len Codec

Het paper introduceert een nieuwe codec genaamd base- $m$ -len. Dit is een canonieke afbeelding van byte-strings (lengte $< 2^{64}$ ) naar lijsten van restklassen modulo $m$ . De aanpak is gebaseerd op de principes van range Asymmetric Numeral Systems (rANS) van Duda, maar aangepast voor deterministische, niet-compressieve doeleinden.

De Wire Format (Berichtstructuur):
Het gecodeerde bericht bestaat uit drie delen:

Lengte-prefix: Een vaste breedte ( $k$ ) weergave van de byte-lengte van het originele bericht in basis $m$ .
State-prefix: Een vaste breedte ( $k$ ) weergave van de eindtoestand van de payload.
Payload-stream: Een stroom van restklassen gegenereerd door een uniforme transductie van de bytes.

Het Encoderingsproces:

De encoder scant de input-bytes van rechts naar links.
Het onderhoudt een interne toestand $x$ . Voor elke byte $b$ wordt de toestand vermenigvuldigd met 256 en wordt de byte opgeteld ( $x \leftarrow 256x + b$ ).
Zolang de toestand $x$ een bepaalde drempelwaarde (encoder threshold) overschrijdt, worden er restklassen ( $x \mod m$ ) uitgezonden en wordt $x$ gedeeld door $m$ .
Na het verwerken van alle bytes worden de uitgezonden digits in omgekeerde volgorde (FIFO) geplaatst, zodat de decoder ze van links naar rechts kan lezen.

Het Decoderingsproces:

De decoder leest eerst de lengte-prefix om te weten hoeveel bytes er verwacht worden.
Vervolgens leest hij de state-prefix om de initiële toestand te herstellen.
Hij reconstructeert de bytes door de payload-digits te verwerken en de toestand te renormaliseren.
Belangrijk: De decoder stopt precies na het reconstrueren van de aangegeven lengte. Eventuele geldige suffix-digits (extra data achteraan) worden genegeerd, wat tolerantie biedt voor "padding" of aangehechte data.

3. Belangrijkste Bijdragen

Canonieke Codec Definitie: Een modulus-geparametriseerde, deterministische byte-naar-residue codec met een vast formaat (wire format) dat geschikt is voor eindige-ring protocollen.
Formele Correctheid: Het paper biedt wiskundige garanties voor exacte decoding, tolerantie voor suffixen en de omkeerbaarheid van de vaste breedte headers voor alle ondersteunde moduli en byte-strings kleiner dan $2^{64}$ .
Implementatie en Verificatie:
- Een Rust-bibliotheek (sym-adv-encoding) voor praktische toepassing.
- Een Lean 4 formalisering met machine-gecontroleerde bewijzen. Dit bewijst dat de abstracte specificatie correct is, inclusief de grenzen van de payload-toestand en de correctheid van de stream.

4. Resultaten en Evaluatie

Correctheid: De Lean 4 formalisering bewijst dat voor elke ondersteunde modulus $m$ en elke geldige byte-string, Decode(Encode(bytes)) exact bytes teruggeeft. Ook wordt bewezen dat extra suffix-digits geen invloed hebben op het resultaat.
Complexiteit: De codec werkt in lineaire tijd $O(n)$ met een constante werkruimte (buiten de buffers).
Performance (Benchmarks):
- Tests op een Apple M3 Pro tonen aan dat de native implementatie aanzienlijk sneller is dan baselines die gebruikmaken van grote gehele getallen (BigUint radix-conversie).
- Bijvoorbeeld: Het coderen van 1 KiB data met $m=257$ gaat ongeveer 10x sneller in de native Rust-implementatie (217 MiB/s) dan met BigUint (21.7 MiB/s).
- De decodering is nog sneller (tot 640 MiB/s voor $m=257$ ).
Efficiëntie: Voor grotere moduli (bijv. $m=257$ ) nadert het aantal benodigde digits per byte de waarde 1, wat betekent dat er bijna geen overhead is in vergelijking met de originele byte-omvang.

5. Betekenis en Toepassing

Scheidingsprincipe: Het paper isoleert het probleem van "data representatie" van het probleem van "cryptografische encryptie". Dit maakt het mogelijk om verschillende ring-mapping cryptosystemen te bouwen op een betrouwbare, gemeenschappelijke representatielaag.
Veiligheid: De codec is deterministisch en publiek. Het biedt geen vertrouwelijkheid, integriteit of authenticiteit; het is puur een serialisatielaag. Veiligheid moet worden gegarandeerd door de daaropvolgende cryptografische protocollen.
Toekomstige Werk: De codec is direct toepasbaar in projecten zoals SYMPZON (symmetrische primitieven over gehele ringen) en vormt een essentiële schakel voor format-preserving encryption en zero-knowledge bewijssystemen die werken over $\mathbb{Z}_m$ .

Conclusie:
Dit werk levert een fundamentele, wiskundig bewezen oplossing voor het vertalen van binaire data naar de algebraïsche domeinen die nodig zijn voor moderne post-kwantum en ring-gebaseerde cryptografie. Door de combinatie van een efficiënte Rust-implementatie en formele Lean 4-verificatie, biedt het een betrouwbare basis voor de volgende generatie cryptografische protocollen.