Paper 2020/646
Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices
Ward Beullens, 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
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- 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 - History
- 2020-06-03: received
- Short URL
- https://ia.cr/2020/646
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/646, 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}, url = {https://eprint.iacr.org/2020/646} }