Compressed M-SIDH: An Instance of Compressed SIDH-like Schemes with Isogenies of Highly Composite Degrees

Kaizhan Lin; Jianming Lin; Shiping Cai; Weize Wang; Chang-An Zhao

Paper 2023/136

Compressed M-SIDH: An Instance of Compressed SIDH-like Schemes with Isogenies of Highly Composite Degrees

Kaizhan Lin, Sun Yat-sen University

Jianming Lin, Sun Yat-sen University

Shiping Cai, Sun Yat-sen University

Weize Wang, Sun Yat-sen University

Chang-An Zhao, Sun Yat-sen University

Abstract

Recently, SIDH was broken by a series of attacks. To avoid the attacks, several new countermeasures, such as M-SIDH and binSIDH, have been developed. Different from SIDH, the new SIDH-like schemes have relatively large public key sizes. Besides, the orders of the torsion groups considered in new SIDH-like schemes are the products of many primes. Therefore, the key compression techniques in SIDH can not be directly applied to these schemes. It remains an open problem to compress the public key in new SIDH-like schemes. This paper takes M-SIDH as an instance to explore how to compress the public key in new SIDH-like schemes efficiently. We propose compressed M-SIDH, which is reminiscent of compressed SIDH. We also show that our approach to compress the public key of M-SIDH is valid and prove that compressed M-SIDH is secure as long as M-SIDH is secure. In addition, new algorithms to accelerate the performance of public-key compression in M-SIDH are presented in this paper. We provide a proof-of-concept implementation of compressed M-SIDH in SageMath. Experimental results show that our approach fits well with compressed M-SIDH. The techniques proposed in this work also benefit public-key compression in other SIDH-like protocols, such as binSIDH and terSIDH. Besides, our method for torsion basis generation has the potential to improve the performance of SQALE and dCSIDH.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Designs, Codes and Cryptography
Keywords: M-SIDH Post-quantum Cryptography Public-key Compression SIDH
Contact author(s): linkzh5 @ mail2 sysu edu cn
linjm28 @ mail2 sysu edu cn
caishp6 @ mail2 sysu edu cn
wangwz @ mail2 sysu edu cn
zhaochan3 @ mail sysu edu cn
History: 2024-03-18: last of 2 revisions; 2023-02-06: received; See all versions
Short URL: https://ia.cr/2023/136
License: CC BY

BibTeX

@misc{cryptoeprint:2023/136,
      author = {Kaizhan Lin and Jianming Lin and Shiping Cai and Weize Wang and Chang-An Zhao},
      title = {Compressed M-SIDH: An Instance of Compressed SIDH-like Schemes with Isogenies of Highly Composite Degrees},
      howpublished = {Cryptology ePrint Archive, Paper 2023/136},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/136}},
      url = {https://eprint.iacr.org/2023/136}
}