Cryptology ePrint Archive: Report 2020/646

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

Ward Beullens and Shuichi Katsumata and Federico Pintore

Abstract: 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$.

Category / Keywords: public-key cryptography / Isogeny-based cryptography, Lattice-based cryptography, Linkable Ring Signature, Post-Quantum cryptography

Date: received 29 May 2020

Contact author: ward beullens at esat kuleuven be, shuichi katsumata000@gmail com, shuichi katsumata@aist go jp, federico pintore@maths ox ac uk, federico pintore@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200603:095019 (All versions of this report)

Short URL: ia.cr/2020/646


[ Cryptology ePrint archive ]