Paper 2024/649

Sphinx-in-the-Head: Group Signatures from Symmetric Primitives

Liqun Chen, University of Surrey
Changyu Dong, Guangzhou University
Christopher J. P. Newton, University of Surrey
Yalan Wang, University of Surrey

Group signatures and their variants have been widely used in privacy-sensitive scenarios such as anonymous authentication and attestation. In this paper, we present a new post-quantum group signature scheme from symmetric primitives. Using only symmetric primitives makes the scheme less prone to unknown attacks than basing the design on newly proposed hard problems whose security is less well-understood. However, symmetric primitives do not have rich algebraic properties, and this makes it extremely challenging to design a group signature scheme on top of them. It is even more challenging if we want a group signature scheme suitable for real-world applications, one that can support large groups and require few trust assumptions. Our scheme is based on MPC-in-the-head non-interactive zero-knowledge proofs, and we specifically design a novel hash-based group credential scheme, which is rooted in the SPHINCS+ signature scheme but with various modifications to make it MPC (multi-party computation) friendly. The security of the scheme has been proved under the fully dynamic group signature model. We provide an implementation of the scheme and demonstrate the feasibility of handling a group size as large as $2^{60}$. This is the first group signature scheme from symmetric primitives that supports such a large group size and meets all the security requirements.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM Transactions on Privacy and Security (TOPS)
Group signaturesHash-based cryptographyPost-quantum cryptography
Contact author(s)
liqun chen @ surrey ac uk
changyu dong @ gzhu edu cn
c newton @ surrey ac uk
yalan wang @ surrey ac uk
2024-04-29: approved
2024-04-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Liqun Chen and Changyu Dong and Christopher J. P. Newton and Yalan Wang},
      title = {Sphinx-in-the-Head: Group Signatures from Symmetric Primitives},
      howpublished = {Cryptology ePrint Archive, Paper 2024/649},
      year = {2024},
      doi = {10.1145/3638763},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.