Mojtaba Fadavi
Department of Combinatorics & Optimization, University of Waterloo, Canada

Seyyed Arash Azimi
CPS2 Lab, Electrical Engineering Department, Shahid Rajaee Teacher Training University, Tehran, Iran

Sabyasachi Karati
Cryptology and Security Research Unit, Indian Statistical Institute, Kolkata, India

Samuel Jaques
Department of Combinatorics & Optimization, University of Waterloo, Canada

Keywords: post-quantum cryptography, group signatures, dynamic group signatures, SPHINCS+, hash-based signatures

Abstract

A group signature scheme enables users of a group to anonymously sign messages on behalf of the group, while a designated authority can revoke anonymity when needed to ensure user accountability. In this paper, we build a post-quantum fully dynamic group signature scheme from only symmetric encryption and hash functions.

Our protocol, DGSP, achieves the following: (i) the set-up time is effectively constant in the number of signatures that may be issued, with support for up to $2^{64}$ signatures; (ii) the tracing algorithm run by the authority has constant runtime in the number of users; (iii) the set of users is fully dynamic and users can be revoked or added as needed without system-wide updates; and (iv) forward anonymity, where if a user's secrets are compromised they cannot be used to de-anonymize previous signatures. DGSP is the first group signature based only on symmetric primitives to achieve all of these properties: the previous state-of-the-art in this area is SPHINX-in-the-Head (SITH), which does not achieve (ii) or (iv), and DGMT, which does not achieve (i) and may not achieve (iv). Like DGMT, but unlike SITH, DGSP is stateful and users must refresh a local storage of certificates to issue new signatures.

We provide a full Rust implementation, showing that our signatures are roughly 5 times larger than DGMT but nearly 100 times smaller than SITH, and all basic operations run in under 2 milliseconds. We prove security in the standard model based on typical assumptions for symmetric primitives. DGSP is a compelling solution for applications requiring large-scale user support, efficient operations, and conservative post-quantum security.