Otto Hanyecz
Eőtvős Loránd University, Budapest, Hungary

Alexander Karenin
Technology Innovation Institute, Abu Dhabi, UAE

Elena Kirshanova
Technology Innovation Institute, Abu Dhabi, UAE

Péter Kutas
Eőtvős Loránd University, Budapest, Hungary; University of Birmingham, Birmingham, UK

Sina Schaeffler
ETH Zürich, Zürich, Switzerland; IBM Research Europe, Zürich, Switzerland

Keywords: LLL, BKZ, constant time, isogenies, 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 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.