Paper 2021/1528
An Alternative Approach for Computing Discrete Logarithms in Compressed SIDH
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
-
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},
note = {\url{https://eprint.iacr.org/2021/1528}},
url = {https://eprint.iacr.org/2021/1528}
}
