Paper 2021/1528

An Alternative Approach for Computing Discrete Logarithms in Compressed SIDH

Kaizhan Lin
Weize Wang
Lin Wang
Chang-An Zhao
Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Isogeny-based Cryptography SIDH SIKE Public-key Compression Discrete Logarithms
Contact author(s)
linkzh5 @ mail2 sysu edu cn
History
2022-10-09: last of 3 revisions
2021-11-22: received
See all versions
Short URL
https://ia.cr/2021/1528
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1528,
      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},
      url = {https://eprint.iacr.org/2021/1528}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.