Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / isogeny-based cryptography, CSIDH, CSURF, radical isogenies, constant-time

Date: received 3 Mar 2021, last revised 7 Apr 2021

Contact author: jesus chidominguez at tuni fi,krijn reijnders@ru nl

Available format(s): PDF | BibTeX Citation

Version: 20210407:131100 (All versions of this report)

Short URL: ia.cr/2021/259


[ Cryptology ePrint archive ]