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

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

Available format(s)
Publication info
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
2023-05-25: revised
2023-05-25: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.