🔢 mathematics

Exact Bias of Linear TRNG Correctors -- Spectral Approach

本文采用谱方法推导线性真随机数生成器校正器的近最优紧偏置界，揭示出在10%输入偏置下实现80位安全性需牺牲超过50%的码率并付出显著的硬件成本。

原作者： Maciej Skorski, Francisco-Javier Soto, Onur Günlü

发布于 2026-05-22

📖 1 分钟阅读🧠 深度阅读

原作者： Maciej Skorski, Francisco-Javier Soto, Onur Günlü

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

想象一下，你正在试图构建一台能够生成真正随机数的机器，就像抛硬币来决定密码一样。在现实世界中，物理“硬币”（如电路中的电子噪声）很少是完美的。它们可能略微偏重，导致“正面”出现的概率为 55%，“反面”为 45%。这种轻微的不公平被称为偏差。

如果你直接使用这些略微不公平的硬币进行安全操作（例如加密消息），黑客最终可能会猜出其中的模式。为了解决这个问题，工程师使用一种“校正器”——一种特殊的机器，它将许多这些不公平的硬币混合在一起，从而产生一枚完全公平的硬币。

本文旨在构建最佳可能的混合机器，并精确计算其性能表现。

以下是作者发现的要点分解，使用了简单的类比：

1. 旧方法与新方法

旧方法（“最坏情况”猜测）：
此前，工程师试图通过观察单一的最坏情况来估算其混合机器的公平性。这就像说：“如果我有一袋 100 枚硬币，其中最差的一枚偏差为 10%，那么我整袋硬币都很糟糕。”这种方法非常安全，但也极其悲观。它告诉工程师，为了获得良好的安全性，需要庞大而昂贵的机器，即使这些机器的实际表现远好于数学预测。

新方法（“谱”方法）：
作者使用了一种名为傅里叶分析的数学工具（将其想象为将复杂声音分解为单个音符的方法）。他们不再仅仅关注最差的硬币，而是观察所有硬币如何相互影响。

比喻： 想象一个合唱团。旧方法只倾听最响亮但走调的歌手来评判整个团体。而新方法则倾听整个团体的和声。
结果： 他们发现，混合机器的表现远好于之前的预期。他们的新数学表明，“不公平性”的下降速度远快于旧估算的预测。事实上，他们的新估算往往比旧估算准确 10 倍（一个数量级）。

2. 完美混合的“配方”

本文介绍了一种基于权重枚举器（Weight Enumerator）的具体“配方”。

类比： 将混合机器想象成一本食谱书。“权重枚举器”是一份清单，列出了输入位（原料）可以有多少种不同的组合方式。
发现： 作者证明，如果你知道这份清单（食谱），你就可以精确计算输出结果接近完美随机的程度。他们不仅仅是猜测，而是给出了精确的公式。
“甜蜜点”： 他们找到了一种方法，将两种不同的数学测量（称为 $\ell_2$ 和 $\ell_\infty$ ）联系起来，从而获得一个几乎完美紧密的结果。这就像在“最佳情况”和“最坏情况”之间找到精确的中间点，以获得真实的答案。

3. 完美的代价（权衡）

本文还考察了制造这些机器的现实成本。

类比： 想象你想将一桶浑浊的水（有偏差的输入）变成一杯纯净水（随机输出）。
- 为了得到一杯纯净水，你必须倒掉大量的浑水。
- 输入水越浑浊（偏差越大），你需要倒掉的就越多。
发现： 作者测试了约20,000 种不同的混合配方（代码）。他们发现，如果你的输入即使只有轻微偏差（10% 的不公平），并且你希望获得极高的安全级别（80 位安全性，这是现代加密的黄金标准），你就必须牺牲超过一半的数据。
- 你可能从 100 位原始数据开始，但为了获得真正安全的结果，最终可能只得到 40 或 50 位可用的输出。
- 这种“浪费”并非缺陷，而是清理随机性的固有成本。你不能无中生有。

4. 硬件现实

最后，他们考察了这些机器在计算机芯片上所占的空间。

类比： 建造更好的过滤器需要更多的管道和阀门。
发现： 安全性、速度（速率）和成本之间存在直接联系。
- 如果你想要最高的安全性，就需要更大、更复杂的机器（更多的“门等效数”或硬件空间）。
- 如果你试图缩小机器以节省空间，你要么会降低安全性，要么必须倒掉更多的输入数据。

总结

本文是随机数发生器背后数学的“用户手册”。它告诉工程师：

不要恐慌： 你的混合机器很可能比旧有的、令人恐惧的数学预测要好得多。
要精确： 使用这种新的“傅里叶”数学来确切了解你的安全程度。
预期代价： 如果你希望从不完美的硬件中获得高安全性，就必须接受你将损失大量数据速度，并且需要更多的芯片空间来构建机器。

作者并没有发明一种新型随机数发生器；他们只是给了我们一把更锐利、更准确的尺子，用来衡量现有机器究竟有多好。

技术摘要：线性 TRNG 校正器的精确偏差：谱方法

问题陈述

