Paper 2021/1528

An Alternative Approach for Computing Discrete Logarithms in Compressed SIDH

Kaizhan Lin
Weize Wang
Lin Wang
Chang-An Zhao

Currently, public-key compression of supersingular isogeny Diffie-Hellman (SIDH) and its variant, supersingular isogeny key encapsulation (SIKE) involve pairing computation and discrete logarithm computation. Both of them require large storage for precomputation to accelerate the performance. In this paper, we propose a novel method to compute only three discrete logarithms instead of four, in exchange for computing a lookup table efficiently. We also suggest another alternative method to compute discrete logarithms with small storage. Our implementation shows that the efficiency of our first method is close to that of the previous work, and our algorithms perform better in some special cases. Although the implementation of the second method is not as efficient as the state of the art, the storage is reduced by a factor of about 3:77 to about 22:86. In particular, the storage requirement for discrete logarithms of the order-$3^{e_3}$ multiplicative group decreases from 390.00 KiB to 17.06 KiB when using the 751-bit prime. We believe that the latter method will be highly attractive in memory constrained environments.

Available format(s)
Public-key cryptography
Publication info
Isogeny-based Cryptography SIDH SIKE Public-key Compression Discrete Logarithms
Contact author(s)
linkzh5 @ mail2 sysu edu cn
2022-10-09: last of 3 revisions
2021-11-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kaizhan Lin and Weize Wang and Lin Wang and Chang-An Zhao},
      title = {An Alternative Approach for Computing Discrete Logarithms in Compressed SIDH},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1528},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.