Cryptology ePrint Archive: Report 2020/124

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

Ali El Kaafarani and Shuichi Katsumata and Federico Pintore

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.

Category / Keywords: public-key cryptography / public-key cryptography

Original Publication (with minor differences): IACR-PKC-2020

Date: received 5 Feb 2020, last revised 11 Jun 2020

Contact author: shuichi katsumata000 at gmail com,shuichi katsumata@aist go jp,federico pintore@maths ox ac uk,elkaafarani@pqshield com

Available format(s): PDF | BibTeX Citation

Note: Added acknowledgments.

Version: 20200611:083647 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]