Paper 2023/194

Hull Attacks on the Lattice Isomorphism Problem

Léo Ducas, Centrum Wiskunde & Informatica, Leiden University
Shane Gibbons, Centrum Wiskunde & Informatica, Leiden University

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 two independent works [Ducas & van Woerden, EUROCRYPT 2022, Bennett et al. preprint 2021]. 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 work we study the cryptanalytic role of an adaptation of the hull to the lattice setting, namely, the $s$-hull. We first show that the $s$-hull is not helpful for creating an arithmetic distinguisher. More specifically, the genus of the $s$-hull can be efficiently predicted from $s$ and the original genus and therefore carries no extra information. However, we also 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. This second result gives a counterexample to the general hardness conjecture of LIP proposed by Ducas & van Woerden. 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 dual and their hulls, leaving only the original lattice to an attacker. Remarkably, this is already the case in proposed instantiations, namely the trivial lattice $\mathbb{Z}^n$ and the Barnes-Wall lattices.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in PKC 2023
Lattice IsomorphismHullCode EquivalenceGraph IsomorphismCryptanalysis
Contact author(s)
Shane Gibbons @ cwi nl
2023-02-15: approved
2023-02-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Léo Ducas and Shane Gibbons},
      title = {Hull Attacks on the Lattice Isomorphism Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2023/194},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.