Title: An Algorithmic Reduction Theory for Binary Codes: LLL and more
Joint work with Thomas Debris-Alazard and Wessel van Woerden
| Speaker: | Léo Ducas |
| Affiliation: | Centrum Wiskunde & Informatica (CWI) |
| Zoom: | Please email Emma Watson |
Abstract:
Lattice
reduction
is
the
task
of
finding
a
basis
of
short
and
somewhat
orthogonal
vectors
of
a
given
lattice.
In
1985
Lenstra,
Lenstra
and
Lovasz
proposed
a
polynomial
time
algorithm
for
this
task,
with
an
application
to
factoring
rational
polynomials.
Since
then,
the
LLL
algorithm
has
found
countless
application
in
algorithmic
number
theory
and
in
cryptanalysis.
There
are
many
analogies
to
be
drawn
between
Euclidean
lattices
and
linear
codes
over
finite
fields.
In
this
work,
we
propose
to
extend
the
range
of
these
analogies
by
considering
the
task
of
reducing
the
basis
of
a
binary
code.
In
fact,
all
it
takes
is
to
choose
the
adequate
notion
mimicking
Euclidean
orthogonality
(namely
orthopodality),
after
which,
all
the
required
notions,
arguments,
and
algorithms
unfold
before
us,
in
quasi-perfect
analogy
with
lattices.