Theory Seminar
"Analysis of Lattice Reduction Algorithms"
Michael Walter
(UCSD)
Tuesday, November 3rd, 2015, 1:00pm
EBU3B, Room 4258
Abstract:
Lattice reduction algorithms take as input an arbitrary lattice basis
and turn them into a "good" basis, for some precise definition of
"good". Alternatively, one can think of them as approximation algorithms
for the Shortest Vector Problem. The most prominent reduction algorithms
are the celebrated LLL algorithm and its block generalization BKZ, which
are important tools in cryptanalysis. Unfortunately, while the LLL
algorithm has a very clean analysis, both in terms of output quality and
running time, the same is not true for BKZ. This complicates
cryptanalysis, since it is not clear how to optimize the trade-off
between output quality and running time.
In this talk, we will recap the LLL algorithms, including its analysis.
We will discuss BKZ and why a similar analysis breaks down in this case.
Finally, we will introduce a variant of BKZ, for which we can prove good
bounds on the output quality and, in certain settings, the running time.
For this, we will model the algorithm as a (relatively simple) dynamical
linear system and show that it converges to a fixed point.