Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Transactions on Privacy and Security

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

Liqun Chen, Changyu Dong, Christopher J. P. Newton, Yalan Wang

Published Dec 27, 2023• 13 citations
Publisher

Abstract

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.

DOI
10.1145/3638763

Related papers

HPGS: An Efficient Hash-Based Post-Quantum Dynamic Group Signature for Industrial Internet of Things

Kaili Dou, Yanyan Han, Suheng Wei +3 more

Group signatures, due to their inherent advantages in anonymous authentication, have been widely adopted in privacy-preserving multi-device authentication and related scenarios, establishing themselves as a fundamental cryptographic building block for securing communications in Industrial Internet of Things (IIoT) systems. However, existing post-quantum group signature schemes suffer from excessively large signature sizes, lack of strong non-frameability, and insufficient privilege separation, making them difficult to meet the efficiency and security requirements of IIoT. To address these limitations, this paper proposes a hash-based post-quantum group signature scheme (HPGS) for IIoT, which employs the SPHINCS+variant CEDRUS and MPC-in-the-Head zero-knowledge proofs. Specifically, we optimize the zero-knowledge proof circuit and Merkle tree parameters, and introduce an epoch-based Merkle tree accumulator to constrain the signature size to the kilobyte scale while supporting dynamic enrollment and revocation. Next, we design a member self-key-generation mechanism, where each member independently generates the signing key and only registers a public commitment, guaranteeing strong non-frameability. Furthermore, we distribute credential issuance and signature opening to two independent entities, enforcing protocol-level privilege separation. Experimental results show that, under NIST Level 1 post-quantum security, the scheme achieves a signature size of 47.07 KB, an online signing time of 104 μs, and a verification time of 1.4 ms, outperforming existing schemes in signing speed, verification efficiency, and functional completeness.

IEEE Internet of Things Journal•Jan 1, 2026•0 citations

Alati kaks : Kahe osapoolega SDitH digiallkirjad

Veri, Hans Kristjan

The rise of quantum computing threatens to break many of the cryptographic systems that secure today’s digital world. In response, researchers are developing new tools designed to remain secure in a post-quantum future. Most of the promising candidates for post-quantum digital signatures rely on security assumptions based on lattices or properties of hash functions. Another promising approach transforms secure multi-party computation protocols into zero-knowledge proofs, which are then turned into digital signatures. This technique, known as multi-party computation in-the-head (MPCitH), offers strong security properties and flexibility for distributed applications. This thesis investigates whether MPCitH digital signatures can be efficiently adapted for use by two cooperating parties to jointly produce a signature. Here we show how to construct two-party signatures based on syndrome decoding in-the-head (SDitH) signatures. We propose a provably secure scheme that achieves the smallest known communication overhead among two-party MPCitH signatures, while resulting in a signature size approximately double that of a single-prover variant. This result provides a new data point in the design space of multi-party MPCitH signatures and post-quantum digital signatures in general.

•Jan 1, 2025•0 citations

A Provably Secure Group Signature Scheme from Code-Based Assumptions.

Martianus Frederic Ezerman, Hyung Tae Lee, San Ling +2 more

Abstract. We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise prob-lem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ( ≈ 224 users). The feasibility of the scheme is supported by implementa-tion results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

•Jan 1, 2015•0 citations

Post-quantum group signature scheme for multi-party satellite control via CP-WOTS+ optimization

Qiyan Sang, Lin Zhou, Xi Lin +1 more

Abstract Quantum computing creates new security risks for legacy satellite communication systems, especially for Telemetry, Tracking, and Control (TT&C) links. Hash-Based Signature (HBS) schemes are seen as the safest option for Post-Quantum Cryptography (PQC) migrations, as they only depend on the collision resistance of hash functions without involving complex security assumptions. But in practice, applying current HBS standards in engineering is tough due to the trade-off between signature size and computational overhead. We solve this problem by proposing CP-WOTS+, an optimization scheme based on checkpoint pre-computation. By introducing a checkpoint mechanism to the signer, we achieved a compact signature of 1088 bytes under the w = 256 parameter set, while reducing the generation time from 7.15 to 0.45 ms (a $$15.9 \times$$ 15.9 × speedup). Building on this primitive, we designed the CP-XMSS-GS group signature scheme for multi-party satellite control. This scheme implements a centralized authorization model that offloads complexity to the ground: the satellite remains strictly stateless (storing only a 64-byte group public key) and just handles verification. Complex member management and traceability are handled by the ground administrator. Experimental results demonstrate that our scheme maintains a small signature size of 1764 bytes and ensures anonymity and traceability, and it requires zero on-orbit updates when members change. Our work provides a highly secure, lightweight post-quantum solution for resource-constrained satellite-ground links.

