Paper 2021/523
No Time to Hash: On Super Efficient Entropy Accumulation
Yevgeniy Dodis, Siyao Guo, Noah StephensDavidowitz, and Zhiye Xie
Abstract
Realworld 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 entropyaccumulation 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 realworld 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 minentropy $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}$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2021
 DOI
 10.1007/9783030842598_19
 Keywords
 extractorscondensorsentropy accumulationRNGs
 Contact author(s)

dodis @ cs nyu edu
gsy014 @ gmail com
noahsd @ gmail com
zx572 @ nyu edu  History
 20220317: last of 2 revisions
 20210423: received
 See all versions
 Short URL
 https://ia.cr/2021/523
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/523, author = {Yevgeniy Dodis and Siyao Guo and Noah StephensDavidowitz and Zhiye Xie}, title = {No Time to Hash: On Super Efficient Entropy Accumulation}, howpublished = {Cryptology ePrint Archive, Paper 2021/523}, year = {2021}, doi = {10.1007/9783030842598_19}, note = {\url{https://eprint.iacr.org/2021/523}}, url = {https://eprint.iacr.org/2021/523} }