The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents

Abstract

Recent independent analyses by Bonnetain–Schrottenloher and Peikert in Eurocrypt 2020 significantly reduced the estimated quantum security of the isogeny-based commutative group action key-exchange protocol CSIDH. This paper refines the estimates of a resource-constrained quantum collimation sieve attack to give a precise quantum security to CSIDH. Furthermore, we optimize large CSIDH parameters for performance while still achieving the NIST security levels 1, 2, and 3. Finally, we provide a C-code constant-time implementation of those CSIDH large instantiations using the square-root-complexity Vélu’s formulas recently proposed by Bernstein, De Feo, Leroux and Smith.