在计算机安全领域，随机数是构成安全系统基础的关键值，例如密钥或初始化向量 (IV)，它们必须是不可预测的。为了实现这一点，人们使用确定性随机位生成器 (DRBG)，它可以生成看似随机的数字。然而，现有的 DRBG 在安全性(对黑客攻击的不可预测性)和输出速度方面都存在局限性。

韩国科学技术研究院 (KAIST) 的研究人员开发了一种 DRBG，该算法通过一种新的证明技术，理论上实现了最高级别的安全性，同时通过并行化结构最大限度地提高了速度。这使得从物联网设备到大型服务器，都能安全、超快速地生成随机数。

计算机学院Jooyoung Lee教授领导的研究团队建立了分析基于置换的确定性随机位生成器(DRBG，Deterministic Random Bits Generator)安全性的全新理论框架，并设计出了一种实现最优效率的DRBG 。

确定性随机位生成器使用基本加密操作(例如分组密码、哈希函数和排列)从熵源(从环境中获得的随机数据)创建不可预测的随机数。

大多数密码算法都使用生成的随机数来决定依赖于它们的整个系统的根本安全性。因此，DRBG 是密码学的基础，提高其效率和安全性是一项非常重要的研究任务。

排列函数作为允许双向计算的密码算法的基本组成部分，因其出色的安全性和效率而备受关注，尤其是自从被美国标准SHA-3哈希函数采用以来。

然而，SHA-3 采用的海绵结构因其输出效率相对于置换规模的限制而受到批评。由于所有现有的基于置换的 DRBG 在其输出函数中都使用了海绵结构，因此它们也存在输出效率的限制。

此外，现有的基于置换的DRBGs使用了一种名为“游戏跳跃”的技术来证明安全性。然而，这种方法的局限性在于其安全性保证低于理论上的水平。

例如，当一个排列的容量(c)为256位时，理论上的期望值为min{c/2, λ}，即128位的安全性。但在传统的证明方法下，实际保证的安全性仅为min{c/3, λ}，约为85位。(λ为熵阈值，min表示取两者中较小的一个。)

游戏跳跃将随机数生成器和对手之间的情况定义为一场“博弈”，将其分解成许多小步骤(迷你游戏)，并计算对手在每个阶段的成功概率，然后将它们组合起来。然而，由于该过程过度细分了阶段，最终的安全级别低于实际安全级别。

韩国科学技术研究院的李柱英教授的研究团队指出，传统的跳局技术将整个游戏划分为太多步骤，并提出了一种新的证明方法，将其简化为两个阶段。

最终，他们证明了基于置换的 DRBG 的安全级别实际上对应于 min{c/2, λ} 位——与现有证明相比，提高了约 50%。他们还证明了该值是理论上可实现的最大值。

研究团队还设计了POSDRBG(基于并行输出海绵的DRBG)，以解决现有海绵结构因串行(单线)处理而导致的输出效率受限的问题。新提出的并行结构可以同时处理多个流，从而实现基于置换的DRBG的最大效率。

Jooyoung Lee教授表示：“POSDRBG是一种新型确定性随机位生成器，它提高了随机数生成速度和安全性，使其适用于从小型物联网设备到大型服务器的各种应用。这项研究预计将对正在进行的国际DRBG标准SP800-90A的修订产生积极影响，最终正式纳入基于置换的DRBG。”

这项研究由 Woohyuk Chung(韩国科学技术院，第一作者)、Seongha Hwang(韩国科学技术院)、Hwigyeom Kim(三星电子)和 Jooyoung Lee(韩国科学技术院，通讯作者)共同完成，将于 8 月在CRYPTO (年度国际密码学会议)上发表，并作为《密码学进展 - CRYPTO 2025》的一部分发表。

现有 Sponge-DRBG 的随机数输出函数采用直接连接置换 P 的海绵结构。作为参考，所有现有的基于置换函数的 DRBG 均具有此海绵结构。在该海绵结构中，P 的 n 位输入中，仅使用高 r 位作为输出 Z。因此，输出效率始终限制为 r/n。

本研究中，POSDRBG的随机数输出函数设计为允许并行计算，置换函数P的所有n位输出均变为随机数Z，因此其输出效率为1。

更多信息： Woohyuk Chung 等人，《增强基于置换的 DRBG 的可证明安全性和效率》，《密码学进展 - CRYPTO 2025》(2025 年)。