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.
We thank Nicolas Brisebarre for pointing out the following error.
In appendix, the induction in the proof of Theorem 2 is incorrect. The sqrt(n) term should
in fact be sqrt(n(n-1)...(n-d+1)). This is obtained by triangularizing, as in the current proof,
and then using Hadamard's inequality. In the statement of Theorem 2, the sqrt(n) term should
be replaced by sqrt(n(n-1)...(n-d+1)).
In the bound on Det(B3) that is provided just after Lemma 7, the sqrt(d) term may be replaced
by (d alpha)^O(d alpha). In Theorem 10, an extra term (d alpha)^O(d alpha) should be added.
As a result of this updated Theorem 10, the condition log d = O(alpha) is too permissive.
It may be replaced by d = O(alpha^3 / log alpha), so that the extra term (d alpha)^O(d alpha)
2^O(alpha^4), a term already present in the bound of Theorem 10. The condition
d = O(alpha^3 / log alpha) suffices for Corollaries 4 and 5.