SQIsign2D–West: The Fast, the Small, and the Safer

Andrea Basso; Pierrick  Dartois; Luca  De Feo; Antonin  Leroux; Luciano Maino; Giacomo  Pope; Damien  Robert; Benjamin Wesolowski

doi:10.1007/978-981-96-0891-1_11

SQIsign2D–West: The Fast, the Small, and the Safer

Andrea Basso^*, Pierrick Dartois, Luca De Feo, Antonin Leroux, Luciano Maino, Giacomo Pope, Damien Robert, Benjamin Wesolowski

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

9 Citations (Scopus)

4 Downloads (Pure)

Abstract

We introduce SQIsign2D–West, a variant of SQIsign using two-dimensional isogeny representations.

SQIsignHD introduced four- and eight-dimensional isogeny representations to improve signing times and provable security of SQIsign, at the cost of slower verification. It left open the question of leveraging two-dimensional representations, which we solve here by introducing new algorithmic tools. These lead to a “best-of-both-worlds” scheme: our signing times are only 2 to 3 slower than SQIsignHD but 10 to 15 faster than SQIsign, our security proof rigorously reduces to an assumption similar to the one behind SQIsignHD, and our verification times are the fastest among all present variants of SQIsign. Additionally, like SQIsignHD, SQIsign2D–West favourably scales to high levels of security.

Concretely, for NIST level I we achieve signing times of 80 ms and verifying times of 4.5 ms, using optimised arithmetic for the x86_64 architecture. For NIST level V, we achieve 470 ms for signing and 31 ms for verifying.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2024
Subtitle of host publication	30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III
Editors	Kai-Min Chung, Yu Sasaki
Publisher	Springer, Singapore
Pages	339-370
Number of pages	32
ISBN (Electronic)	9789819608911
ISBN (Print)	9789819608904
DOIs	https://doi.org/10.1007/978-981-96-0891-1_11
Publication status	Published - 12 Dec 2024
Event	ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security - Kolkata, India Duration: 9 Dec 2024 → 13 Dec 2024 https://asiacrypt.iacr.org/2024/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	15486
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	ASIACRYPT 2024
Country/Territory	India
City	Kolkata
Period	9/12/24 → 13/12/24
Internet address	https://asiacrypt.iacr.org/2024/

Bibliographical note

Publisher Copyright:
© 2025 International Association for Cryptologic Research.

Access to Document

10.1007/978-981-96-0891-1_11

Full-text PDF (accepted manuscript)
This is the accepted author manuscript (AAM) of the article which has been made Open Access under the University of Bristol's Scholarly Works Policy. The final published version (Version of Record) can be found on the publisher's website. The copyright of any third-party content, such as images, remains with the copyright holder.
Accepted author manuscript, 822 KBLicence: CC BY

Handle.net

Persistent link

Cite this

Basso, A., Dartois, P., De Feo, L., Leroux, A., Maino, L., Pope, G., Robert, D., & Wesolowski, B. (2024). SQIsign2D–West: The Fast, the Small, and the Safer. In K.-M. Chung, & Y. Sasaki (Eds.), Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III (pp. 339-370). (Lecture Notes in Computer Science; Vol. 15486). Springer, Singapore. https://doi.org/10.1007/978-981-96-0891-1_11

Basso, Andrea ; Dartois, Pierrick ; De Feo, Luca et al. / SQIsign2D–West : The Fast, the Small, and the Safer. Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III. editor / Kai-Min Chung ; Yu Sasaki. Springer, Singapore, 2024. pp. 339-370 (Lecture Notes in Computer Science).

@inproceedings{f9e28e47d23241039758eedde9e31d09,

title = "SQIsign2D–West: The Fast, the Small, and the Safer",

abstract = "We introduce SQIsign2D–West, a variant of SQIsign using two-dimensional isogeny representations. SQIsignHD introduced four- and eight-dimensional isogeny representations to improve signing times and provable security of SQIsign, at the cost of slower verification. It left open the question of leveraging two-dimensional representations, which we solve here by introducing new algorithmic tools. These lead to a “best-of-both-worlds” scheme: our signing times are only 2 to 3 slower than SQIsignHD but 10 to 15 faster than SQIsign, our security proof rigorously reduces to an assumption similar to the one behind SQIsignHD, and our verification times are the fastest among all present variants of SQIsign. Additionally, like SQIsignHD, SQIsign2D–West favourably scales to high levels of security. Concretely, for NIST level I we achieve signing times of 80 ms and verifying times of 4.5 ms, using optimised arithmetic for the x86\_64 architecture. For NIST level V, we achieve 470 ms for signing and 31 ms for verifying.",

author = "Andrea Basso and Pierrick Dartois and \{De Feo\}, Luca and Antonin Leroux and Luciano Maino and Giacomo Pope and Damien Robert and Benjamin Wesolowski",

note = "Publisher Copyright: {\textcopyright} 2025 International Association for Cryptologic Research. ; ASIACRYPT 2024 : 30th International Conference on the Theory and Application of Cryptology and Information Security ; Conference date: 09-12-2024 Through 13-12-2024",

year = "2024",

month = dec,

day = "12",

doi = "10.1007/978-981-96-0891-1\_11",

language = "English",

isbn = "9789819608904",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Singapore",

pages = "339--370",

editor = "Kai-Min Chung and Yu Sasaki",

booktitle = "Advances in Cryptology – ASIACRYPT 2024",

address = "Singapore",

url = "https://asiacrypt.iacr.org/2024/",

}

