Paper 2021/259

Don't forget the constant-time in CSURF

Jesús-Javier Chi-Domínguez and Krijn Reijnders

Abstract

CSURF (CSIDH on the surface) was recently proposed by Castryck, and Decru in PQCrypto-2020, and then improved by the radical isogeny formulae in Asiacrypt-2020. The main advantage of using CSURF and radical isogenies is the possibility of using isogenies of degree two and radical isogeny chains of odd degree requiring only a single random sampling of points. This work addresses the practical implications of a constant-time implementation of CSURF and the radical isogeny procedures. In particular, this paper introduces the first constant-time formulation and implementation of the radical isogenies using projective representation, which are twice as efficient as the original radical isogeny formulae. Nevertheless, the overhead introduced by going to constant-time is significant: in terms of finite field operations, our experiments illustrate that the speed-up of using a constant-time CSURF-512 is reduced to 1.64% in comparison to the fastest state-of-the-art constant-time CSIDH-512 implementation. Furthermore, these savings disappear when using constant-time radical isogenies and when moving to higher parameter sets. This negatively answers the open question from Castryck and Decru: constant-time CSIDH implementations outperform both CSURF and radical isogenies.