🔢 mathematics

Correlation Bounds and Markov Analysis for Ring-Oscillator TRNGs: A Joint Validation Framework

本文提出了一种联合验证框架，首次建立了基于环振荡器的真随机数生成器中毛瑞尔（Maurer）Z 分数与二阶非峰值相关度 $C_2$ 之间的数学关联，并通过 OpenTRNG 实现验证了该框架在简化新设计质量评估方面的有效性。

原作者： Miguel Alcocer, Ana Isabel Gómez, Domingo Gomez-Perez

发布于 2026-03-17

📖 1 分钟阅读🧠 深度阅读

原作者： Miguel Alcocer, Ana Isabel Gómez, Domingo Gomez-Perez

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

这篇论文主要是在研究如何制造真正随机的数字（就像抛硬币或掷骰子那样，完全不可预测），并发明了一套新的“体检方法”来检查这些随机数是否合格。

为了让你更容易理解，我们可以把这篇论文的内容想象成**“制造完美骰子并设计一套快速质检流程”**的故事。

1. 背景：我们需要什么样的“骰子”？

在网络安全（比如银行转账、加密聊天）中，我们需要一种叫做真随机数生成器（TRNG）的东西。它就像是一个魔法骰子，每次掷出来的数字都必须是完全不可预测的。

现有的方法：科学家常用一种叫**“环形振荡器”的电路来制造这种骰子。你可以把它想象成一个“电子回音室”**：信号在里面一圈圈跑，因为电路里微小的热噪声（就像空气里的杂音），信号跑的速度会有极其微小的快慢变化。这种“快慢不一”就是随机性的来源。
问题：虽然理论上很完美，但实际做出来的电路可能会有瑕疵。如果随机数不够“乱”，黑客就能猜出你的密码。所以，我们需要严格的测试来确保它真的随机。

2. 过去的“体检”太复杂

以前，科学家有两种主要的测试方法，但它们像是两个互不相干的医生：

医生 A（Maurer 测试）：专门检查骰子掷出来的序列有没有“压缩性”（比如是不是有很多重复的图案）。如果序列太有规律，这个医生就会报警。
医生 B（Mauduit-Sárközy 相关性测量）：专门检查序列里有没有“隐藏的朋友关系”。比如，如果掷出"1"之后，下一次掷出"0"的概率特别大，那它们就有“关系”，不够随机。

痛点：以前没人知道这两个医生说的话有没有关联。如果医生 A 说“合格”，医生 B 会不会也说“合格”？如果不通，我们就得把两个医生都请来做全套检查，既费时又费力。

3. 这篇论文的突破：把两个医生“联姻”

这篇论文的作者（来自西班牙的三位研究者）做了一件开创性的事：他们发现这两个医生其实是“连体婴”，说的话高度相关！

核心发现：他们建立了一个数学模型，证明了**“相关性测量”（医生 B）和"Maurer 测试分数”（医生 A）**之间存在极强的正相关关系。
- 比喻：就像你发现，如果一个骰子掷出的点数分布很均匀（医生 A 满意），那么它内部肯定也不存在奇怪的“朋友关系”（医生 B 也会满意）。
新框架：他们提出了一套**“联合验证框架”**。现在，你不需要分别做两套复杂的测试，只要看这两个指标是否同时达标，就能快速判断这个随机数生成器好不好。

4. 他们是怎么验证的？（实验过程）

作者们利用开源工具 OpenTRNG，像搭积木一样设计了 58 种不同的“环形振荡器”电路（有的简单，有的复杂）。

实验方法：
- 他们给这些电路输入不同的频率参数。
- 然后同时计算“相关性分数”和"Maurer 测试分数”。
- 他们还对比了两种读取数据的方法：
  1. 直接采样（像直接看信号波形）：效果很差，就像用漏勺接水，随机性漏掉了。
  2. 计数法（像数信号转了多少圈）：效果极好。