Basso, A, Dartois, P, De Feo, L, Leroux, A, Maino, L, Pope, G, Robert, D & Wesolowski, B 2024, SQIsign2D–West: The Fast, the Small, and the Safer. in K-M Chung & Y Sasaki (eds), Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III. Lecture Notes in Computer Science, vol. 15486, Springer, Singapore, pp. 339-370, ASIACRYPT 2024, Kolkata, India, 9/12/24. https://doi.org/10.1007/978-981-96-0891-1_11

SQIsign2D–West: The Fast, the Small, and the Safer. / Basso, Andrea; Dartois, Pierrick ; De Feo, Luca et al.
Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III. ed. / Kai-Min Chung; Yu Sasaki. Springer, Singapore, 2024. p. 339-370 (Lecture Notes in Computer Science; Vol. 15486).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - SQIsign2D–West

T2 - ASIACRYPT 2024

AU - Basso, Andrea

AU - Dartois, Pierrick

AU - De Feo, Luca

AU - Leroux, Antonin

AU - Maino, Luciano

AU - Pope, Giacomo

AU - Robert, Damien

AU - Wesolowski, Benjamin

PY - 2024/12/12

Y1 - 2024/12/12

N2 - We introduce SQIsign2D–West, a variant of SQIsign using two-dimensional isogeny representations. SQIsignHD introduced four- and eight-dimensional isogeny representations to improve signing times and provable security of SQIsign, at the cost of slower verification. It left open the question of leveraging two-dimensional representations, which we solve here by introducing new algorithmic tools. These lead to a “best-of-both-worlds” scheme: our signing times are only 2 to 3 slower than SQIsignHD but 10 to 15 faster than SQIsign, our security proof rigorously reduces to an assumption similar to the one behind SQIsignHD, and our verification times are the fastest among all present variants of SQIsign. Additionally, like SQIsignHD, SQIsign2D–West favourably scales to high levels of security. Concretely, for NIST level I we achieve signing times of 80 ms and verifying times of 4.5 ms, using optimised arithmetic for the x86_64 architecture. For NIST level V, we achieve 470 ms for signing and 31 ms for verifying.

AB - We introduce SQIsign2D–West, a variant of SQIsign using two-dimensional isogeny representations. SQIsignHD introduced four- and eight-dimensional isogeny representations to improve signing times and provable security of SQIsign, at the cost of slower verification. It left open the question of leveraging two-dimensional representations, which we solve here by introducing new algorithmic tools. These lead to a “best-of-both-worlds” scheme: our signing times are only 2 to 3 slower than SQIsignHD but 10 to 15 faster than SQIsign, our security proof rigorously reduces to an assumption similar to the one behind SQIsignHD, and our verification times are the fastest among all present variants of SQIsign. Additionally, like SQIsignHD, SQIsign2D–West favourably scales to high levels of security. Concretely, for NIST level I we achieve signing times of 80 ms and verifying times of 4.5 ms, using optimised arithmetic for the x86_64 architecture. For NIST level V, we achieve 470 ms for signing and 31 ms for verifying.

UR - https://asiacrypt.iacr.org/2024/

U2 - 10.1007/978-981-96-0891-1_11

DO - 10.1007/978-981-96-0891-1_11

M3 - Conference Contribution (Conference Proceeding)

SN - 9789819608904

T3 - Lecture Notes in Computer Science

SP - 339

EP - 370

BT - Advances in Cryptology – ASIACRYPT 2024

A2 - Chung, Kai-Min

A2 - Sasaki, Yu

PB - Springer, Singapore

Y2 - 9 December 2024 through 13 December 2024

ER -

Basso A, Dartois P, De Feo L, Leroux A, Maino L, Pope G et al. SQIsign2D–West: The Fast, the Small, and the Safer. In Chung KM, Sasaki Y, editors, Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III. Springer, Singapore. 2024. p. 339-370. (Lecture Notes in Computer Science). doi: 10.1007/978-981-96-0891-1_11

SQIsign2D–West: The Fast, the Small, and the Safer

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this