International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Constant time lattice reduction in dimension 4 with application to SQIsign

Authors:
Otto Hanyecz
Alexander Karenin
Elena Kirshanova
Péter Kutas
Sina Schaeffler
Download:
DOI: 10.46586/tches.v2025.i2.511-534
URL: https://tches.iacr.org/index.php/TCHES/article/view/12056
Search ePrint
Search Google
Abstract: In this paper we propose a constant time lattice reduction algorithm for integral dimension-4 lattices. Motivated by its application in the SQIsign postquantum signature scheme, we provide for the first time a constant time LLLlike 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.
BibTeX
@article{tches-2025-35236,
  title={Constant time lattice reduction in dimension 4 with application to SQIsign},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2025},
  pages={511-534},
  url={https://tches.iacr.org/index.php/TCHES/article/view/12056},
  doi={10.46586/tches.v2025.i2.511-534},
  author={Otto Hanyecz and Alexander Karenin and Elena Kirshanova and Péter Kutas and Sina Schaeffler},
  year=2025
}