Cybersecurity•Jul 31, 2026•0 citations

Formal security analysis of MPC-in-the-head zero-knowledge protocols

Nikolaj Sidorenco, Sabine Oechsner, Bas Spitters

Zero-knowledge proofs allow a prover to convince a verifier of the veracity of a statement without revealing any other information. An interesting class of zero-knowledge protocols are those following the MPC-in-the-head paradigm (Ishai et al., STOC '07) which use secure multiparty computation (MPC) protocols as the basis. Efficient instances of this paradigm have emerged as an active research topic in the last years, starting with ZKBoo (Giacomelli et al., USENIX '16). Zero-knowledge protocols are a vital building block in the design of privacy-preserving technologies as well as cryptographic primitives like digital signature schemes that provide post-quantum security. This work investigates the security of zero-knowledge protocols following the MPC-in-the-head paradigm. We provide the first machine-checked security proof of such a protocol on the example of ZKBoo. Our proofs are checked in the EasyCrypt proof assistant. To enable a modular security proof, we develop a new security notion for the MPC protocols used in MPC-in-the-head zero-knowledge protocols. This allows us to recast existing security proofs in a black-box fashion which we believe to be of independent interest.

IEEE Computer Security Foundations Workshop (CSFW)•Jun 1, 2021•16 citations

Fully Anonymous Attribute Tokens from Lattices.

Jan L. Camenisch, Gregory Neven, Markus Rückert

Anonymous authentication schemes such as group signatures and anonymous credentials are important privacy-protecting tools in electronic communications. The only currently known scheme based on assumptions that resist quantum attacks is the group signature scheme by Gordon et al. (ASIACRYPT 2010). We present a generalization of group signatures called anonymous attribute tokens where users are issued attribute-containing credentials that they can use to anonymously sign messages and generate tokens revealing only a subset of their attributes. We present two lattice-based constructions of this new primitive, one with and one without opening capabilities for the group manager. The latter construction directly yields as a special case the first lattice-based group signature scheme offering full anonymity (in the random-oracle model), as opposed to the practically less relevant notion of chosen-plaintext anonymity offered by the scheme of Gordon et al. We also extend our scheme to protect users from framing attacks by the group manager, where the latter creates tokens or signatures in the name of honest users. Our constructions involve new lattice-based tools for aggregating signatures and verifiable CCA2-secure encryption.

