International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Lossy CSI-FiSh: Efficient Signature Scheme with Tight Reduction to Decisional CSIDH-512

Ali El Kaafarani
Shuichi Katsumata
Federico Pintore
DOI: 10.1007/978-3-030-45388-6_6
Search ePrint
Search Google
Abstract: Recently, Beullens, Kleinjung, and Vercauteren (Asiacrypt’19) provided the first practical isogeny-based digital signature, obtained from the Fiat-Shamir (FS) paradigm. They worked with the CSIDH-512 parameters and passed through a new record class group computation. However, as with all standard FS signatures, the security proof is highly non-tight and the concrete parameters are set under the heuristic that the only way to attack the scheme is by finding collisions for a hash function. In this paper, we propose an FS-style signature scheme, called Lossy CSI-FiSh, constructed using the CSIDH-512 parameters and with a security proof based on the “Lossy Keys” technique introduced by Kiltz, Lyubashevsky and Schaffner (Eurocrypt’18). Lossy CSI-FiSh is provably secure under the same assumption which underlies the security of the key exchange protocol CSIDH (Castryck et al. (Asiacrypt’18)) and is almost as efficient as CSI-FiSh. For instance, aiming for small signature size, our scheme is expected to take around $$approx 800$$  ms to sign/verify while producing signatures of size $$approx 280$$ bytes. This is only twice slower than CSI-FiSh while having similar signature size for the same parameter set. As an additional benefit, our scheme is by construction secure both in the classical and quantum random oracle model.
Video from PKC 2020
  title={Lossy CSI-FiSh: Efficient Signature Scheme with Tight Reduction to Decisional CSIDH-512},
  booktitle={Public-Key Cryptography – PKC 2020},
  series={Public-Key Cryptography – PKC 2020},
  author={Ali El Kaafarani and Shuichi Katsumata and Federico Pintore},