2023-11-11
Provable lattice reduction of Zn with blocksize n/2
Publication
Publication
The Lattice Isomorphism Problem (LIP) is the computational task of recovering, assuming it exists, an orthogonal linear transformation sending one lattice to another. For cryptographic purposes, the case of the trivial lattice Zn is of particular interest (Z LIP). 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 Z LIP can indeed be solved by making polynomially many calls to a Shortest Vector Problem oracle in dimension at most n/ 2 + 1 .
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1007/s10623-023-01320-7 | |
| Designs, Codes and Cryptography | |
| A Reduction Theory for Codes and Lattices in Cryptography | |
|
Ducas, L. (2023). Provable lattice reduction of Zn with blocksize n/2. Designs, Codes and Cryptography. doi:10.1007/s10623-023-01320-7 |
|
