Paper 2025/027
Constant time lattice reduction in dimension 4 with application to SQIsign
, Technology Innovation Institute, Eőtvős Loránd University, University of BirminghamAbstract
In this paper we propose a constant time lattice reduction algorithm for integral dimension-4 lattices. Motivated by its application in the SQIsign post-quantum signature scheme, we provide for the first time a constant time LLL-like algorithm with guarantees on the length of the shortest output vector. We implemented our algorithm and ensured through various tools that it indeed operates in constant time. Our experiments suggest that in practice our implementation outputs a Minkowski reduced basis and thus can replace a non constant time lattice reduction subroutine in SQIsign.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- LLLBKZconstant timeisogeniesSQIsign
- Contact author(s)
-
ohanyecz @ inf elte hu
alexander karenin @ tii ae
elenakirshanova @ gmail com
kutasp @ gmail com
sschaeffle @ ethz ch - History
- 2025-01-08: approved
- 2025-01-08: received
- See all versions
- Short URL
- https://ia.cr/2025/027
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/027,
author = {Otto Hanyecz and Alexander Karenin and Elena Kirshanova and Péter Kutas and Sina Schaeffler},
title = {Constant time lattice reduction in dimension 4 with application to {SQIsign}},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/027},
year = {2025},
url = {https://eprint.iacr.org/2025/027}
}
