Cryptology ePrint Archive: Report 2021/523

No Time to Hash: On Superefficient Entropy Accumulation

Yevgeniy Dodis and Siyao Guo and 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 $\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}$.

Category / Keywords: foundations / extractors, condensors, entropy accumulation, RNGs

Date: received 20 Apr 2021, last revised 20 Apr 2021

Contact author: dodis at cs nyu edu,gsy014@gmail com,noahsd@gmail com,zx572@nyu edu

Available format(s): PDF | BibTeX Citation

Version: 20210423:122421 (All versions of this report)

Short URL: ia.cr/2021/523


[ Cryptology ePrint archive ]