🔢 mathematics

Canonical Byte-String Encoding for Finite-Ring Cryptosystems

This paper introduces a canonical base-m codec for finite-ring cryptosystems that maps byte strings to residue lists using an adapted rANS-based system, featuring exact decoding, length-prefixed headers for suffix tolerance, and a Rust implementation alongside a machine-checked Lean 4 formalization verifying its correctness and bounds.

Original authors: Kyrylo Riabov, Serhii Kryvyi

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kyrylo Riabov, Serhii Kryvyi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message to a friend who lives in a very strange city. In this city, the only currency people use is coins, not paper bills. Furthermore, the city has a strict rule: you can only carry a specific number of coins at a time (let's say, up to 50 coins).

Your message, however, is written on standard paper (bytes of data like text, images, or code). You can't just hand your friend a stack of paper; you have to convert that paper into a stack of coins before you can enter the city's secure zone.

This paper is about building the perfect machine to do that conversion.

The Problem: The "Paper-to-Coin" Mismatch

In the world of advanced cryptography (specifically "Ring-Mapping Cryptosystems"), computers need to turn normal data (like your email or a photo) into numbers that fit inside a mathematical "ring" (a circle of numbers).

The Old Way: People used to build these machines by hand, making up their own rules for every single project. It was like trying to build a bridge with random bricks you found in your garage. It worked for small projects, but it was messy and prone to breaking.
The New Way: This paper proposes a standardized, universal machine called the Base-m-len Codec. It's like a factory assembly line that turns any piece of paper (up to a certain size) into a perfect stack of coins, no matter what the coin size (modulus) is.

How the Machine Works (The Analogy)

The machine has three distinct parts, which form the "wire format" (the shape of the data as it travels):

The ID Card (The Length Header):
Before the machine starts, it looks at your paper and writes down exactly how many pages you have. It writes this number in a fixed-size box.
- Why? So the machine on the other end knows exactly when to stop reading. It's like writing "20 pages" on the envelope so the recipient doesn't keep looking for pages that don't exist.
The Blueprint (The State Header):
The machine also writes down a "snapshot" of its internal gears. This is a second fixed-size box.
- Why? This ensures that if the machine gets interrupted or if there's extra junk at the end of the message, it can still figure out exactly where it was supposed to stop. It's like a "checkpoint" marker.
The Coin Stream (The Payload):
Now, the machine takes your paper, page by page, and converts it into a stream of coins.
- The Magic Trick: It doesn't just do simple math. It uses a clever technique (borrowed from data compression technology called rANS) that acts like a sliding scale.
- Imagine you have a bucket. You pour a page of text into the bucket. If the bucket gets too full, you scoop out a handful of coins and put them in a line. You keep doing this until the bucket is just right, then you pour in the next page.
- The result is a long line of coins that perfectly represents your original text.

Why is this Special?

1. It's "Canonical" (The Standard)
Before this, everyone built their own coin-conversion machines. If you sent a message to Person A, they might need a different machine than Person B. This paper says, "Let's all use this specific machine." Now, any computer running this protocol can talk to any other computer, no matter what language or system they use.

2. It's "Forgiving" (Suffix Tolerance)
Imagine you send a message, but the delivery truck accidentally drops a few extra coins at the end of the line.

Old machines: Might get confused, think the message is longer than it is, and crash.
This machine: Looks at the "ID Card" (the length header), counts exactly that many coins, and then says, "Okay, I have my message. I'll ignore the extra coins you dropped." It's incredibly robust.

3. It's Proven to be Perfect (The Lean 4 Formalization)
This is the most impressive part. The authors didn't just write code; they wrote a mathematical proof using a computer program called Lean 4.

Think of it like a lawyer who doesn't just say, "I promise this bridge is safe." They have a computer that has mathematically proven that the bridge will never collapse, no matter how many cars drive over it, as long as the rules are followed.
They proved that if you put in a message, the machine will give you back the exact same message, with zero errors.

The "Real World" Check

The authors also built a working version of this machine in a programming language called Rust. They tested it on a modern computer (an Apple M3 chip).

Speed: It's fast. It can process data much quicker than older, clunky methods.
Efficiency: For larger coin sizes, it's almost as efficient as just sending the paper directly (1 coin per page), but it still keeps the safety features.

Summary

This paper introduces a universal, mathematically proven translator that turns normal digital data into the specific number format required by next-generation encryption systems. It's like creating a standard adapter plug for the entire world of secure communication, ensuring that data can move between different cryptographic systems without getting lost, corrupted, or misunderstood.

In short: It's the "USB-C port" for a very specific type of high-security mathematical encryption.

1. Problem Statement

Finite-ring cryptosystems (such as those used in Format-Preserving Encryption, Multi-Party Computation, and Fully Homomorphic Encryption) operate on mathematical elements within the ring $\mathbb{Z}_m$ (integers modulo $m$ ). However, real-world data exists as arbitrary byte strings (e.g., UTF-8 text or binary files).

Current implementations often rely on ad-hoc, hand-built alphabets or small fixed symbol tables to map bytes to residues. This approach lacks a canonical, general-purpose representation layer that can handle arbitrary data of any length (up to $2^{64}$ bytes) before the algebraic encryption step begins. The paper addresses the need for a deterministic, self-delimiting codec that maps byte strings to lists of residues modulo $m$ without ambiguity or loss of information.

2. Methodology: The Base- $m$ -Len Codec

The authors propose a new codec called base- $m$ -len, which transforms a byte string into a stream of residues in $\mathbb{Z}_m$ . The design is inspired by rANS (range Asymmetric Numeral Systems) but adapted for deterministic, uniform byte-to-residue transduction rather than probabilistic entropy coding.

Wire Format

The encoded output consists of three distinct components:

Length Prefix: A fixed-width encoding of the original byte string length ($|bytes|$).
State Prefix: A fixed-width encoding of the final payload state.
Payload Stream: A sequence of residues generated by processing the input bytes.

Encoding Algorithm

Header Calculation: For a given modulus $m$ , the system calculates a width $k = \min \{j \in \mathbb{N}_0 : m^j \ge 2^{64}\}$ . Both the length and the final state are encoded using exactly $k$ little-endian base- $m$ digits.
Payload Transduction: The encoder processes the input bytes in reverse order. It maintains a state variable $x$ , initialized at a specific lower bound $L$ . For each byte $b$ , the state is updated via $x \leftarrow 256x + b$ . Before each update, the encoder emits digits ( $x \mod m$ ) and renormalizes the state ( $x \leftarrow \lfloor x/m \rfloor$ ) until the state falls below an encoder threshold.
Output: The emitted payload digits are reversed to form a FIFO (First-In-First-Out) stream for the decoder.

Decoding Algorithm

Header Parsing: The decoder reads the first $k$ digits to recover the declared length $\ell$ . If $\ell = 0$ , it returns an empty string immediately.
State Initialization: The next $k$ digits are read to reconstruct the initial payload state.
Reconstruction: The decoder iterates $\ell$ times. In each step, it extracts a byte ( $x \mod 256$ ), updates the state ( $x \leftarrow \lfloor x/256 \rfloor$ ), and consumes new payload digits to renormalize the state back up to the decoder lower bound.
Suffix Tolerance: Crucially, the decoder stops exactly after reconstructing $\ell$ bytes. Any valid residue digits remaining in the stream (a "suffix") are ignored, making the codec robust against appended data.

3. Key Contributions

Canonical Codec Definition: The paper defines a modulus-parameterized, canonical byte-to-residue codec suitable for finite-ring protocols, centered on the base- $m$ -len wire format.
Formal Verification (Lean 4): The authors provide a machine-checked formalization in Lean 4. This includes:
- Proofs of fixed-width prefix inversion (guaranteeing the length and state can be perfectly recovered).
- Proofs of payload-state bounds (ensuring the state never exceeds $2^{64}$ ).
- End-to-end stream correctness (proving Decode(Encode(bytes)) == bytes).
- Proof of suffix tolerance (decoding ignores trailing valid digits).
Reference Implementation: A high-performance Rust library (sym-adv-encoding) implementing the codec, including UTF-8 frontends and benchmarking suites.
Complexity Analysis: The codec operates in $O(n)$ time and $O(1)$ working state (excluding I/O buffers), making it linear and efficient for streaming applications.

4. Results and Performance

Correctness: The Lean 4 formalization mathematically guarantees that for any supported modulus $m$ (where $2 \le m$ and $256 \le \text{decoderLowerBound}(m)$ ) and any byte string of length $< 2^{64}$ , the roundtrip is exact.
Efficiency: Benchmarks on an Apple M3 Pro machine show the native Rust implementation significantly outperforms exact BigUint radix-conversion baselines.
- Example: Encoding 1 KiB with $m=257$ achieves 217.0 MiB/s, compared to 25.2 MiB/s for the BigUint baseline.
- Decoding is even faster, reaching 640.5 MiB/s for the same configuration.
Overhead: The paper analyzes the trade-off between modulus size and overhead. Larger moduli reduce the payload rate (approaching 1 residue per byte as $m \to 256$ ) but increase the fixed header size. For $m=257$ , the payload rate is $\approx 0.9993$ digits per byte, with a fixed header of 16 digits.

5. Significance and Limitations

Significance:

Standardization: It provides a missing "glue" layer for ring-based cryptography, allowing arbitrary data to be safely transported into $\mathbb{Z}_m$ domains without custom, error-prone mappings.
Formal Trust: The machine-checked proofs provide a high level of assurance for critical cryptographic infrastructure, a rarity in codec implementations.
Practicality: The performance benchmarks demonstrate that this theoretical construct is viable for real-world high-throughput applications.

Limitations & Security Context:

Not a Security Primitive: The codec is deterministic and public; it provides no confidentiality, integrity, or authenticity. It must be wrapped by a cryptographic protocol.
Length Leakage: The wire format explicitly reveals the exact byte length of the input. If length hiding is required, padding must be applied at the protocol layer.
Implementation Scope: The formal proofs cover the abstract specification, not the low-level Rust implementation details (e.g., memory allocation, parser hardening), which remain engineering responsibilities.

In conclusion, this paper successfully isolates and solves the byte-to-residue representation problem for finite-ring cryptosystems, offering a mathematically verified, high-performance, and canonical solution that bridges the gap between raw data and algebraic encryption.