On the Randomness of Bits Generated by Sufficiently Smooth Functions
Abstract: Elementary functions such as sin or exp may naively
be considered as good generators of random bits: the bit-runs
output by these functions are believed to be statistically random most of
the time. Here we investigate their computational hardness: given a part
of the binary expansion of exp(x), can one recover x? We describe a
heuristic technique to address this type of questions.
It relies upon Coppersmith's heuristic technique --- itself based
on lattice reduction --- for finding the small roots of multivariate
polynomials modulo an integer.
For our needs, we improve the lattice construction step of
Coppersmith's method: we describe a way to
find a subset of a set of vectors that decreases the Minkowski theorem
bound, in a rather general setup including Coppersmith-type lattices.