🔢 mathematics

Fast Bounded-Independence Functions and Their Duals

本文提出了快速有限独立函数及其对偶函数的改进构造，这些构造同时优化了电路规模与代数次数，实现了极低的失败概率，并支持先进的密码学应用，例如具有线性复杂度的完美安全多方计算以及最优的加密矩阵-向量乘法。

原作者： Martijn Brehm, Yuval Ishai, Nicolas Resch

发布于 2026-06-08

📖 1 分钟阅读🧠 深度阅读

原作者： Martijn Brehm, Yuval Ishai, Nicolas Resch

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

想象一下你正在试图建造一座数字堡垒。为了保护你的数据安全，你需要两种主要工具：哈希函数（就像是文件的唯一指纹）和纠错码（就像是一种能让信息在被撕碎并重新组装后仍能幸存的方法）。

通常情况下，让这些工具变得“完美随机”（这样黑客就无法预测）既缓慢又昂贵。这就像是用手搅拌一大桶油漆；这需要耗费很长时间。这篇论文的目标是构建这些工具，使它们既快速（像使用机器一样），又能表现得足够随机以确保安全。

以下是作者取得的成就，通过简单的类比进行解释：

1. “超级指纹”机器（快速哈希函数）

问题： 想象你有一个巨大的图书馆。你想为每本书创建一个简短的“指纹”，以便你能分辨出两本书是否不同。一个“随机”的指纹是非常棒的，因为它是无法伪造的，但制作一个指纹需要太长时间。
旧方法： 以前的方法只能保证如果你观察两本书，它们的指纹是互不相关的。但如果你观察三本书，模式可能会开始重复或变得可预测。
新的魔力： 作者构建了一台机器，它可以同时为任意数量的书（比如 10 本或 100 本）生成指纹，并且它们看起来都会是完全无关的。

类比： 想想掷骰子。旧机器一次只能掷两个骰子并保证它们不匹配。而这台新机器可以同时掷 100 个骰子，无论你看多少个，结果都是完全不可预测的。
为什么重要： 在密码学中，这意味着你可以更快地处理数据，而不会损失安全性。他们还确保了其背后的数学原理并不复杂（低“代数次数”），这就像是说这台机器使用的是简单的齿轮，而不是复杂的、缓慢的机器人技术。

2. “孪生代码”系统（具有快速对偶码的快速编码）

问题： 在密码学中，你通常需要两个相关的代码：一个用于加密信息的“原码”（Primal code）和一个用于辅助解密或验证的“对偶码”（Dual code）。通常，你可以拥有一个快速的原码或者一个快速的对偶码，但很难同时拥有两者。这就像是一个锁很快，但钥匙很慢；或者钥匙很快，但锁很慢。
旧方法： 最近曾有人尝试让两者都变快，但这种方法非常不稳定。它仅适用于二进制（0 和 1），失败概率较高，且无法处理不同的数据速率。
新的魔力： 作者构建了一个系统，使得锁和钥匙都很快，适用于任何类型的数据（不仅是 0 和 1），且几乎不会失败。

类比： 想象一个高安全性保险库。以前，你可以得到一个开启速度很快的保险库，但备份钥匙需要数小时才能切割完成。或者你有一个快速的钥匙，但保险库却需要数天才能打开。这个新设计让你拥有的保险库能瞬间开启，且备份钥匙也能瞬间切割完成。
“GV 界限”成就： 他们还证明了这些编码在理论上是尽可能完美的。想象一下要把行李箱装进卡车。“吉尔伯特-瓦尔沙姆界限”（Gilbert-Varshamov bound）是理论上你能装入多少行李箱的极限。这些新编码就像随机、完美的装载工作一样，将卡车装到了绝对的极限，但他们是用一种快速、有序的方法实现的。

3. “超强韧性”编码（列表译码）

问题： 有时，信息会被严重损坏（比如一条短信有一半字母丢失了），以至于你不能仅仅靠猜测来还原。你必须列出所有可能的原始信息。
新的魔力： 作者创建的编码非常鲁棒，即使信息受到严重破坏，可能存在的原始信息列表也会非常短（只有寥寥几种选择）。

类比： 想象你收到一张撕碎的食谱。普通的编码可能会说：“它可能是‘烤蛋糕’到‘盖房子’之间的任何东西。”而这个新编码会说：“它肯定要么是‘烤蛋糕’，要么是‘烤派’。”它将混乱缩小到了一个极小的、可控的范围内。
转折点： 他们对锁和钥匙（代码及其对偶码）都实现了这一点，这在业界尚属首次。

4. 为什么这很重要（“聚会”类比）

