⚡ electrical engineering

Deterministic Johnson--Lindenstrauss Projections from Pisot $\beta$ -Transformations for Zero-Knowledge Private Routing

本文介绍了一种确定性的、零知识友好的 Johnson–Lindenstrauss 投影，该投影源自 Pisot $\beta$ -变换，通过使用单个公共种子实现了无维度的方差和精确的有限域可复现性，从而消除了对昂贵的电路内随机性的需求，同时保留了成对距离。

原作者： I. Dey, I. Cherkaoui

发布于 2026-08-14

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： I. Dey, I. Cherkaoui

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

想象一个你的数字生活是由一系列秘密握手组成的场景。你想向一名保镖证明你属于某个 VIP 俱乐部，但又不想出示身份证；或者想向银行证明你有足够的钱，却不想透露你的余额。这就是“零知识证明”（Zero-Knowledge Proofs, ZK）的魔力：一种无需泄露秘密本身，就能表达“我知道这个秘密”的方法。但问题在于：为了证明你属于正确的群体，你的数字身份通常是一个巨大的、复杂的数字云（高维向量）。检查这个云是否与 VIP 名单匹配，就像试图在山脉中寻找一颗特定的沙粒；这需要消耗大量的计算能力和时间，从而拖慢了整个进程。

为了解决这个问题，科学家们使用了一种被称为“约翰逊-林登斯特劳斯”（Johnson-Lindenstrauss, JL）投影的技巧。把它想象成一台神奇的复印机，能将一个巨大的 3D 雕塑压扁成一个平面的 2D 影子。令人惊叹的是，如果你压得恰到好处，影子中点之间的距离与原始雕塑中的距离会保持完全一致。这让“保镖”的工作变得既轻松又快速。然而，这里有一个障碍：制作这种“挤压机器”的标准方法涉及掷一个数字骰子。由于机器是随机的，为了证明你没有偏离协议，你必须证明你正确地掷了骰子。这种证明过程过于沉重，抵消了你通过挤压数据所获得的所有速度优势。我们需要一种固定的、公开的、且不需要通过证明骰子投掷是否公平来运行的挤压机器。

本文介绍了一种利用一种特殊的数学工具——“Pisot $\beta$ -变换”（Pisot $\beta$ -transformations）来构建这种机器的新方法。作者 I. Dey 和 I. Cherkaoui 构建了一种确定性的（非随机）投影，它与随机投影一样出色，但具有完美的复现性，任何人、在任何地方都可以复现，而无需证明一个随机种子。

问题所在：“随机”瓶颈

在隐私路由的世界里（即 AI 代理决定哪个专家模型应该处理一条私密消息），消息会被转化为一长串数字。为了保持隐私，代理需要证明该消息属于一个“安全”类别，方法是将消息与一组已知的“质心”（代表安全消息的平均示例）进行比较。这种比较是非常昂expensive（昂贵）的。

通常的解决方法是使用随机矩阵（JL 投影）来缩减数字列表。但因为矩阵是随机的，计算机必须对其进行承诺，并证明其生成的公平性。这种证明成本如此之高，以至于抵消了缩减数据带来的初衷。作者认为，我们需要一个公开、固定且对所有人一致的矩阵，这样就不需要证明随机性了。

解决方案：“拉伸与折叠”机器

作者提议使用一种被称为 Pisot $\beta$ -变换 的混沌映射来构建这个固定的矩阵。

类比： 想象一块面团。你拉伸它（乘以一个数字 $\beta$ ），然后将其折叠回自身（取余数）。这是一个“混沌”的过程；如果你从两个几乎相同的面团点开始，它们会迅速移动到完全不同的位置。这种混沌通常非常适合扰乱数据，但对于需要达成共识的计算机来说却很糟糕。
普通混沌的问题： 如果两台计算机尝试模拟这种拉伸和折叠，微小的数学差异（如舍入误差）会导致它们迅速分道扬镳。一台计算机可能认为面团在位置 A，而另一台则认为在位置 B。它们无法达成一致。
Pisot 的魔力： 作者使用了一种被称为 Pisot 数（例如黄金比例 1.618 或塑料数 1.325）的特殊数字。这些数字具有特殊的代数属性：尽管过程是混沌的，但其“轨道”（面团经过的路径）可以通过一组有限的规则精确计算。
- 结果： 两台计算机可以运行完全相同的“拉伸与折叠”模拟，并得到完全相同的结果，没有任何舍入误差。这就像拥有一份完美的食谱，无论你使用的是木勺还是金属勺，只要遵循步骤，结果都是一样的。

他们的发现

团队证明了这种确定性矩阵与随机矩阵一样有效，同时还具备以下几个关键优势：

它保留了距离： 他们在数学上证明了“挤压”后的数据几乎完全保留了原始点之间的距离。误差（偏差）极小，即使数据变得巨大也不会恶化。
它快速且廉价： 因为矩阵是固定且公开的，计算机不需要花费时间去证明其生成过程是公平的。它只需使用预先商定的“食谱”即可。
它是可复现的： 他们展示了虽然通用的混沌映射（如著名的“逻辑映射”）需要极其庞大的内存才能精确计算（呈指数级增长），但 Pisot 映射仅需要极小的、固定的内存（呈线性增长）。
- 测试： 在模拟中，他们将 Pisot 方法与包括随机高斯矩阵和其他混沌映射在内的六种标准方法进行了对比。
- 结果： Pisot 方法在统计质量上完美匹配了随机矩阵。测量中的“噪声”是一致的，且路由消息的能力也完全相同。事实上，他们发现，一个单一的公开“种子”（面团的起始点）就可以为大型列表中的所有质心对保留距离。

局限性（以及未来）

作者非常明确地说明了他们已经做到了什么以及还没做到什么。

已证明的部分： 他们在数学上证明了偏差是微小的，并且方差（噪声）表现良好。他们证明了一个好的种子是存在的，并且可以通过搜索找到。
已测量的部分： 他们通过模拟证明，在实践中该方法与随机方法一样有效，没有精度损失。
仍待解决的部分： 他们承认，虽然他们相信该方法甚至比目前的证明所显示的还要好（对于大型列表需要更少的内存），但他们尚未完全证明能够保证针对任何可能输入的“集中不等式”（concentration inequality），目前仅针对他们所保护的特定质心集有效。

为什么这很重要

这不仅仅是一个数学谜题；它是让隐私 AI 变得实用的关键。目前，如果你想将一个私密的医疗案例路由给专家，或者在不透露细节的情况下验证一笔付款，这种“证明”过程可能需要数分钟时间和数 GB 的数据。有了这种新的确定性投影，作者认为我们可以将时间缩短至秒级，将数据量缩减至 KB 级，同时保持坚不可摧的隐私保障。

他们不仅仅是发现了一个新数字；他们发现了一种让零知识证明的“魔法”在一条固定的、公开的轨道上运行的方法，使任何人都能进行验证，从而消除了拖慢一切节奏的昂贵的随机“掷骰子”过程。这是迈向一个隐私不再以牺牲耐心为代价的未来的重要一步。

技术摘要：基于 Pisot $\beta$ -变换的确定性 Johnson–Lindenstrauss 投影，用于零知识证明私密路由

1. 问题陈述

在用于私密路由的零知识（ZK）证明系统中，证明者必须证明消息嵌入 $v \in \mathbb{R}^d$ 属于由一组公开质心 $C = \{c_1, \dots, c_N\}$ 定义的允许语义类。这通常通过最近质心测试来完成，该测试需要 $O(Nd) $个算术约束。鉴于现代嵌入维度（$ d \in [768, 4096]$），这种约束数量主导了证明的大小和证明者的计算时间。

标准的补救措施是使用 Johnson–Lindenstrauss (JL) 投影将维度降低到 $m \ll d$ 。然而，经典的 JL 矩阵是随机的。在 ZK 上下文中，使用随机矩阵会迫使电路去提交矩阵并证明其采样的正确性，从而重新引入了本应通过投影消除的计算成本。此外，随机矩阵需要证明采样过程，这会产生泄露风险。挑战在于如何构建一个公开、确定且固定的投影矩阵，该矩阵能够：

可证明地保持成对距离。
原生适用于电路的有限域。
不需要电路内的随机性或采样证明。

2. 方法论

作者提出通过 Pisot $\beta$ -变换 的标准化轨道来构建投影矩阵 $A$ 。

映射： $\beta$ -变换 $T_\beta x = \beta x - \lfloor \beta x \rfloor$ 是定义在单位区间上的映射，其中 $\beta > 1$ 是一个 Pisot 数（一个其伽罗瓦共轭均严格位于单位圆内的代数整数，例如黄金分割比）。
动力学： 该映射是一个确定性的“拉伸与折叠”混沌系统，具有唯一的不变 Parry 测度 $\mu$ 。至关重要的是，由于 $\beta$ 是 Pisot 数，该映射的传递算子具有谱间隙（spectral gap），导致观测值之间的相关性呈几何级数衰减（ $|r_k| \le C\theta^k$ ）。
矩阵构建：
- 选择一个公开种子 $x_0$ 。
- 固定一个采样间隔 $g$ ，以确保采样点处于相关时间之外。
- 矩阵条目 $A_{ij}$ 通过归一化的轨道值 $z_p = \psi(T_\beta^{pg} x_0)$ 顺序填充。
- 投影为 $\Phi(v) = Av/\sqrt{m}$ 。
有限域可重现性： 与通用的混沌映射不同，Pisot 性质确保了其轨道可以在固定的有限域中精确重现。生成 $k$ 步的成本与 $k$ 成线性关系（具体为 $O(k \log_2 \beta)$ 比特），而通用的混沌映射（如 Logistic 映射）则需要指数级的比特增长（ $O(2^k)$ ）才能维持精确算术。

