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 $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 $\mathcal{O}_K^2$), 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 latticesLattice Isomorphism ProblemCryptanalysis
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.