Paper 2020/1520

The SQALE of CSIDH: Square-root vélu Quantum-resistant isogeny Action with Low Exponents

Jorge Chávez-Saab and Jesús-Javier Chi-Domínguez and Samuel Jaques and Francisco Rodríguez-Henríquez

Abstract

Recent analyses reported independently by Bonnetain-Schrottenloher and Peikert in Eurocrypt 2020, significantly reduce the estimated quantum security provided by the isogeny-based commutative group action protocol CSIDH. In this paper the CSIDH quantum security is revisited through a comprehensive analysis of the computational cost associated to the quantum collimation sieve attack. Furthermore, we propose a set of primes that can be applied to obtain large instantiations of CSIDH achieving the NIST security levels 1, 2, and 3. Finally, we provide a C-code constant-time implementation of those CSIDH large instantiations supported by the new Vélu formulae.

Note: Small modifications in the introduction and the Acknowledgements have been extended.