Paper 2023/447

Provable Lattice Reduction of Zn with Blocksize n/2

Léo Ducas, Centrum Wiskunde & Informatica, Leiden University
Abstract

The Lattice Isomorphism Problem (LIP) is the computational task of recovering, assuming it exists, a orthogonal linear transformation sending one lattice to another. For cryptographic purposes, the case of the trivial lattice Zn is of particular interest (ZLIP). Heuristic analysis suggests that the BKZ algorithm with blocksize β=n/2+o(n) solves such instances (Ducas, Postlethwaite, Pulles, van Woerden, ASIACRYPT 2022). In this work, I propose a provable version of this statement, namely, that ZLIP can indeed be solved by making polynomially many calls to a Shortest Vector Problem (SVP) oracle in dimension at most .

Note: Update: many typos fixed, and substantial editorial improvements.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Lattice Isomorphism ProblemLattice ReductionProvable Algorithm
Contact author(s)
ducas @ cwi nl
History
2023-09-05: last of 2 revisions
2023-03-27: received
See all versions
Short URL
https://ia.cr/2023/447
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/447,
      author = {Léo Ducas},
      title = {Provable Lattice Reduction of $\mathbb Z^n$ with Blocksize $n/2$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/447},
      year = {2023},
      url = {https://eprint.iacr.org/2023/447}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.