New Techniques for Efficient Isogeny-based Encryption Protocols
Isogeny-based cryptography is known for its low bandwidth requirements, which often come at the cost of slower computations. SIDH, one of the most well-known isogeny-based key exchanges, and the only one submitted to the NIST standardisation process, was broken in 2022 in a series of three breakthrough papers. The attack relies on isogenies between abelian varieties (a generalisation of elliptic curves to higher dimensions), and it leads to a complete key recovery within seconds.
In this talk, we discuss two approaches to obtaining secure protocols that could, eventually, replace SIDH. The first approach involves modifying the SIDH protocol to include simple but effective countermeasures against all known attacks. The technique is based on restricting the set of potential isogenies, so that less information about the secret isogeny (in the form of torsion images) need to be revealed.
The second approach is based on the development of a new PKE, which we call FESTA. The attacks on SIDH rely on higher-dimensional isogenies to make some computations, previously believed to be hard, extremely efficient. In FESTA, we use the same techniques constructively: we build a trapdoor function where the inversion operation consists of recovering an SIDH secret key. From the trapdoor, it is then simple to obtain an IND-CCA PKE through standard transformations.
Andrea Basso is a postdoctoral researcher at the University of Bristol, where he focuses on developing new isogeny-based protocols, with a particular interest in advanced functionalities such as non-interactive key exchanges and oblivious pseudorandom functions. He received his PhD from the University of Birmingham, and he will soon join IBM Research Zurich as a postdoctoral researcher.
Photo © Private