3. 核心贡献

本文提出了四个主要的理论与实践贡献：

无维度偏差与方差界限：
- 偏差（Bias）： 作者证明，平方范数估计器的偏差受限于随采样间隔 $g$ 几何衰减的项（引理 1），且该项与环境维度 $d$ 无关。这是通过 $\beta$ -映射的谱间隙推导出的，相比于标准的等分布论证提供了更强的保证。
- 方差（Variance）： 他们表明估计器的方差按 $V_0/m$ 比例缩放。至关重要的是，在给定的集中假设下，常数 $V_0$ 是**无维度（dimension-free）**的（不会随 $d^2$ 增长），这与暗示 $O(d^2)$ 的粗略界限不同。这意味着无论 $d$ 有多大，固定的投影维度 $m$ 都足够了。
单一公开种子的存在性：
- 定理 1 证明存在一个公开种子 $x_0$ ，能够将所有 $\binom{N}{2}$ 对质心间的距离保持在 $(1 \pm \varepsilon)$ 之内。
- 该种子可以通过高效的离线搜索找到。一旦找到，矩阵就是固定的、公开的，在 ZK 证明期间不需要随机性承诺。
通过 Pisot 性质实现精确重现：
- 本文指出，Pisot 性质（而非通用的混沌性质）对于 ZK 部署至关重要。它保证了轨道可以以每步 $\log_2 \beta$ 的计算成本在固定有限域中精确重现，避免了通用混沌映射导致的指数级精度（分母）增长问题。
鲁棒性与搜索：
- 提供了一个闭式可验证的鲁棒性半径（命题 1），定义了查询在不改变其投影后最近质心的情况下所能承受的最大扰动。
- 种子的搜索是无条件的（由方差界限保证），但如果针对谱间隙映射的特定集中不等式成立，搜索复杂度可以优化到对 $N$ 的对数依赖。

4. 实验结果

该构造针对六种标准投影进行了评估：高斯（Gaussian）、Rademacher、Achlioptas 稀疏、次采样随机哈达玛变换（SRHT）、以及混沌序列矩阵（Yu 等人）。

统计质量： Pisot 投影在统计质量上与随机投影相匹配。
- 方差率： 估计器方差遵循 $1/m$ 定律，并与高斯 JL 的 $2/m$ 参考值重合。
- 维度无关性： 当 $d$ 从 64 增加到 1024 时，方差常数 $V_0$ 在 2 附近保持平坦，证实了无维度的理论预测。
- 失真： 所有质心对的最坏情况相对失真追踪了高斯 JL 基准。
任务性能： 在一个 $d=256$ 的 24 类最近质心路由任务中，Pisot 投影在 $m=32$ 时恢复了 100% 的准确率（实现了 8 倍压缩），与其他方法表现一致。
可重现性： 模拟确认，浮点实现会在约 50-70 步后偏离精确轨道（符合 Lyapunov 预测），而 Pisot $\beta$ -进位表示法保持精确且紧凑（200 步仅需 139 比特，而 Logistic 映射需要 $1.66 \times 10^6$ 比特）。

5. 重要性与主张

本文声称，该构造是唯一能同时满足以下三个关键要求的方案，用于 ZK 私密路由：

无电路内随机性： 无需承诺或证明随机矩阵的采样过程。
在固定有限域中精确重现： 通过 Pisot 性质实现，每步成本为 $\log_2 \beta$ ，避免了通用混沌映射 $O(2^k)$ 的成本。
在统计上等同于随机投影： 其方差率和失真特性与标准 JL 矩阵相匹配。

作者指出，虽然统计质量已得到证明，但将无条件的 $O(N^2)$ 种子搜索界限提升到条件性的 $O(\log N)$ 界限，仍依赖于一个特定的针对传递算子的集中不等式，这目前仍是一个开放的理论步骤。在实践中，该方法使证明生成从分钟/GB 级转向秒级，使得高维嵌入的可验证私密路由变得可行。