真随机数生成器（TRNG）从物理现象中提取熵，但其原始输出往往表现出统计缺陷，如偏差和相关性，这些缺陷违反了密码学要求。虽然随机性提取器为校正这些缺陷提供了理论框架，但硬件实现更倾向于更简单的结构。线性校正器由运算 $Y = GX $定义（其中$ G $是二进制矩阵，$ X $是原始输入，$ Y$ 是校正后的输出），由于其仅依赖于异或门，在实践中被广泛使用。

然而，现有的针对这些线性校正器的安全分析通常依赖于 $\ell_\infty$ 界限或对单个输入偏差的简单求和。作者认为，这些技术经常产生过于保守且远离输出分布与均匀分布之间真实总变差距离（ $\ell_1$ 范数）的安全估计。这种差距导致安全评估不准确，可能引起不必要的码率（压缩效率）牺牲或硬件复杂度增加。

方法论

本文采用傅里叶分析方法来表征偏倚硬币模型下线性校正器的输出分布，其中输入位是独立但存在偏倚的。

傅里叶展开：作者利用布尔立方体上函数的傅里叶展开。通过将输出 $Y$ 的概率质量函数表示为傅里叶系数，他们将分布与矩阵 $G$ 生成的线性码的重量枚举子联系起来。
范数表征：
- $\ell_\infty$ 范数：他们推导出了任意输出最大概率的精确公式，将校正器作为最小熵凝聚器的有效性表征为码的重量枚举子多项式 $W_G(\delta)$ 的函数。
- $\ell_2$ 范数：利用帕塞瓦尔定理，他们建立了与均匀性偏差的平方 $\ell_2$ 距离的精确表征。这与加密上下文中的 Rényi 熵和不可区分性相关。
- $\ell_1$ 范数（总变差）：通过在推导出的 $\ell_\infty$ 和 $\ell_2$ 界限之间进行插值，作者构建了总变差距离的近乎紧致的上下界。
编码理论框架：分析假设输入位 $X_i$ 是独立的，具有偏倚 $\delta_i = 1 - 2p_i$ 。结果使用重量枚举子多项式 $W_G(x) = \sum A_w x^w$ 紧凑地表示，其中 $A_w$ 是汉明重量为 $w$ 的码字数量。

主要贡献

1. 精确的傅里叶分析表征

本文提供了线性校正器到均匀性的 $\ell_\infty$ 和 $\ell_2$ 距离的首个精确公式，直接通过码重量枚举子表示。这扩展了以往通常依赖较宽松界限或对输入分布做出特定假设的工作。

2. 通过插值实现的近乎紧致的 $\ell_1$ 界限

主要的理论贡献是推导出了总变差距离（ $\ell_1$ 范数）的界限，这些界限比先前的估计显著更锐利。对于具有重量枚举子 $W_G$ 和输入偏倚 $\delta$ 的码，总变差距离的界限为：
$\frac{W_G(\delta^2) - 1}{W_G(\delta) - 1} \leq \|P_Y - P_{U_k}\|_1 \leq \sqrt{W_G(\delta^2) - 1}$
这些界限将基于 $\ell_\infty$ 的先前估计提高了约一个数量级，适用于实际感兴趣的安全级别。

3. 权衡的实证评估

作者对约 20,000 个线性码（包括 Reed-Muller 码、BCH 码和循环码）进行了大规模实证研究。他们量化了以下因素之间的基本权衡：

压缩效率（码率）：比率 $k/n$ 。
密码学安全性：偏差降低的水平。
硬件复杂度：以门当量（GE）估算。

结果

安全界限与紧致性

小偏倚区域：对于小输入偏倚 $\delta \ll 1$ ，总变差距离按 $\Theta(\delta^d)$ 衰减，其中 $d$ 是码的最小距离。这与基于 $\ell_\infty$ 的先前界限形成对比，后者通常暗示依赖于 $\sqrt{\delta}$ 或更不利的缩放。
改进幅度：与 Reed-Muller 码和 BCH 码的比较表明，新界限产生了更严格的安全评估，在实际参数范围内，估计值通常提高了接近一个数量级的因子。
紧致性：对于“好”码（具有近似二项式重量分布的码），推导出的下界和上界之间的差距很小，使得 $\sqrt{W_G(\delta^2) - 1}$ 成为精确总变差距离的可靠代理。

速率 - 安全 - 成本权衡

安全成本：在有显著输入偏倚（例如 10%）的情况下实现高安全性（例如 80 位安全），通常需要牺牲超过 50% 的码率。
硬件成本：更高的安全级别通常与增加的硬件成本（以门当量衡量）相关。
帕累托前沿：研究强调，循环码通常位于帕累托前沿，在实现成本、安全性和速率之间提供有利的平衡。

意义与主张

本文声称建立了线性 TRNG 校正器的近最优安全界限，超越了历史上主导该领域的过于保守的估计。通过将分析转向谱（傅里叶）视角，作者证明了总变差距离对输入偏倚的依赖性与码的完整最小距离项成正比，而不是其平方根。

这项工作提供了一个统一的编码理论框架，允许进行精确的安全评估。它量化了硬件中随机性提取的固有成本，表明使用有偏输入实现高安全性需要大幅降低吞吐量（码率）并增加硬件复杂度。作者指出，其源代码可供复现，并建议未来的工作可以将这些结果扩展到其他码族（如极化码），并整合特定的硬件约束，如面积和功耗。