CryptoDB
Hull Attacks on the Lattice Isomorphism Problem
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | PKC 2023 |
| Abstract: | 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 independant works [Ducas & van Worden, EUROCRYPT 2022, Bennett et al. preprint 2021]. This problem is the lattice variant of the code equivalence problem, where 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 to 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 Z^n and the Barnes-Wall lattices. |
BibTeX
@inproceedings{pkc-2023-32726,
title={Hull Attacks on the Lattice Isomorphism Problem},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-31368-4_7},
author={Léo Ducas and Shane Gibbons},
year=2023
}