结果：
- 他们发现，使用**“计数法”（Counting）配合“异或积累”**（把多个信号混合在一起，就像把多杯不同温度的水倒在一起搅匀），产生的随机数质量极高。
- 数据图表显示，这两个指标（Z 分数和相关性）几乎是一条直线上升的。这意味着：只要相关性低，Maurer 测试分数就一定好。

5. 这意味着什么？（对未来的影响）

这篇论文给未来的随机数生成器设计师带来了一个**“万能公式”**：

简化工作：以前设计新电路，要跑一堆复杂的测试。现在，只要算出**“相关性”和"Maurer 分数”**，如果这两个数都在安全范围内（比如相关性小于 0.01），就可以大胆地认为这个设计是安全的，大概率能通过所有其他复杂测试。
快速排雷：如果这两个指标有一个不对劲，设计师就能立刻知道电路设计有问题，不用等到最后才发现。
理论突破：他们不仅做了实验，还从数学上证明了这些指标和**“马尔可夫链”**（一种描述状态转移概率的数学工具）之间的关系，把“数数”和“概率”完美地联系在了一起。

总结

简单来说，这篇论文就像是为**“制造完美随机骰子”的工匠们提供了一把“双刃尺”**。

以前，工匠们需要拿着两把不同的尺子（Maurer 测试和相关性分析）反复测量，生怕漏掉什么。现在，作者告诉他们：“别慌，这两把尺子量出来的结果其实是一回事！只要用这把‘联合尺’量一下，发现数值都很漂亮，那你的骰子就是世界顶级的，可以直接拿去保护你的银行密码了！”

这不仅节省了时间，还让设计更可靠，是密码学安全领域的一个重要进步。

这篇论文提出了一种针对基于环形振荡器（Ring Oscillator, RO）的真随机数发生器（TRNG）的联合验证框架。该框架首次将理论上的相关性界限（Mauduit-Sarkozy 相关性度量）与经验熵评估（Maurer 通用统计测试）联系起来，并建立了它们与高阶马尔可夫链转移概率之间的数学关系。

以下是该论文的详细技术总结：

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

背景：基于环形振荡器的 TRNG 利用热抖动（thermal jitter）作为熵源，广泛应用于密码学。为了确保其输出序列具有加密级质量，必须进行严格的统计验证。
现有局限：
- 目前的研究通常单独使用 Mauduit-Sarkozy $k$ 阶相关性度量 ( $C_k$ ) 来提供伪随机性的理论界限，或使用 Maurer 通用统计测试（通过 Z 分数评估）来评估经验熵。
- 缺乏关联：此前没有工作将这两个关键指标（ $C_k$ 和 Maurer Z-score）进行实证关联，也没有研究它们与高阶马尔可夫链转移概率之间的数学联系。
- 验证困难：设计者缺乏一个统一的指标来快速评估新设计的 TRNG 质量，往往需要运行全套测试套件（如 NIST、AIS31），耗时且复杂。

2. 方法论 (Methodology)

论文采用理论推导与计算仿真相结合的方法：

理论分析：
- 建立 $C_k$ 与马尔可夫链的关系：推导了 $k$ 阶马尔可夫链转移概率与 $C_k$ 之间的数学不等式。证明了低 $C_k$ 值能保证 $k$ 位模式频率接近均匀分布（即高熵的必要条件）。
- 建立 $C_k$ 与 Maurer 测试的关系：推导了 Maurer 测试函数 $f_{TU}$ 的上下界，并将其表示为 $C_k$ 的函数，从而在理论上连接了压缩性测试与相关性度量。
- 引用 Schmidt 界限：采用了 Schmidt 改进的相关性界限公式 $C_k(S) \le \sqrt{\frac{2k \ln N}{N}}$ ，该界限比传统的 Alon 界限更紧（约 3.5 倍改进）。
计算仿真与实验设计：
- 工具：使用开源框架 OpenTRNG 进行实现和评估。
- 架构：采用 差分计数器方法（Differential Counter-based approach，参考 Allini et al. [6]）。
  - 使用两个频率略有不同的自由运行环形振荡器（RO）。
  - 通过参考时钟同步采样，计算振荡器周期数（而非直接采样比特值）。
  - 对两个计数器的最低有效位（LSB）进行异或（XOR）操作，并累加 $n$ 个独立源以进一步降低相关性。
