International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Group Signature and More from Isogenies and Lattices: Generic, Simple, and Efficient

Shuichi Katsumata , AIST
Ward Beullens , KU Leuven
Samuel Dobson , University of Auckland
Yi-Fu Lai , University of Auckland
Federico Pintore , University of Bari
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
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 ¥emph{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}$.
Video from EUROCRYPT 2022
  title={Group Signature and More from Isogenies and Lattices: Generic, Simple, and Efficient},
  author={Shuichi Katsumata and Ward Beullens and Samuel Dobson and Yi-Fu Lai and Federico Pintore},