A search to distinguish reduction for the isomorphism problem on direct sum lattices

At Eurocrypt 2003, Szydlo presented a search to distinguish reduction for the Lattice Isomorphism Problem (LIP) on the integer lat- tice Zn. Here the search problem asks to find an isometry between Zn and an isomorphic lattice, while the distinguish variant asks to distinguish between a list of auxiliary lattices related to Zn. In this work we generalize Szydlo’s search to distinguish reduction in two ways. Firstly, we generalize the reduction to any lattice isomorphic to Γ n, where Γ is a fixed base lattice. Secondly, we allow Γ to be a module lattice over any number field. Assuming the base lattice Γ and the number field K are fixed, our reduction is polynomial in n. As a special case we consider the module lattice O2 used in the module- LIP based signature scheme HAWK, and we show that one can solve the search problem, leading to a full key recovery, with less than 2d2 distinguishing calls on two lattices each, where d is the degree of the power-of-two cyclotomic number field and O its ring of integers.