On the Randomness of Bits Generated by Sufficiently Smooth Functions

Damien Stehlé

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.

Download: pdf, BaCSeL-1.0.


Errata

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.


We thank Nicolas Brisebarre and Guillaume Hanrot for pointing out the following error.
In the table on page 10, alpha in O(n) should be replaced by alpha in omega(1) and in o(n).


Homepage