Welcome to the resource topic for 2021/523
Title:
No Time to Hash: On Super Efficient Entropy Accumulation
Authors: Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie
Abstract:Real-world random number generators (RNGs) cannot afford to use (slow) cryptographic hashing every time they refresh their state R with a new entropic input X. Instead, they use ``superefficient’’ simple entropy-accumulation procedures, such as $$R \leftarrow \mathsf{rot}{\alpha, n}(R) \oplus X,$$ where \mathsf{rot}_{\alpha,n} rotates an n-bit state R by some fixed number \alpha. For example, Microsoft’s RNG uses \alpha=5 for n=32 and \alpha=19 for n=64. Where do these numbers come from? Are they good choices? Should rotation be replaced by a better permutation \pi of the input bits? In this work we initiate a rigorous study of these pragmatic questions, by modeling the sequence of successive entropic inputs X_1,X_2,\ldots as independent (but otherwise adversarial) samples from some natural distribution family {\mathcal D}. Our contribution is as follows. * We define 2-monotone distributions as a rich family {\mathcal D} that includes relevant real-world distributions (Gaussian, exponential, etc.), but avoids trivial impossibility results. * For any \alpha with \gcd(\alpha,n)=1, we show that rotation accumulates \Omega(n) bits of entropy from n independent samples X_1,\ldots,X_n from any (unknown) 2-monotone distribution with entropy k > 1. * However, we also show that some choices of \alpha perform much better than others for a given n. E.g., we show \alpha=19 is one of the best choices for n=64; in contrast, \alpha=5 is good, but generally worse than \alpha=7, for n=32. * More generally, given a permutation \pi and k\ge 1, we define a simple parameter, the covering number C_{\pi,k}, and show that it characterizes the number of steps before the rule $$(R_1,\ldots,R_n)\leftarrow (R{\pi(1)},\ldots, R_{\pi(n)})\oplus X$$ accumulates nearly n bits of entropy from independent, 2-monotone samples of min-entropy k each. * We build a simple permutation \pi^*, which achieves nearly optimal C_{\pi^*,k}\approx n/k for all values of k simultaneously, and experimentally validate that it compares favorably with all rotations \mathsf{rot}_{\alpha,n}.
ePrint: https://eprint.iacr.org/2021/523
Talk: https://www.youtube.com/watch?v=FBd1WykCzHQ
Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/41/slides.pptx
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 .