TY - GEN
T1 - No Time to Hash
T2 - 41st Annual International Cryptology Conference, CRYPTO 2021
AU - Dodis, Yevgeniy
AU - Guo, Siyao
AU - Stephens-Davidowitz, Noah
AU - Xie, Zhiye
N1 - Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - 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←rotα,n(R)⊕X, where rotα , n rotates an n-bit state R by some fixed number α. For example, Microsoft’s RNG uses α= 5 for n= 32 and α= 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 X1, X2, … as independent (but otherwise adversarial) samples from some natural distribution family D. Our contribution is as follows. We define 2-monotone distributions as a rich family D that includes relevant real-world distributions (Gaussian, exponential, etc.), but avoids trivial impossibility results.For any α with gcd (α, n) = 1, we show that rotation accumulates Ω(n) bits of entropy from n independent samples X1, …, Xn from any (unknown) 2-monotone distribution with entropy k> 1.However, we also show some choices of α perform much better than others for a given n. E.g., we show α= 19 is one of the best choices for n= 64 ; in contrast, α= 5 is good, but generally worse than α= 7, for n= 32.More generally, given a permutation π and k≥ 1, we define a simple parameter, the covering number Cπ , k, and show that it characterizes the number of steps before the rule (Formula presented.) accumulates nearly n bits of entropy from independent, 2-monotone samples of min-entropy k each.We build a simple permutation π∗, which achieves nearly optimal Cπ∗,k≈n/k for all values of k simultaneously, and experimentally validate that it compares favorably with all rotations rotα , n.
AB - 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←rotα,n(R)⊕X, where rotα , n rotates an n-bit state R by some fixed number α. For example, Microsoft’s RNG uses α= 5 for n= 32 and α= 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 X1, X2, … as independent (but otherwise adversarial) samples from some natural distribution family D. Our contribution is as follows. We define 2-monotone distributions as a rich family D that includes relevant real-world distributions (Gaussian, exponential, etc.), but avoids trivial impossibility results.For any α with gcd (α, n) = 1, we show that rotation accumulates Ω(n) bits of entropy from n independent samples X1, …, Xn from any (unknown) 2-monotone distribution with entropy k> 1.However, we also show some choices of α perform much better than others for a given n. E.g., we show α= 19 is one of the best choices for n= 64 ; in contrast, α= 5 is good, but generally worse than α= 7, for n= 32.More generally, given a permutation π and k≥ 1, we define a simple parameter, the covering number Cπ , k, and show that it characterizes the number of steps before the rule (Formula presented.) accumulates nearly n bits of entropy from independent, 2-monotone samples of min-entropy k each.We build a simple permutation π∗, which achieves nearly optimal Cπ∗,k≈n/k for all values of k simultaneously, and experimentally validate that it compares favorably with all rotations rotα , n.
KW - Entropy accumulation
KW - RNGs
KW - Randomness extractors
UR - http://www.scopus.com/inward/record.url?scp=85115155755&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115155755&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-84259-8_19
DO - 10.1007/978-3-030-84259-8_19
M3 - Conference contribution
AN - SCOPUS:85115155755
SN - 9783030842581
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 548
EP - 576
BT - Advances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
A2 - Malkin, Tal
A2 - Peikert, Chris
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 16 August 2021 through 20 August 2021
ER -