Paper 2020/124
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
Note: Added acknowledgments.
Metadata
- Available format(s)
-
PDF
- 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
- 2020-02-06: received
- See all versions
- Short URL
- https://ia.cr/2020/124
- License
-
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}, url = {https://eprint.iacr.org/2020/124} }