Paper 2023/753

A Faster Software Implementation of SQISign

Kaizhan Lin, School of Mathematics, Sun Yat-sen University, Guangzhou, China
Weize Wang, School of Mathematics, Sun Yat-sen University, Guangzhou, China
Zheng Xu, Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, Beijing, China, Yau Mathematical Sciences Center, Tsinghua University, Beijing, China
Chang-An Zhao, School of Mathematics, Sun Yat-sen University, Guangzhou, China, Guangdong Key Laboratory of Information Security, Guangzhou, China
Abstract

Isogeny-based cryptography is famous for its short key size. As one of the most compact digital signatures, SQISign (Short Quaternion and Isogeny Signature) is attractive among post-quantum cryptography, but it is ineffcient compared to other post-quantum competitors because of complicated procedures in ideal to isogeny translation, which is the effciency bottleneck of the signing phase. In this paper, we recall the current implementation of SQISign and mainly discuss how to improve the execution of ideal to isogeny translation in SQISign. To be precise, we modify the SigningKLPT algorithm to accelerate the performance of generating the ideal $I_\sigma$. In addition, we explore how to save one of the two elliptic curve discrete logarithms and compute the remainder with the help of the reduced Tate pairing correctly and effciently. We speed up other procedures in ideal to isogeny translation with various techniques as well. It should be noted that our improvements also benefit the performances of key generation and verification in SQISign. In particular, in the instantiation with p3923 the improvements lead to a speedup of 8.82%, 8.50% and 18.94% for key generation, signature and verification, respectively

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Isogeny-based CryptographySQISignPairingsDiscrete Logarithms
Contact author(s)
linkzh5 @ mail2 sysu edu cn
wangwz @ mail2 sysu edu cn
xuzheng @ bimsa cn
zhaochan3 @ mail sysu edu cn
History
2023-05-25: revised
2023-05-25: received
See all versions
Short URL
https://ia.cr/2023/753
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/753,
      author = {Kaizhan Lin and Weize Wang and Zheng Xu and Chang-An Zhao},
      title = {A Faster Software Implementation of SQISign},
      howpublished = {Cryptology ePrint Archive, Paper 2023/753},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/753}},
      url = {https://eprint.iacr.org/2023/753}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.