Paper 2019/498

CSI-FiSh: Efficient Isogeny based Signatures through Class Group Computations

Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren

Abstract

In this paper we report on a new record class group computation of an imaginary quadratic field having 154-digit discriminant, surpassing the previous record of 130 digits. This class group is central to the CSIDH-512 isogeny based cryptosystem, and knowing the class group structure and relation lattice implies efficient uniform sampling and a canonical representation of its elements. Both operations were impossible before and allow us to instantiate an isogeny based signature scheme first sketched by Stolbunov, which we further optimize using multiple public keys and Merkle trees. We also show that including quadratic twists allows to cut the public key size in half for free. Optimizing for signature size, our implementation takes 390ms to sign/verify and results in signatures of $263$ bytes, at the expense of a large public key. This is 300 times faster and over 3 times smaller than an optimized version of SeaSign for the same parameter set. Optimizing for public key and signature size combined, results in a total size of 1468 bytes, which is smaller than any other post-quantum signature scheme at the 128-bit security level.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Isogeny-based cryptographydigital signatureclass groupgroup actionFiat-Shamir
Contact author(s)
ward beullens @ esat kuleuven be
thorsten kleinjung @ epfl ch
frederik vercauteren @ esat kuleuven be
History
2019-05-20: received
Short URL
https://ia.cr/2019/498
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/498,
      author = {Ward Beullens and Thorsten Kleinjung and Frederik Vercauteren},
      title = {CSI-FiSh: Efficient Isogeny based Signatures through Class Group Computations},
      howpublished = {Cryptology ePrint Archive, Paper 2019/498},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/498}},
      url = {https://eprint.iacr.org/2019/498}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.