Paper 2021/523

No Time to Hash: On Super Efficient Entropy Accumulation

Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, and 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 $$ of the input bits? In this work we initiate a rigorous study of these pragmatic questions, by modeling the sequence of successive entropic inputs $$ as independent (but otherwise adversarial) samples from some natural distribution family $$. Our contribution is as follows. * We define $$-monotone distributions as a rich family $$ that includes relevant real-world distributions (Gaussian, exponential, etc.), but avoids trivial impossibility results. * For any $$ with $$, we show that rotation accumulates $$ bits of entropy from $$ independent samples $$ from any (unknown) $$-monotone distribution with entropy $$. * However, we also show that some choices of $$ perform much better than others for a given $$. E.g., we show $$ is one of the best choices for $$; in contrast, $$ is good, but generally worse than $$, for $$. * More generally, given a permutation $$ and $$, we define a simple parameter, the covering number $$, and show that it characterizes the number of steps before the rule $$ accumulates nearly $$ bits of entropy from independent, $$-monotone samples of min-entropy $$ each. * We build a simple permutation $$, which achieves nearly optimal $$ for all values of $$ simultaneously, and experimentally validate that it compares favorably with all rotations $$.