Welcome to the resource topic for 2025/951
Title:
Enhancing Provable Security and Efficiency of Permutation-based DRBGs
Authors: Woohyuk Chung, Seongha Hwang, Hwigyeom Kim, Jooyoung Lee
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 O\left(\min \left\{2^{\frac{c}{2}}, 2^{\frac{\lambda}{2}}\right\}\right) queries in the seedless robustness model, where \lambda is the required min-entropy and c is the sponge capacity. This significantly improves the provable security bound from the existing O\left(\min \left\{2^{\frac{c}{3}}, 2^{\frac{\lambda}{2}}\right\}\right) 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 1, outperforming the output rate \frac{r}{n} of Sponge-DRBG, where n is the output size of the underlying permutation and r=n-c. We prove that POSDRBG is tightly secure up to O\left(\min \left\{2^{\frac{c}{2}}, 2^{\frac{\lambda}{2}}\right\}\right) 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.
ePrint: https://eprint.iacr.org/2025/951
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .