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.

KAIST (President Kwang Hyung Lee) announced on the 20th of August that 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.
*Permutation: The process of shuffling bits or bytes by changing their order, allowing bidirectional conversion (the shuffled data can be restored to its original state).

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.
*Block cipher: A method of transforming plaintext into ciphertext of the same length.
**Hash function: A function that converts input into a fixed-length digest by mixing input data to produce an unpredictable value.

The random numbers generated are used in most cryptographic algorithms 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.
*Sponge construction (Sponge construction): A structure resembling a sponge’s process of absorbing and squeezing out water. It sequentially absorbs input data and then squeezes out as much output as desired. Since the output length is not fixed, it can generate very long random numbers or hashes when needed.

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.”
*SP800-90A: An international standard document established by the U.S. NIST (National Institute of Standards and Technology), defining the design and operational criteria for DRBGs used in cryptographic systems. Until now, permutation-based DRBGs have not been included in the standard.

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), the world’s top academic conference in cryptology.

Article title: “Enhancing Provable Security and Efficiency of Permutation-Based DRBGs“
DOI: https://doi.org/10.1007/978-3-032-01901-1_15

This research was supported by the Institute for Information & Communications Technology Planning & Evaluation (IITP).

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.