Title: Hull attacks on the Lattice Isomorphism Problem
Abstract: The lattice isomorphism problem (LIP) asks
one to find an isometry between two lattices. It has
recently been proposed as a foundation for cryptography
in independent works. This problem is the lattice variant
of the code equivalence problem, on which the notion of
the hull of a code can lead to devastating attacks.
In this talk I will present the cryptanalytic role of an
adaptation of the hull to the lattice setting, which we call the
s-hull. Specifically, we show that the hull can be helpful
for geometric attacks: for certain lattices the minimal
distance of the hull is relatively smaller than that of the
original lattice, and this can be exploited. The attack cost
remains exponential, but the constant in the exponent is halved.
Our results suggests that one should be very considerate
about the geometry of hulls when instantiating LIP for
cryptography. They also point to unimodular lattices as attractive
options, as they are equal to their own hulls. Remarkably,
this is already the case in proposed instantiations,
namely the trivial lattice Z^n and the Barnes-Wall lattices.
