Sweet and sour lessons from chasing hard-to-round cases in 128-bit
Speaker(s) : Serge Torres (LIP, École normale supérieure de Lyon)
We will report on our experience with the implementation of the
SLZ-algorithm¹ to assess its effectiveness for chasing hard-to-round
cases for exp(x) in 128-bit.
This presentation only requires some familiarity with floating-point
numbers representation. The reach of some of the mentioned concerns
may go beyond the floating-point application field.
We will first recall the Table Maker's Dilemma and justify why
trying to solve it in 128-bit is of interest.
Next, we will cover the transformation of the problem into an
instance tractable with the Coppersmith technique², which is at the
heart of the SLZ-algorithm, and some problems associated with this
We will then deal with lattice reduction issues since the execution
time of this operation dominates the overall algorithm timing.
After providing some experimental results, we will give some
improvement leads and concluding remarks.
1 D. Stehlé, V. Lefèvre, and P. Zimmermann. Searching Worst Cases of
a One-Variable Function Using Lattice Reduction.
2 D. Coppersmith. Finding a Small Root of a Univariate Modular
Equation (princeps publication).
3 D. Boneh and G. Durfee. Cryptanalysis of RSA with Private Key d
less than N ^(0.292) (for the bivariate version)
More details here
Marc.Mezzarobba (at) nulllip6.fr