Crypto Seminar
Speaker
ZHIYE XIE
Ph.D. Program
New York University
When
-
Where
In Person and Virtual - ET
Description
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_{alpha, n}(R) XOR X where 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, ... as \emph{independent} (but otherwise adversarial) samples from some natural distribution family ${\cal D}$.
Our contribution is as follows.
- We define 2-monotone distributions as a rich family ${\cal 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,...,X_n from any (unknown) 2-monotone distribution with entropy k > 1.
- However, we also show 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 > 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,...,R_n) <- (R_{pi(1)},..., R_{pi(n)}) XOR 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 rot_{alpha,n}.