30/03/2017

Intervenant(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 transformation.

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)

Marc.Mezzarobba (at) nulllip6.fr