Constant time lattice reduction in dimension 4 with application to SQIsign
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 vect...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2025-03-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/12056 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850252207781314560 |
|---|---|
| author | Otto Hanyecz Alexander Karenin Elena Kirshanova Péter Kutas Sina Schaeffler |
| author_facet | Otto Hanyecz Alexander Karenin Elena Kirshanova Péter Kutas Sina Schaeffler |
| author_sort | Otto Hanyecz |
| collection | DOAJ |
| description |
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.
|
| format | Article |
| id | doaj-art-2ffe7e68f36c4d59a4e342abde45a98a |
| institution | OA Journals |
| issn | 2569-2925 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj-art-2ffe7e68f36c4d59a4e342abde45a98a2025-08-20T01:57:43ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252025-03-012025210.46586/tches.v2025.i2.511-534Constant time lattice reduction in dimension 4 with application to SQIsignOtto Hanyecz0Alexander Karenin1Elena Kirshanova2Péter Kutas3Sina Schaeffler4Eőtvős Loránd University, Budapest, HungaryTechnology Innovation Institute, Abu Dhabi, UAETechnology Innovation Institute, Abu Dhabi, UAEEőtvős Loránd University, Budapest, Hungary; University of Birmingham, Birmingham, UKETH Zürich, Zürich, Switzerland; IBM Research Europe, Zürich, Switzerland 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. https://tches.iacr.org/index.php/TCHES/article/view/12056LLLBKZconstant timeisogeniesSQIsign |
| spellingShingle | Otto Hanyecz Alexander Karenin Elena Kirshanova Péter Kutas Sina Schaeffler Constant time lattice reduction in dimension 4 with application to SQIsign Transactions on Cryptographic Hardware and Embedded Systems LLL BKZ constant time isogenies SQIsign |
| title | Constant time lattice reduction in dimension 4 with application to SQIsign |
| title_full | Constant time lattice reduction in dimension 4 with application to SQIsign |
| title_fullStr | Constant time lattice reduction in dimension 4 with application to SQIsign |
| title_full_unstemmed | Constant time lattice reduction in dimension 4 with application to SQIsign |
| title_short | Constant time lattice reduction in dimension 4 with application to SQIsign |
| title_sort | constant time lattice reduction in dimension 4 with application to sqisign |
| topic | LLL BKZ constant time isogenies SQIsign |
| url | https://tches.iacr.org/index.php/TCHES/article/view/12056 |
| work_keys_str_mv | AT ottohanyecz constanttimelatticereductionindimension4withapplicationtosqisign AT alexanderkarenin constanttimelatticereductionindimension4withapplicationtosqisign AT elenakirshanova constanttimelatticereductionindimension4withapplicationtosqisign AT peterkutas constanttimelatticereductionindimension4withapplicationtosqisign AT sinaschaeffler constanttimelatticereductionindimension4withapplicationtosqisign |