•Jan 1, 2012•0 citations
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.
Group signatures, due to their inherent advantages in anonymous authentication, have been widely adopted in privacy-preserving multi-device authentication and related scenarios, establishing themselves as a fundamental cryptographic building block for securing communications in Industrial Internet of Things (IIoT) systems. However, existing post-quantum group signature schemes suffer from excessively large signature sizes, lack of strong non-frameability, and insufficient privilege separation, making them difficult to meet the efficiency and security requirements of IIoT. To address these limitations, this paper proposes a hash-based post-quantum group signature scheme (HPGS) for IIoT, which employs the SPHINCS+variant CEDRUS and MPC-in-the-Head zero-knowledge proofs. Specifically, we optimize the zero-knowledge proof circuit and Merkle tree parameters, and introduce an epoch-based Merkle tree accumulator to constrain the signature size to the kilobyte scale while supporting dynamic enrollment and revocation. Next, we design a member self-key-generation mechanism, where each member independently generates the signing key and only registers a public commitment, guaranteeing strong non-frameability. Furthermore, we distribute credential issuance and signature opening to two independent entities, enforcing protocol-level privilege separation. Experimental results show that, under NIST Level 1 post-quantum security, the scheme achieves a signature size of 47.07 KB, an online signing time of 104 μs, and a verification time of 1.4 ms, outperforming existing schemes in signing speed, verification efficiency, and functional completeness.
The rise of quantum computing threatens to break many of the cryptographic systems that secure today’s digital world. In response, researchers are developing new tools designed to remain secure in a post-quantum future. Most of the promising candidates for post-quantum digital signatures rely on security assumptions based on lattices or properties of hash functions. Another promising approach transforms secure multi-party computation protocols into zero-knowledge proofs, which are then turned into digital signatures. This technique, known as multi-party computation in-the-head (MPCitH), offers strong security properties and flexibility for distributed applications. This thesis investigates whether MPCitH digital signatures can be efficiently adapted for use by two cooperating parties to jointly produce a signature. Here we show how to construct two-party signatures based on syndrome decoding in-the-head (SDitH) signatures. We propose a provably secure scheme that achieves the smallest known communication overhead among two-party MPCitH signatures, while resulting in a signature size approximately double that of a single-prover variant. This result provides a new data point in the design space of multi-party MPCitH signatures and post-quantum digital signatures in general.
Abstract. We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise prob-lem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ( ≈ 224 users). The feasibility of the scheme is supported by implementa-tion results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.
Abstract Quantum computing creates new security risks for legacy satellite communication systems, especially for Telemetry, Tracking, and Control (TT&C) links. Hash-Based Signature (HBS) schemes are seen as the safest option for Post-Quantum Cryptography (PQC) migrations, as they only depend on the collision resistance of hash functions without involving complex security assumptions. But in practice, applying current HBS standards in engineering is tough due to the trade-off between signature size and computational overhead. We solve this problem by proposing CP-WOTS+, an optimization scheme based on checkpoint pre-computation. By introducing a checkpoint mechanism to the signer, we achieved a compact signature of 1088 bytes under the w = 256 parameter set, while reducing the generation time from 7.15 to 0.45 ms (a 15.9×15.9 \times15.9× 15.9 × speedup). Building on this primitive, we designed the CP-XMSS-GS group signature scheme for multi-party satellite control. This scheme implements a centralized authorization model that offloads complexity to the ground: the satellite remains strictly stateless (storing only a 64-byte group public key) and just handles verification. Complex member management and traceability are handled by the ground administrator. Experimental results demonstrate that our scheme maintains a small signature size of 1764 bytes and ensures anonymity and traceability, and it requires zero on-orbit updates when members change. Our work provides a highly secure, lightweight post-quantum solution for resource-constrained satellite-ground links.
Zero-knowledge proofs allow a prover to convince a verifier of the veracity of a statement without revealing any other information. An interesting class of zero-knowledge protocols are those following the MPC-in-the-head paradigm (Ishai et al., STOC '07) which use secure multiparty computation (MPC) protocols as the basis. Efficient instances of this paradigm have emerged as an active research topic in the last years, starting with ZKBoo (Giacomelli et al., USENIX '16). Zero-knowledge protocols are a vital building block in the design of privacy-preserving technologies as well as cryptographic primitives like digital signature schemes that provide post-quantum security. This work investigates the security of zero-knowledge protocols following the MPC-in-the-head paradigm. We provide the first machine-checked security proof of such a protocol on the example of ZKBoo. Our proofs are checked in the EasyCrypt proof assistant. To enable a modular security proof, we develop a new security notion for the MPC protocols used in MPC-in-the-head zero-knowledge protocols. This allows us to recast existing security proofs in a black-box fashion which we believe to be of independent interest.
Anonymous authentication schemes such as group signatures and anonymous credentials are important privacy-protecting tools in electronic communications. The only currently known scheme based on assumptions that resist quantum attacks is the group signature scheme by Gordon et al. (ASIACRYPT 2010). We present a generalization of group signatures called anonymous attribute tokens where users are issued attribute-containing credentials that they can use to anonymously sign messages and generate tokens revealing only a subset of their attributes. We present two lattice-based constructions of this new primitive, one with and one without opening capabilities for the group manager. The latter construction directly yields as a special case the first lattice-based group signature scheme offering full anonymity (in the random-oracle model), as opposed to the practically less relevant notion of chosen-plaintext anonymity offered by the scheme of Gordon et al. We also extend our scheme to protect users from framing attacks by the group manager, where the latter creates tokens or signatures in the name of honest users. Our constructions involve new lattice-based tools for aggregating signatures and verifiable CCA2-secure encryption.