- 参数空间探索：
  - 振荡器频率： $f_1 \in [100, 250]$ MHz, $f_2/f_1 \in [0.7, 1.4]$ 。
  - 参考频率： $f_{ref} \in [50, 150]$ MHz。
  - 异或累积深度： $n \in \{1, 2, 4, 8, 16\}$ 。
- 评估指标：对 58 种配置生成的 $10^5$ 位序列，计算 2 阶非峰值相关性 ( $C_2$ ) 和 Maurer Z 分数。

3. 关键贡献 (Key Contributions)

首个实证关联：首次建立了 Maurer Z 分数与 $C_2$ （非峰值 2 阶相关性）之间的经验正相关关系。
理论桥梁：推导了 $C_k$ 与 $k$ 阶马尔可夫链转移概率之间的显式数学关系，以及 $C_k$ 与 Maurer 测试界限的关系。
统一验证框架：提出了一种简化的 TRNG 质量评估协议，通过联合检查 $C_2$ 和 Maurer Z 分数即可初步判断设计质量，无需立即运行全套测试。

4. 实验结果 (Results)

强正相关性：在 58 种配置中，Maurer Z 分数与 $C_2$ $C_{2}$ 之间表现出极强的正相关性（皮尔逊相关系数 $r = 0.95$ $r = 0.95$ ）。
- 当 $|Z| < 0.1$ 时， $C_2$ 始终小于 0.01。
- 高 $C_2$ 值（> 0.8）对应 $Z > 1$ ，表明偏离随机期望。
差分计数器的优势：
- 直接采样 vs. 计数器：在相同振荡器参数下，直接采样比特导致 $C_2 = 0.34$ 且 Maurer 测试失败；而计数器方法将 $C_2$ 降至 0.009，且 $|Z| < 1$ （通过测试）。计数器方法使 $C_2$ 改善了约 40 倍。
- 异或累积：增加异或累积深度（ $n \ge 4$ ）能将性能推向理想区域（ $|Z| \approx 0, C_2 < 0.01$ ）。
界限验证：
- 实际实现的差分计数器 TRNG 达到了 Schmidt 改进界限 以下。
- 对于 $N=10^5$ ，理论界限约为 0.021，实际测量值普遍低于 0.01，优于 Alon 等人的旧界限（0.076）。
游程统计：理想噪声模型（无噪声方波）游程长度均值 $\mu=1.22$ ，而硬件基线在累积后 $\mu \approx 2.0$ ，符合理论随机期望（ $\mu=2, \sigma=\sqrt{2}$ ），这直接对应于 $C_2$ 的降低。

5. 意义与结论 (Significance & Conclusion)

简化评估流程：该研究为 TRNG 设计者提供了一个实用的验证协议。如果设计同时满足 $C_2 < 0.01$ 和 $|Z| < 2$ ，则极大概率能通过 NIST 或 AIS31 等全面测试套件。这大大减少了评估时间和计算成本。
早期故障检测：这两个指标的偏差可以作为设计缺陷或攻击（如故意引入的相关性）的早期预警信号。
理论深化：通过将组合数学（相关性界限）与概率论（马尔可夫链、熵）联系起来，加深了对环形振荡器 TRNG 内部随机性机制的理解。
未来方向：未来的工作将探索特定架构的更紧相关性界限，并将该框架扩展到多源异或累积和高阶相关性分析中。

总结：这篇论文通过理论推导和大规模仿真，证明了在基于环形振荡器的 TRNG 中，Maurer 通用测试的 Z 分数与 Mauduit-Sarkozy 相关性度量之间存在强相关性。这一发现使得设计者可以使用这两个易于计算的指标作为“统一度量”，快速、有效地验证 TRNG 的加密级质量，并证实了差分计数器架构在降低相关性方面的显著优势。