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).
We thank Nicolas Brisebarre for pointing out the following error.
In lines 10 and 11 of the algorithm of Figure 1, alpha (alpha+1)/2 should be replaced by (alpha+1)(alpha+2)/2.
Homepage