Paper 2025/027 Original: eprint.iacr.org/2025/027 ↗
Constant time lattice reduction in dimension 4 with application to SQIsign
Abstract
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.
- History
- 2026-09-22: last updated
- 2025-01-08: published
- Short URL
- https://ia.cr/2025/027
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}