Cryptology ePrint Archive: Report 2021/1528

An Alternative Approach for Computing Discrete Logarithms in Compressed SIDH

Kaizhan Lin, Weize Wang, Lin Wang, and Chang-An Zhao

Abstract: Currently, public-key compression of supersingular isogeny Diffe-Hellman (SIDH) and its variant, supersingular isogeny key encapsulation (SIKE) involve pairing computation and discrete logarithm computation. In this paper, we propose novel methods to compute only 3 discrete logarithms instead of 4, in exchange for computing a lookup table effciently. The algorithms also allow us to make a trade-off between memory and effciency. Our implementation shows that the effciency of our algorithms is close to that of the previous work, and our algorithms perform better in some special cases.

Category / Keywords: public-key cryptography / Isogeny-based Cryptography, SIDH, SIKE, Public-key Compression, Discrete Logarithms

Date: received 18 Nov 2021, last revised 22 Nov 2021

Contact author: zhaochan3 at mail sysu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20211122:122853 (All versions of this report)

Short URL: ia.cr/2021/1528


[ Cryptology ePrint archive ]