论文展示了这些工具如何帮助安全多方计算（MPC）。

场景： 假设 100 个人想要计算他们的平均薪资，但同时又不希望泄露自己的薪资。
旧的瓶颈： 进行这种安全计算通常需要大量的通信和计算能力，随着人数的增加，性能扩展性很差。
新的结果： 使用这些快速编码，所需的计算能力会随人数呈线性增长。
类比： 如果有 10 个人，需要 10 分钟。如果有一千个人，需要一千分钟。在此之前，增加人数可能会导致时间爆炸式增长（比如 100 个人可能需要 10,000 分钟）。这使得大规模群体的安全计算变得可行。

总结

作者为密码学构建了一套全新的“快进”按钮。他们创造了：

即使在同时观察多个输入时也能保持不可预测性的哈希函数。
既能快速加密也能快速解密，且适用于任何数据类型的加密编码。
即使在遭受严重损坏后也能通过极少数猜测进行恢复的强韧性编码。

这些工具让安全计算能够高效扩展，使得在大规模群体中保护数据变得可行，而不会让一切都慢下来。

技术摘要：快速有界独立函数及其对偶

问题陈述

本文旨在解决构建既能模拟随机函数和随机线性码的统计特性，又能保持常数计算开销的密码学原语的挑战。作者寻求的是“快速”实现——定义为可由线性规模算术电路（规模为 $O(n)$ ）计算的实现——这些实现需满足：

有界独立性： 对于任何常数 $t$ ，都是 $t$ -wise 独立的哈希函数。
快速对偶码： 一类线性码家族，其编码码与对偶码均能实现快速、系统化编码，并达到接近 Gilbert-Varshamov (GV) 界限的距离。
更强的类随机属性： 超越简单的距离属性，扩展到如列表可译性（list-decodability）等性质，确保这些码即使在局部约束（局部相似性）下也表现得像随机线性码。

先前的工作，如 [IKOS08] 和 [DI14]，建立了快速两两独立（pairwise independent）哈希函数和接近 GV 界限的快速码，但在 $t$ 的独立性参数、运算域或同时优化码及其对偶码的能力方面存在局限性。最近由 [BR26] 完成的构造改进了快速对偶码，但受限于二进制域、要求固定的速率为 1/2、具有非忽略的失败概率，且缺乏系统化编码。

方法论

作者基于“IKOS 构造”（Ishai, Kushilevitz, Ostrovsky, Sahai）和“DI 构造”（Druk, Ishai）进行构建，并将它们推广到更高的独立性参数。

1. 泛化哈希函数

哈希函数的核心构造遵循一个三步流水线：

外部编码： 对输入应用一个在大字母表（但为常数大小）上具有大距离的快速线性码。
内部哈希： 对编码向量的每个坐标应用常数大小的 $t$ -wise 独立哈希函数。
提取： 对结果应用一个良性码的生成矩阵的转置（作为提取器）。

为了实现 $t$ -wise 独立性，作者在内部步骤中，用常数大小的 $t$ -wise 独立哈希函数替换了原有的常数大小的两两独立哈希函数。他们证明，如果外部码具有足够大的距离（具体而言为 $> 1 - 1/t^2$ ），则 $t$ 个输入的差异性会在足够比例的坐标上得以保留，从而允许内部哈希函数产生独立的均匀输出，且最终的提取步骤能够保留这些输出。

2. 线性均匀输出族 (LUOF)

为了构造这些码，作者利用了线性均匀输出族 (LUOF) 的概念。若对于任何非零输入 $x$ ，输出 $xA $均服从均匀分布，则称随机矩阵$ A$ 为一个 LUOF。

快速 LUOF： 作者泛化了 [DI14] 的构造，创建了一个快速 $t$ -LUOF。若对于任何 $t$ 个线性无关的输入 $x_1, \dots, x_t$ ，输出 $x_1A, \dots, x_tA$ 均为均匀且随机独立的，则称矩阵 $A$ 是一个 $t$ -LUOF。
构造： 其构造过程与哈希函数的构造类似，涉及一个外部码、一层随机常数大小矩阵（充当“内部”函数）以及一个提取步骤。作者证明，如果外部码具有足够的距离，则内部随机矩阵会将线性无关的输入映射为独立的均匀输出。

3. 构建快速对偶码

利用 $t$ -LUOF 矩阵 $A \in \mathbb{F}_q^{k \times r}$ ，作者定义了一个具有系统化编码映射 $x \mapsto (x, xA)$ 的码 $C$ 。

