Abstract
This paper studies a problem from lattice-based cryptography: deciding whether two lattices are essentially the same, and if so, finding the transformation that maps one to the other. In cryptography, these tasks are often separated into an easier distinguishing problem (telling whether two lattices match) and a harder search problem (explicitly recovering the mapping). Previous work showed how to convert a distinguisher into a search algorithm, but only for very simple lattices.
The authors generalize this connection to much richer lattice structures built by repeating a fixed base lattice many times, including cases with additional algebraic structure. They show that the same kind of reduction still works, and analyze how its cost grows as the lattice gets larger. As an application, they explain how this result impacts the security analysis of certain lattice-based signature schemes: an attacker who can merely distinguish related lattices could, with limited extra effort, solve the harder underlying problem. Overall, the paper strengthens the theoretical foundations behind assumptions used in post-quantum cryptography and clarifies how different lattice problems are linked.
Significantly, this approach has a direct cryptanalytic application to HAWK, a prominent candidate in the NIST additional signatures standardization process. Research such as this helps us better understand the security foundations of the submission and helps validate it as part of the decision-making process.
