Cryptanalysis of rank-2 module-LIP in Totally Real Number Fields

Guilhem Mureau; Alice Pellet-Mary; Heorhii Pliatsok; Alexandre Wallet

Paper 2024/441

Cryptanalysis of rank-2 module-LIP in Totally Real Number Fields

Guilhem Mureau, Inria Bordeaux - Sud-Ouest Research Centre, Institut de Mathématiques de Bordeaux

Alice Pellet-Mary

, Institut de Mathématiques de Bordeaux, Centre National de la Recherche Scientifique, Inria Bordeaux - Sud-Ouest Research Centre

Heorhii Pliatsok, Insitute of Mathematics, NAS of Ukraine

Alexandre Wallet

, University of Rennes 1, Inria, Centre National de la Recherche Scientifique, Institut de Recherche en Informatique et Systèmes Aléatoires

Abstract

At Asiacrypt 2022, Ducas, Postlethwaite, Pulles, and van Woerden introduced the Lattice Isomorphism Problem for module lattices in a number field $K$ (module-LIP). In this article, we describe an algorithm solving module-LIP for modules of rank in , when 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 ), and a large class of totally real number fields (including the maximal real subfield of cyclotomic fields) it runs in classical polynomial time in the degree of the field and the residue at 1 of the Dedekind zeta function of the field (under reasonable number theoretic assumptions). We provide a proof-of-concept code running over the maximal real subfield of some cyclotomic fields. As a side contribution, we also provide some algorithmic and theoretical tools for the future study of the module-LIP problem.

Note: This is the full-length version of the article accepted to Eurocrypt 2024, containing proofs, more details about the implementation and a worst-case to average-case reduction for module-LIP.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: A minor revision of an IACR publication in EUROCRYPT 2024
DOI: 10.1007/978-3-031-58754-2_9
Keywords: Module lattices Lattice Isomorphism Problem Cryptanalysis
Contact author(s): guilhem mureau @ math u-bordeaux fr
alice pellet-mary @ math u-bordeaux fr
georgiipliatsok @ icloud com
alexandre wallet @ inria fr
History: 2024-05-22: revised; 2024-03-14: received; See all versions
Short URL: https://ia.cr/2024/441
License: CC BY

BibTeX

@misc{cryptoeprint:2024/441,
      author = {Guilhem Mureau and Alice Pellet-Mary and Heorhii Pliatsok and Alexandre Wallet},
      title = {Cryptanalysis of rank-2 module-{LIP} in Totally Real Number Fields},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/441},
      year = {2024},
      doi = {10.1007/978-3-031-58754-2_9},
      url = {https://eprint.iacr.org/2024/441}
}