🔢 mathematics

Canonical Byte-String Encoding for Finite-Ring Cryptosystems

本文提出了一种基于 rANS 系统的规范字节串编码方案，实现了将长度小于 2^64 的字节串精确映射为模 m 剩余列表，并通过 Rust 实现、Lean 4 形式化验证及性能基准测试，确保了该有限环密码系统基础层的正确性与实用性。

原作者： Kyrylo Riabov, Serhii Kryvyi

发布于 2026-03-25

📖 1 分钟阅读🧠 深度阅读

原作者： Kyrylo Riabov, Serhii Kryvyi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一种名为 "Base-m-len" 的新技术，它就像是为未来的“数学密码锁”（有限环密码系统）准备的一套万能翻译器。

为了让你更容易理解，我们可以把整个加密过程想象成给一个特殊的保险箱运送货物。

1. 背景：为什么需要这个“翻译器”？

想象一下，你有一堆普通的货物（比如你的微信聊天记录、照片或文件，在计算机里就是字节流）。现在，你要把它们送进一个非常特殊的数学保险箱（有限环加密系统）里。

问题：这个保险箱的锁孔非常特殊，它只接受一种叫“余数”（Residue）的特定形状的零件。普通的货物（字节）直接塞进去是塞不进的，或者塞进去会卡住。
现状：以前的做法是，人们为了塞进货物，会自己手工制作一些临时的“适配器”（比如只针对特定字母表）。但这就像是用胶带和回形针临时拼凑的，不够通用，也不够安全。
目标：我们需要一个标准的、官方的翻译器，能把任何普通的货物（无论是中文、英文还是二进制代码）都完美地转换成保险箱能接受的“余数零件”。

2. 核心发明：Base-m-len 翻译器

这篇论文提出的 Base-m-len 就是这个“官方翻译器”。它的工作流程非常巧妙，我们可以把它比作打包和拆包的过程：

A. 打包（编码过程）

当你有一堆货物要送进去时，翻译器会做三件事：

贴标签（长度前缀）：
它首先会数一下货物有多少个，然后把这个数字写在一个固定大小的标签上。
- 比喻：就像快递单上必须写明“包裹里有 5 个苹果”。不管苹果多大，标签的大小是固定的，这样接收方一眼就知道要收多少东西。
记录状态（状态前缀）：
它会在打包过程中记录一个“中间状态”的数字，也写在另一个固定大小的标签上。
- 比喻：就像在装箱单上备注“当前箱子的平衡状态”，这是为了后面能精准复原。
转换货物（负载流）：
它把货物里的每一个字节，按照一种特殊的数学规则（类似把十进制数变成五进制数，但更复杂），一个个转换成“余数零件”。
- 比喻：就像把原本的大块木头（字节），通过一台机器，切割成一个个标准的小积木块（余数），以便塞进保险箱。

关键点：这个翻译器非常聪明，它不仅能转换，还能保证无论货物多长（只要不超过 180 亿亿字节），都能完美转换。

B. 拆包（解码过程）

当接收方拿到这些“余数零件”时，翻译器会这样工作：

先看标签：它先读那个“长度标签”，知道“哦，原来里面有 5 个苹果”。
只看前 5 个：它开始还原货物，一旦还原了 5 个，它就立刻停止。
忽略多余部分：如果后面还有一堆多余的零件（比如传输过程中不小心粘上的），它直接无视，不会报错，也不会乱读。
- 比喻：这就像你点了一份 5 个汉堡的套餐。服务员给你端上来 5 个汉堡，后面还跟着几个没点的汉堡。你吃完 5 个就走了，后面的汉堡留给别人，完全不会搞乱你的用餐体验。

3. 这个翻译器有什么厉害之处？

这篇论文不仅仅是提出了一个想法，还做了两件非常硬核的事情：

