On the Lattice Isomorphism Problem

Abstract

We study the Lattice Isomorphism Problem (LIP), in which given two lattices ℒ1 and ℒ2 the goal is to decide whether there exists an orthogonal linear transformation mapping L1 to ℒ2. Our main result is an algorithm for this problem running in time nO(n) times a polynomial in the input size, where n is the rank of the input lattices. A crucial component is a new generalized isolation lemma, which can isolate n linearly independent vectors in a given subset of ℤn and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.