Lattices in Algorithmics and Cryptography
Jaime Gutierrez, University of Cantabria, Santander, Spain
Friday, October 5, 2007, at U. of Waterloo.
Abstract:
Our world is not linear. Many phenomena, however, are often ``linearized''
because only then a reasonably well-working mathematical machinery can
describe the phenomena and produce meaningful forecasts.
Lattices are geometric objects that have been used to solve many problems in
mathematics and computer science. Lattice reduction strategies or the so
called LLL-techniques seem inherently linear. The general idea of this
technique is to translate our non linear problem to finding a short vector
in a lattice built from the nonlinear equation. Then, the so-called Shortest
Vector Problem and Closest Vector Problem in lattices play a major role. In
recent years, these techniques have been used repeatedly in algorithmic,
coding theory and cryptography.
In this talk I will investigate lattice reduction technique on some
algebraic algorithms and cryptography problems, namely - finding roots of
multivariate integer polynomials and attacking crypto-systems - Integer
factoring and RSA - computing subfields - predicting pseudorandom number
congruential generators over Elliptic Curves - Cayley graphs: Groebner basis
and LLL-reduced basis.
|