International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cryptanalysis of rank-2 module-LIP in totally real number fields

Authors:
Guilhem Mureau , Inria, Univ. Bordeaux
Alice Pellet-Mary , CNRS, Univ. Bordeaux
Georges Pliatsok , Inria, Univ Rennes, Irisa, CNRS, France
Alexandre Wallet , Inria, Univ Rennes, Irisa, CNRS, France
Download:
DOI: 10.1007/978-3-031-58754-2_9 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
Abstract: We formally define the Lattice Isomorphism Problem for module lattices (module-LIP) in a number field K. This is a generalization of the problem defined by Ducas, Postlethwaite, Pulles, and van Woerden (Asiacrypt 2022), taking into account the arithmetic and algebraic specificity of module lattices from their representation using pseudo-bases. We also provide the corresponding set of algorithmic and theoretical tools for the future study of this problem in a module setting. Our main contribution is an algorithm solving module-LIP for modules of rank 2 in K^2, when K is a totally real number field. Our algorithm exploits the connection between this problem, relative norm equations and the decomposition of algebraic integers as sums of two squares. For a large class of modules, including O_K^2, it runs in classical polynomial time (under reasonable number theoretic assumptions). We provide a proof-of-concept code running over the maximal real subfield of cyclotomic fields.
BibTeX
@inproceedings{eurocrypt-2024-33939,
  title={Cryptanalysis of rank-2 module-LIP in totally real number fields},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-58754-2_9},
  author={Guilhem Mureau and Alice Pellet-Mary and Georges Pliatsok and Alexandre Wallet},
  year=2024
}