This is the discussion thread for the first session of season three of The Isogeny Club , where Luciano presents his talk titled: Faster (2,2)-isogenies for Faster Festive Encryption
Abstract:
One of the subroutines underlying some recent isogeny-based cryptosystems is the computation of chains of (2,2)-isogenies between products of elliptic curves. So far, the only method to compute such isogenies relies on ad-hoc methods for the gluing and splitting, and Richelot isogenies for the intermediate steps. Despite being mathematically elegant and having satisfactory performance for cryptanalytic purposes, this method is definitely not efficient enough for constructive applications. Among these constructive applications, we can find FESTA, an efficient isogeny-based public-key encryption protocol based on a constructive application of the SIDH attacks.
In this talk, taking FESTA as a use case, we present new algorithms to compute chains of (2,2)-isogenies between products of elliptic curves in the theta model. Their implementation in the programming language Rust and the computer algebra system SageMath has incredible performance. In SageMath, our implementation achieves a 10 times speed up for the codomain computation and more than 20 times speed up for evaluation time compared to the one in FESTA. The Rust implementation has been written with cryptographic applications in mind and so has been built to run in constant time. For smaller characteristic, the Rust code runs approximately 40 times faster than the same algorithms written in SageMath, and more than 2 times as fast for very large characteristic. Concretely, on an Intel Core i7-9750H CPU with a clock speed of 2.6 GHz with turbo-boost disabled,an isogeny chain of length 208 between elliptic products over Fp2 with a 254-bit characteristic runs in only 2.85 ms.
Video:
