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

Ali El Kaafarani, 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.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2020
Keywords
public-key cryptography
Contact author(s)
shuichi katsumata000 @ gmail com
shuichi katsumata @ aist go jp
federico pintore @ maths ox ac uk
elkaafarani @ pqshield com
History
2020-06-11: last of 3 revisions
See all versions
Short URL
https://ia.cr/2020/124

CC BY

BibTeX

@misc{cryptoeprint:2020/124,
author = {Ali El Kaafarani and Shuichi Katsumata and Federico Pintore},
title = {Lossy CSI-FiSh: Efficient Signature Scheme with Tight Reduction to Decisional CSIDH-512},
howpublished = {Cryptology ePrint Archive, Paper 2020/124},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/124}},
url = {https://eprint.iacr.org/2020/124}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.