International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Ward Beullens
Shuichi Katsumata
Federico Pintore
DOI: 10.1007/978-3-030-64834-3_16
Search ePrint
Search Google
Abstract: We construct efficient ring signatures (RS) from isogeny and lattice assumptions. Our ring signatures are based on a logarithmic OR proof for group actions. We instantiate this group action by either the CSIDH group action or an MLWE-based group action to obtain our isogeny-based or lattice-based RS scheme, respectively. Even though the OR proof has a binary challenge space and therefore requires a number of repetitions which is linear in the security parameter, the sizes of our ring signatures are small and scale better with the ring size N than previously known post-quantum ring signatures. We also construct linkable ring signatures (LRS) that are almost as efficient as the non-linkable variants. The isogeny-based scheme produces signatures whose size is an order of magnitude smaller than all previously known logarithmic post-quantum ring signatures, but it is relatively slow (e.g. 5.5 KB signatures and 79 s signing time for rings with 8 members). In comparison, the 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 approximately 1024.
Video from ASIACRYPT 2020
  title={Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  author={Ward Beullens and Shuichi Katsumata and Federico Pintore},