### Group Signatures and More from Isogenies and Lattices: Generic, Simple, and Efficient

Ward Beullens, Samuel Dobson, Shuichi Katsumata, Yi-Fu Lai, and Federico Pintore

##### Abstract

We construct an efficient dynamic group signature (or more generally an accountable ring signature) from isogeny and lattice assumptions. Our group signature is based on a simple generic construction that can be instantiated by cryptographically hard group actions such as the CSIDH group action or an MLWE-based group action. The signature is of size $O(\log N)$, where $N$ is the number of users in the group. Our idea builds on the recent efficient OR-proof by Beullens, Katsumata, and Pintore (Asiacrypt'20), where we efficiently add a proof of valid ciphertext to their OR-proof and further show that the resulting non-interactive zero-knowledge proof system is online extractable. Our group signatures satisfy more ideal security properties compared to previously known constructions, while simultaneously having an attractive signature size. The signature size of our isogeny-based construction is an order of magnitude smaller than all previously known post-quantum group signatures (e.g., 6.6 KB for 64 members). In comparison, our lattice-based construction has a larger signature size (e.g., either 126 KB or 89 KB for 64 members depending on the satisfied security property). However, since the $O(\cdot)$-notation hides a very small constant factor, it remains small even for very large group sizes, say $2^{20}$.

Note: Updated (Oct.28, 2021): Updated the references.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Isogeny-based cryptographyLattice-based cryptographyPost-Quantum cryptographyAccountable Ring SignatureGroup Signature
Contact author(s)
ward beullens @ esat kuleuven be
samuel dobson nz @ gmail com
shuichi katsumata @ aist go jp
ylai276 @ aucklanduni ac nz
federico pintore @ uniba it
History
2021-10-28: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/1366

CC BY

BibTeX

@misc{cryptoeprint:2021/1366,
author = {Ward Beullens and Samuel Dobson and Shuichi Katsumata and Yi-Fu Lai and Federico Pintore},
title = {Group Signatures and More from Isogenies and Lattices: Generic, Simple, and Efficient},
howpublished = {Cryptology ePrint Archive, Paper 2021/1366},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1366}},
url = {https://eprint.iacr.org/2021/1366}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.