Paper 2025/1563

Optimized Constant-Time Implementation of terSIDH

Abstract

Since supersingular isogeny Diffie-Hellman (SIDH) was broken by a polynomial-time attack, several countermeasures were proposed. Among them, terSIDH has been highlighted for its high performance, yet it exposes a side-channel vulnerability. The total isogeny degree depends on the private key, causing variation in isogeny computation times. This dependency makes terSIDH susceptible to timing attacks. The ratio between the worst- and the best-case execution times of terSIDH was about 32.67 times. In this work, we propose the first constant-time terSIDH. By adding dummy operations, we reduce the dependency of isogeny computations on the private key, ensuring that the algorithm’s execution time remains constant regardless of the private key. Since such countermeasures are generally slower than their non-constant-time counterparts, we applied additional optimizations to mitigate this overhead. Moreover, we present the first C implementation of terSIDH having 128-bit security. We compared our method against CSIDH-4096, a representative isogeny-based key exchange protocol with the same security level. For key generation, the worst-case of terSIDH, CSIDH-4096, and our constant-time method take 1.77 s, 5.18 s, and 1.58 s, respectively. These results demonstrate that our proposed constant-time method is faster than the worst-case of terSIDH while also being significantly more efficient than CSIDH-4096.