对偶性： 对偶码 $C^\perp$ 由映射 $y \mapsto (-yA^\top, y)$ 生成。
转置原理： 引用转置原理（引理 3.4），作者指出，如果计算 $xA $是快速的（线性规模），那么计算$ yA^\top$ 也是快速的。
对偶的独立性： 一个关键的技术贡献是证明了如果 $A$ 是一个 $t$ -LUF，那么 $A^\top$ 也是一个 $t$ -LUF（引理 3.9）。这依赖于 Vazirani 的 XOR 引理，并确保对偶码继承了原码的强随机属性。

核心贡献与结果

1. 快速 $t$ -wise 独立哈希函数

结果： 对于任何常数 $t$ ，作者构造了一个由线性规模电路计算的 $t$ -wise 独立哈希函数族。
优化： 对于二进制域 ( $q=2$ )，代数次数被优化为 $\log_2 t$ 。这是接近最优的，因为更低的次数将无法支持 $t$ -wise 独立性。
效率： 电路规模为 $O(k+r)$ ，其中 $k$ 是输入长度， $r$ 是输出长度。隐藏的常数取决于 $t$ （约为 $\Theta(t^7)$ ），但对于固定的 $t$ 仍为常数。

2. 具有快速对偶码的快速码 (GV-Bound)

结果： 作者构造了一个在任何有限域 $\mathbb{F}_q$ 上具有任意速率 $R \in (0, 1)$ 的码 $C$ 及其对偶码 $C^\perp$ 家族。
属性：
- $C$ 和 $C^\perp$ 均支持快速、系统化编码（线性规模）。
- 两者都能以概率 $1 - 2q^{-\varepsilon n}$ 达到接近 Gilbert-Varshamov 界限 的距离。
- 该构造具有可忽略的失败概率（不同于 [BR26]）。
- 它支持一个用于编码的线性规模通用电路。

3. 具有快速对偶码的快速列表可译码

结果： 通过利用 $t$ -LUOF 属性，作者将该构造扩展到了 $t$ -局部相似 于随机线性码的码。
列表可译性： 他们证明，对于任何常数 $t$ ，所构造的码（及其对偶码）在列表可译容量范围内是 $(\rho, L)$ -列表可译的，其中列表大小 $L = O(1/\varepsilon)$ 。
新颖性： 作者로 知，这是第一个同时实现快速编码、快速对偶编码以及两者皆具备最优列表可译性的构造。

意义与密码学应用

本文展示了这些构造如何作为强大的构建模块，特别是在需要高效率和强安全保证的场景中。

1. 完全安全的多元计算 (MPC)

作者提出了第一个完全安全 MPC 的非平凡协议，其电路复杂度随参与方数量呈线性缩放 ( $O(n)$ )。

背景： 使用代数码（如 Reed-Solomon 码）的先前协议通常会产生准线性开销。
应用： 利用快速对偶码，他们构造了一个不经意线性评估 (OLE) 协议，并将其扩展到一般的常数规模函数。该协议在面对被动攻击者时，实现了安全阈值 $t = (1/2 - \varepsilon)n$ 。

2. 加密矩阵-向量乘法 (EMVP)

在基于复杂度的密码学背景下，作者将快速对偶码应用于加密矩阵-向量乘法。

改进： 他们的构造克服了 [BR26] 方法的局限性（该方法受限于 $\mathbb{F}_2$ 且具有非忽略的失败概率）。
益处： 这使得 EMVP 协议中的矩阵编码和查询编码都能够实现渐近最优的电路复杂度。

3. 随机线性码的保守替代品

$t$ -LUOF 构造为依赖于噪声线性代数硬度（如 LPN - Learning Parity with Noise）的应用提供了随机线性码的“保守”替代品。

优势： 虽然之前的构造仅依赖于最小距离（1-局部相似性），但 $t$ -LUOF 确保了 $t$ -局部相似性，从而保证了更强的组合特性，如列表可译性。这为防止可能利用局部结构的攻击提供了更稳健的安全假设。

4. MPC 友好型哈希

具有低代数次数的快速 $t$ -wise 独立哈希函数直接适用于 MPC 协议，在这些协议中，电路规模和代数次数都会影响通信和轮数复杂度。该构造同时优化了这两者。

结论

本文成功地将先前的线性规模构造推广到支持更高的独立性参数和更强的类随机属性。通过引入快速 $t$ -LUOF 及其对偶性质的证明，作者提供了一个统一的框架，用于构造同时具备快速、系统化且具有统计鲁棒性的码和哈希函数。这些结果为实现具有最优渐近复杂度的全新密码学协议提供了可能，特别是在信息论 MPC 和加密计算领域。