KAIST Develops Theoretically Optimal Deterministic Random Bits Generator

A team of Korean researchers has developed a world-class Deterministic Random Bits Generator (DRBG).

Random numbers are crucial values in computer security, such as secret keys and initialization vectors (IVs), which must be unpredictable and form the foundation of security systems. DRBGs use basic cryptographic operations-such as block ciphers, hash functions, and permutations-to generate unpredictable random numbers from environmental random data sources (entropy sources).

However, existing DRBGs have limitations in terms of unpredictability (security) against hacking and output speed. In contrast, the DRBG developed by the research team has demonstrated the highest theoretically possible level of security through a new proof technique, and maximized speed by parallelizing its structure. This makes it possible to generate random numbers both securely and at ultra-high speeds.

(From left) Sungha Hwang, PhD candidate, Department of Computer Science, KAIST; Woohyeok Jung, PhD candidate; Jooyoung Lee, Professor. Provided by KAIST

On August 20, KAIST announced that Professor Jooyoung Lee’s research team from the Department of Computer Science has established a new theoretical framework for analyzing the security of DRBGs based on permutation (a process of shuffling the order of multiple bits or bytes, which allows for bidirectional conversion), and has successfully designed a DRBG that achieves optimal efficiency.

Random numbers generated by DRBGs are used in most cryptographic algorithms, such as generating secret keys and initialization vectors, and thus fundamentally determine the security of entire systems built on them. This is why improving the efficiency and security of DRBGs has emerged as a critical challenge.

In DRBGs, permutation functions are basic components of cryptographic algorithms that allow bidirectional computation. They are used in the U.S. standard SHA-3 hash function, which is recognized for its excellent security and efficiency.

However, the "sponge structure" adopted in SHA-3 has a limitation in that its output efficiency is low compared to the size of the permutation. The sponge structure refers to a process where, much like a sponge absorbs and squeezes out water, data input is sequentially absorbed and then output of the desired length is squeezed out.

Existing permutation-based DRBGs have used a technique called "Game Hopping" to prove security, but this method has sometimes resulted in lower security evaluations than what is theoretically possible.

For example, when the capacity (c) of the permutation is 256 bits, one would theoretically expect 128 bits of security, but the existing proof method only guarantees about 85 bits, failing to meet the theoretical expectation.

The Game Hopping technique defines the scenario where the DRBG and an attacker compete as a "game," dividing it into several small stages ("minigames") and calculating the probability of the attacker winning at each stage, then summing these probabilities. This process, due to excessive subdivision of stages, results in lower security figures than in reality.

Focusing on this issue with the Game Hopping technique, the research team proposed a new proof method by simplifying the subdivided stages into just two. They also demonstrated that applying this method can improve the security level of permutation-based DRBGs by about 50% compared to previous methods.

In particular, they proved that the enhanced security level is the theoretical maximum that can be achieved.

The team also designed "POSDRBG (Parallel Output Sponge-based DRBG)," which overcomes the output efficiency limitations of the serial (single-line) processing approach of the traditional sponge structure. POSDRBG is a new DRBG that improves both the speed and security of random number generation, from small Internet of Things (IoT) devices to large-scale servers. The new parallel structure allows data to be output in parallel, as if processing multiple lines simultaneously, enabling permutation-based DRBGs to achieve maximum efficiency, according to the research team.

Professor Jooyoung Lee stated, "We expect that this research will have a positive impact on the ongoing revision of the international standard SP800-90A for DRBGs, by including 'permutation function-based DRBGs' as an official standard."

SP800-90A is an international standard document established by the U.S. National Institute of Standards and Technology (NIST), 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 was supported by the Institute for Information & Communications Technology Planning & Evaluation (IITP), with Woohyuk Jung, a PhD candidate at the KAIST Graduate School of Information Security, as the first author, and Professor Jooyoung Lee as the corresponding author. The results will be presented at CRYPTO (Annual International Cryptology Conference), an international conference in the field of cryptography.

This content was produced with the assistance of AI translation services.