August 20, 2025 by The Korea Advanced Institute of Science and Technology (KAIST)
Collected at: https://techxplore.com/news/2025-08-ultra-fast-random-generator-boosts.html
In computer security, random numbers are crucial values that must be unpredictable—such as secret keys or initialization vectors (IVs)—forming the foundation of security systems. To achieve this, deterministic random bit generators (DRBGs) are used, which produce numbers that appear random. However, existing DRBGs had limitations in both security (unpredictability against hacking) and output speed.
KAIST researchers have developed a DRBG that theoretically achieves the highest possible level of security through a new proof technique, while maximizing speed by parallelizing its structure. This enables safe and ultra-fast random number generation applicable from IoT devices to large-scale servers.
A research team led by Professor Jooyoung Lee from the School of Computing has established a new theoretical framework for analyzing the security of permutation-based deterministic random bit generators (DRBG, Deterministic Random Bits Generator) and has designed a DRBG that achieves optimal efficiency.
Deterministic random bit generators create unpredictable random numbers from entropy sources (random data obtained from the environment) using basic cryptographic operations such as block ciphers, hash functions and permutations.
The random numbers generated are used in most cryptographic algorithms to determine the fundamental security of the entire system that relies on them. Therefore, DRBGs form the basis of cryptography, and improving their efficiency and security is a highly important research task.
Permutation functions, as fundamental components of cryptographic algorithms that allow bidirectional computation, have attracted significant attention for their excellent security and efficiency, especially since being adopted in the U.S. standard SHA-3 hash function.
However, the sponge construction adopted in SHA-3 has been criticized for its limited output efficiency relative to permutation size. Since all existing permutation-based DRBGs used sponge constructions in their output functions, they too suffered from output efficiency limitations.
In addition, existing permutation-based DRBGs used a technique called game hopping to prove security. However, this method had the limitation of yielding lower security guarantees than theoretically possible.
For example, when a permutation’s capacity (c) is 256 bits, the theoretical expectation is min{c/2, λ}, i.e., 128-bit security. But under the conventional proof method, the guarantee was only min{c/3, λ}, about 85 bits. (λ refers to the entropy threshold, and min indicates taking the smaller of the two values.)
Game hopping defines the situation between the random number generator and the adversary as a “game,” splits it into many small steps (mini-games), and calculates the adversary’s success probability at each stage to combine them. However, because the process excessively subdivides the stages, the resulting security level turned out lower than the actual one.
Professor Jooyoung Lee’s research team at KAIST noted that the conventional game-hopping technique divided the overall game into too many steps and proposed a new proof method simplifying it into just two stages.
As a result, they demonstrated that the security level of permutation-based DRBGs actually corresponds to min{c/2, λ} bits— an improvement of approximately 50% compared to existing proofs. They also proved that this value is the theoretical maximum achievable.
The research team also designed POSDRBG (Parallel Output Sponge-based DRBG) to address the output efficiency limitation of the existing sponge structure caused by its serial (single-line) processing. The newly proposed parallel structure processes multiple streams simultaneously, thereby achieving the maximum efficiency possible for permutation-based DRBGs.
Professor Jooyoung Lee stated, “POSDRBG is a new deterministic random bit generator that improves both random number generation speed and security, making it applicable from small IoT devices to large-scale servers. This research is expected to positively influence the ongoing revision of the international DRBG standard SP800-90A, leading to the formal inclusion of permutation-based DRBGs.”
This research, with Woohyuk Chung (KAIST, first author), Seongha Hwang (KAIST), Hwigyeom Kim (Samsung Electronics), and Jooyoung Lee (KAIST, corresponding author), will be presented in August at CRYPTO (the Annual International Cryptology Conference) and have been published as part of Advances in Cryptology – CRYPTO 2025
The random number output function of the existing Sponge-DRBG uses a sponge structure that directly connects the permutation P. For reference, all existing permutation-function-based DRBGs have this sponge structure. In the sponge structure, among the n-bit inputs of P, only the upper r bits are used as the output Z. Therefore, the output efficiency is always limited to r/n.
In this study, the random number output function of POSDRBG was designed to allow parallel computation, and all n-bit outputs of the permutation function P become random numbers Z. Therefore, it has an output efficiency of 1.
More information: Woohyuk Chung et al, Enhancing Provable Security and Efficiency of Permutation-Based DRBGs, Advances in Cryptology – CRYPTO 2025 (2025). DOI: 10.1007/978-3-032-01901-1_15
Leave a Reply