International Association
for Cryptologic Research

Group actions have been used as a foundation in Public-key Cryptography to provide a framework for hard problems and assumptions. In this work we formalize the Lattice Isomorphism Problem (LIP) within the context of cryptographic group actions. Our main result shows that a quadratic number of queries to a randomized oracle outputting LIP instances sharing the same secret is enough for inverting the group action in polynomial time. We use this result to uncover a family of weak isomorphisms and to derive two new hard problems on quadratic forms equivalent to LIP for the case of lattices with trivial automorphism.