数学上的“绝对保证” (Lean 4 形式化验证)：
作者没有只靠“我觉得它是对的”来写代码。他们用一种叫 Lean 4 的数学证明工具，像写数学定理一样，用计算机证明了这个翻译器在数学上是绝对正确的。
- 比喻：这就像造桥，普通工程师靠经验算算，而这篇论文是请了最顶级的数学家，用计算机一步步推演，证明这座桥在理论上绝对不会塌，无论你怎么走。
实际跑得很快 (Rust 实现)：
他们写了一个叫 Rust 的程序库，并且测试了速度。结果显示，这个翻译器不仅理论上完美，在实际电脑里跑得也飞快，比那些笨重的老方法快得多。

4. 为什么这很重要？

通用性：以前，不同的加密系统可能需要不同的“翻译器”，现在有了这个标准，大家都能用。
安全性：它本身不是加密锁（它不保密），它是把货物准备好的过程。只有把货物完美地放进保险箱，真正的加密锁才能发挥作用。如果货物没放好，锁就锁不上。
容错性：它不怕后面多出来的“垃圾数据”，这在网络传输中非常重要，因为网络传输经常会有杂音或多余的数据包。

总结

简单来说，这篇论文发明了一套标准化的“货物打包说明书”。

以前，大家想把普通文件放进“数学保险箱”时，都是各自为战，容易出错。现在，他们提供了一套经过数学严格证明、速度飞快、且能自动处理多余数据的标准打包法。这让未来的加密通信（比如保护隐私、多方计算等）变得更加安全、可靠和高效。

这就好比他们为未来的“数字世界”制定了一套通用的集装箱标准，让所有的货物都能安全、无损地通过那些特殊的“数学海关”。

这是一份关于论文《Canonical Byte-String Encoding for Finite-Ring Cryptosystems》（有限环密码系统的规范字节串编码）的详细技术总结。

1. 研究背景与问题 (Problem)

核心痛点：基于环（Ring-mapping）的密码系统（如有限环上的对称原语、同态加密、零知识证明等）需要将消息表示为模 $m$ 的剩余类（residues in $\mathbb{Z}_m$ ）才能进行代数加密或解密。
现有局限：以往的研究（如文献 [2], [3]）通常依赖手动构建的字母表或小型固定符号表来处理消息准备。这种方法仅适用于演示代数原理，无法解决任意 UTF-8 文本或二进制数据如何规范地转换为环元素的一般性问题。
需求：需要一个通用的、规范化的“字节到剩余类”（Byte-to-Residue）编码层，作为环级加密之前的标准预处理步骤。该层需要支持任意长度的字节串（小于 $2^{64}$ ），并能精确还原。

2. 方法论 (Methodology)

论文提出了一种名为 Base- $m$ -len 的规范编解码器（Codec），其核心设计如下：

编码结构：
该编解码器将字节串映射为模 $m$ 的剩余类列表，其线格式（Wire Format）包含三个部分：
1. 长度前缀 (Length Prefix)：使用固定宽度的 $k$ 位 $m$ 进制数编码字节串的长度 $|bytes|$。
2. 状态前缀 (State Prefix)：使用固定宽度的 $k$ 位 $m$ 进制数编码最终的有效载荷状态。
3. 有效载荷流 (Payload Stream)：通过均匀 $m$ 进制转换（Uniform Base- $m$ Transduction）生成的剩余类序列。
核心算法机制：
- 基于 rANS 的变体：编码器借鉴了 Duda 提出的 rANS（Range Asymmetric Numeral Systems）系统，但进行了适应性调整。
- 状态维护：编码器维护一个状态 $x$ ，初始化为解码器下界 $L$ 。
- 处理流程：
  - 编码：从右向左扫描输入字节。在每次更新状态 $x \leftarrow 256x + b$ 之前，如果 $x$ 超过编码器阈值，则输出 $x \mod m$ 并更新 $x \leftarrow \lfloor x/m \rfloor$ 。最后将最终状态编码为固定宽度的前缀。
  - 解码：首先读取长度前缀，确定需要恢复的字节数。然后读取状态前缀，按顺序消耗有效载荷数字，执行逆操作 $x \leftarrow \lfloor x/256 \rfloor$ 并输出字节。
