An Alternative Approach for Computing Discrete Logarithms in Compressed SIDH
This incremental improvement addresses efficiency in post-quantum cryptography for secure communication systems.
The paper tackles the problem of reducing the number of discrete logarithm computations in compressed SIDH and SIKE from 4 to 3, by introducing novel methods that trade off with lookup table computation and memory efficiency, with implementation results showing close efficiency to prior work and better performance in special cases.
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. In this paper, we propose novel methods to compute only 3 discrete logarithms instead of 4, in exchange for computing a lookup table efficiently. The algorithms also allow us to make a trade-off between memory and efficiency. Our implementation shows that the efficiency of our algorithms is close to that of the previous work, and our algorithms perform better in some special cases.