Paper 2025/951

Enhancing Provable Security and Efficiency of Permutation-based DRBGs

Woohyuk Chung, Korea Advanced Institute of Science and Technology
Seongha Hwang, Korea Advanced Institute of Science and Technology
Hwigyeom Kim, Norma Inc. Seoul, Korea
Jooyoung Lee, Korea Advanced Institute of Science and Technology
Abstract

We revisit the security analysis of the permutation-based deterministic random bit generator~(DRBG) discussed by Coretti et al. at CRYPTO 2019. Specifically, we prove that their construction, based on the sponge construction, and hence called Sponge-DRBG in this paper, is secure up to queries in the seedless robustness model, where is the required min-entropy and is the sponge capacity. This significantly improves the provable security bound from the existing to the birthday bound. We also show that our bound is tight by giving matching attacks. As the Multi-Extraction game-based reduction proposed by Chung et al. at Asiacrypt 2024 is not applicable to Sponge-DRBG in a straightforward manner, we further refine and generalize the proof technique so that it can be applied to a broader class of DRBGs to improve their provable security. We also propose a new permutation-based DRBG, dubbed POSDRBG, with almost the optimal output rate , outperforming the output rate of Sponge-DRBG, where is the output size of the underlying permutation and . We prove that POSDRBG is tightly secure up to queries. Thus, to the best of our knowledge, POSDRBG is the first permutation-based DRBG that achieves the optimal output rate of 1, while maintaining the same level of provable security as Sponge-DRBG in the seedless robustness model.

Note: Full version of the paper.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2025
Keywords
Deterministic random bit generatorSeedless robustness modelCryptographic spongePermutationProvable security
Contact author(s)
hephaistus @ kaist ac kr
mathience98 @ kaist ac kr
rlagnlrua4 @ gmail com
hicalf @ kaist ac kr
History
2025-05-26: approved
2025-05-25: received
See all versions
Short URL
https://ia.cr/2025/951
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/951,
      author = {Woohyuk Chung and Seongha Hwang and Hwigyeom Kim and Jooyoung Lee},
      title = {Enhancing Provable Security and Efficiency of Permutation-based {DRBGs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/951},
      year = {2025},
      url = {https://eprint.iacr.org/2025/951}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.