- 自定界与容错：由于长度信息包含在固定宽度头部中，解码器在恢复声明的字节数后即可停止。这意味着解码过程对尾部附加的有效后缀数字具有容错性（Suffix Tolerance），即忽略多余的合法后缀。
形式化验证：
- 使用 Lean 4 对抽象编解码器进行了形式化规范。
- 提供了机器检查的数学证明，涵盖固定宽度前缀的可逆性、有效载荷状态边界（确保状态值在 $2^{64}$ 范围内）以及流级别的往返正确性。

3. 主要贡献 (Key Contributions)

规范编解码器定义：定义了一个参数化的、基于模数 $m$ 的字节到剩余类编解码器（Base- $m$ -len），专门用于有限环协议。
理论保证：
- 证明了对于所有满足参数界限的模数 $m$ 和长度小于 $2^{64}$ 的字节串，解码是精确的（Exact Decoding）。
- 证明了头部前缀的固定宽度可逆性。
- 证明了解码器对尾部有效后缀的容忍性。
工程实现与验证：
- 发布了 Rust 库 (sym-adv-encoding) 作为参考实现。
- 提供了 Lean 4 形式化规范及机器验证证明，确保算法逻辑的数学正确性。
- 提供了性能基准测试数据。

4. 实验结果与性能 (Results)

复杂度分析：
- 编码和解码的时间复杂度为线性 $O(n)$ ，其中 $n$ 是字节串长度。
- 工作空间复杂度为 $O(1)$ （除输入输出缓冲区外）。
- 开销：由固定宽度的头部（ $2k$ 个数字）和有效载荷速率（ $\log_m 256$ 个数字/字节）组成。随着模数 $m$ 增大，有效载荷速率降低，但头部宽度仅在 $m^k$ 跨越 $2^{64}$ 阈值时发生阶跃变化。
性能基准 (Apple M3 Pro)：
- 吞吐量：原生实现（Native）显著快于基于大整数（BigUint）的精确基数转换基准。
  - 例如，在 $m=257$ 时，编码 64 KiB 数据的吞吐量约为 236.7 MiB/s，解码约为 669.1 MiB/s。
  - 相比之下，BigUint 方法在相同规模下性能急剧下降（解码仅约 3.2 MiB/s）。
- 效率：当 $m=257$ 时，每个字节约对应 1 个剩余类，同时保留了显式的长度恢复和尾部容错能力，非常高效。

5. 意义与应用 (Significance)

填补空白：为有限环密码系统提供了一个标准化的、通用的消息表示层，解决了任意二进制数据如何安全、规范地映射到 $\mathbb{Z}_m$ 的问题。
支持前沿协议：该编解码器可直接集成到对称加密、多方计算（MPC）、全同态加密（FHE）和零知识证明（ZK）等协议中，特别是支持 ERC 项目 SYMPZON 等关于整数环上对称原语的研究。
安全性与局限性：
- 该编解码器本身是确定性且公开的，不提供机密性、完整性或真实性（需由上层密码协议提供）。
- 它暴露了确切的字节长度，若需隐藏长度，需在上层协议中强制填充。
- 形式化验证仅覆盖抽象规范边界，底层实现（如内存分配、解析器硬化）仍需开发者自行处理。
与现有技术的区别：不同于 NTRU 或 ML-KEM 等基于格的密码系统（关注硬问题加密），本文专注于字节到剩余类的表示层；不同于传统的 ANS 熵编码（关注概率源模型压缩），本文利用 ANS 的状态归一化机制来实现确定性的、自定界的剩余类传输。

总结：这篇论文通过数学形式化验证和高效的工程实现，建立了一个连接通用二进制数据与有限环密码原语的关键桥梁，确保了数据在代数加密步骤前的规范性和可逆性。