Constant time lattice reduction in dimension 4 with application to SQIsign

Hanyecz, Ottó and Karenin, Alexander and Kirshanova, Elena and Kutas, Péter and Schaeffler, Sina (2025) Constant time lattice reduction in dimension 4 with application to SQIsign. IACR TRANSACTIONS ON CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS, 2025 (2). pp. 511-534. ISSN 2569-2925

Preview

Text TCHES2025_2_17.pdf - Published Version Available under License Creative Commons Attribution. Download (694kB) | Preview

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.

Actions (login required)

Edit Item