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.


Erratum

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.


Homepage