Paper 2020/646

Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices

Ward Beullens, Shuichi Katsumata, and Federico Pintore


We construct efficient ring signatures from isogeny and lattice assumptions. Our ring signatures are based on a logarithmic OR proof for group actions. We then instantiate this group action by either the CSIDH group action or an MLWE-based group action to obtain our isogeny-based or lattice-based ring signature scheme respectively. Even though this OR proof has a binary challenge space and therefore needs to be repeated a linear number of times, the size of our ring signatures is small and scales better with the ring size N than previously known post-quantum ring signatures. We also construct linkable ring signatures that are almost as efficient as the non-linkable variant. The signature size of our isogeny-based construction is an order of magnitude smaller than all previously known logarithmic post-quantum ring signatures, but is relatively slow (e.g. 5.5 KB signatures and 79 s signing time for rings with 8 members). In comparison, our lattice-based construction is much faster, but has larger signatures (e.g. 30 KB signatures and 90 ms signing time for the same ring size). For small ring sizes our lattice-based ring signatures are slightly larger than state-of-the-art schemes, but they are smaller for ring sizes larger than $N \approx 1024$.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Isogeny-based cryptographyLattice-based cryptographyLinkable Ring SignaturePost-Quantum cryptography
Contact author(s)
ward beullens @ esat kuleuven be
shuichi katsumata000 @ gmail com
shuichi katsumata @ aist go jp
federico pintore @ maths ox ac uk
federico pintore @ gmail com
2020-06-03: received
Short URL
Creative Commons Attribution


      author = {Ward Beullens and Shuichi Katsumata and Federico Pintore},
      title = {Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2020/646},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.