Source-linked AI summary
Thresholding Post-Quantum Signatures
Francesco De Sclavis, Matteo Nardelli, Marco Pedicini
TL;DR
Post-quantum threshold signatures are less mature and often less practical than classical threshold schemes, while standardization focuses on simple signatures and does not directly cover threshold conversion. The paper systematizes techniques across post-quantum paradigms and generic approaches, identifying trade-offs including one-round FHE transformations, practical secret sharing at medium thresholds, and efficiency or parameter limitations.
Problem
Post-quantum threshold signatures are scarce and often impractical, while NIST standardization targets simple signatures and proposed schemes are not immediately convertible to threshold versions using MPC.
Method
The paper classifies techniques for building T-out-of-N post-quantum threshold signatures across paradigms and examines generic FHE, MPC, and ZKP approaches.
Results
The surveyed approaches include one-round FHE threshold transformation, practical Hermine secret sharing for T ≤ N ≤ 64, and group-action and MPC techniques with distinct efficiency and security properties.
Takeaways & Limitations
Linear secret sharing is a recurring design pattern, but post-quantum schemes require paradigm-specific adaptations for shortness, rejection sampling, trapdoors, or verification.
Takeaways & Limitations
Some generic approaches are inefficient unless the underlying signature is amenable to FHE or MPC, while some secret-sharing methods remain practical only for medium thresholds or small parameters.
Abstract
from arXiv · showhide
Threshold signature schemes distribute the signing process among $T$ parties out of $N$. They enable a variety of applications and their research is also motivated by a recent NIST call. However, applications are dominated by pre-quantum signatures, which are more efficient but not secure in the post-quantum setting. This paper investigates existing post-quantum signatures, based on a variety of paradigms: lattice problems, one-way (hash) functions, cryptographic group actions, isogenies and multivariate systems. We propose a classification (divided by paradigm) of existing tools that are used to build $T$-out-of-$N$ schemes from digital signatures. We also include general approaches based on FHE, MPC or ZKP.
1 Introduction
Threshold signatures distribute signing across T of N participants, but post-quantum threshold solutions remain scarce and often impractical. The paper systematizes techniques for constructing such schemes across paradigms and includes generic approaches.
- Threshold signatures: Threshold signatures let T of N signers jointly produce valid signatures while preventing T −1 dishonest participants from forging them.They split secret keys into partial secrets and aggregate partial signatures, distributing trust and avoiding single points of failure.
- Post-quantum gap: Efficient RSA, DSA, ECDSA, BLS, and Schnorr threshold schemes exist, but post-quantum solutions are few and often costly in keys, signatures, or signing time.The cited post-quantum setting is motivated by quantum threats and NIST’s standardization competition.
- Post-quantum gap: NIST’s standardization process addresses simple signatures rather than threshold signatures, and competition schemes are not immediately convertible using MPC.This leaves threshold functionality outside the process’s stated scope.
- Techniques: PQ threshold techniques commonly adapt linear secret sharing and Schnorr-like FROST methods, while addressing lattice non-linearities and verification of aggregated signatures.Zero-knowledge proofs can be used to prove that aggregated signatures verify correctly.
- Paper scope: The paper examines implementation techniques across PQ paradigms, focusing on modular tools rather than individual threshold signatures and covering generic FHE, MPC, and ZKP approaches.Its scope is T-out-of-N schemes, excluding multi-signatures and ring signatures.
2 Lattice-based Signatures
Lattice-based threshold signatures must address the difficulty of thresholdizing trapdoor or rejection-sampling operations while preventing leakage from responses. Existing approaches use noise flooding, homomorphic commitments, and alternative sharing schemes, each with distinct efficiency, security, or functionality trade-offs.
- Lattice-based signatures use hash-and-sign or Fiat-Shamir with Aborts, based on SIS, LWE, or related assumptions.Threshold constructions must adapt or bypass operations that are non-trivial to perform jointly.
- 2.1 Noise Flooding: Noise flooding replaces trapdoor or rejection sampling by adding sufficiently dispersed noise to hide the secret.The resulting protocols are not zero-knowledge, so leakage must be mitigated statistically or computationally; minimizing leakage increases signature size.
- 2.2 Na¨ıve Approach with Secret Sharing: Shamir-based linear aggregation enables threshold responses with the base signature’s formal expression, preserving unchanged verification when functional interchangeability holds.Participants combine partial responses with Lagrange coefficients, but large coefficients can make partial responses long and leak secret shares.
- 2.2 Na¨ıve Approach with Secret Sharing: One-time additive masks hide Shamir shares, addressing attacks that recover a share from enough partial signatures across different signing sets.Commitments and zero-knowledge proofs may be needed to obtain identifiable aborts, although masks can make misbehavior harder to detect.
- 2.3 Homomorphic Commitments: Homomorphic commitments allow Fiat-Shamir threshold schemes to retain rejection sampling, but they alter verification and can make threshold conversion costly.A multi-signature construction exists, while transforming it into a threshold signature is non-trivial because abort-related repetitions can grow excessively.
- 2.4 Alternative Secret Sharing Schemes: Alternative sharing schemes can produce short shares and simpler reconstruction, enabling Hermine’s partially non-interactive design for medium thresholds, while other schemes scale only to small parameters.Hermine supports T ≤ N ≤ 64; another approach uses ramp secret sharing for bigger parameters than schemes whose costs grow quickly.
3 Signatures from Other Paradigms
The paper surveys threshold constructions for hash-based signatures and group-action signatures, emphasizing their protocol structure, security assumptions, and practical constraints. Stateful hash-based approaches require centralized setup and careful one-time-key management, while group-action approaches face sequential evaluation and efficiency challenges.
- Hash-based signatures: Stateful hash-based signatures build threshold schemes from Merkle signatures using an underlying secure one-time signature, preserving functional interchangeability.The framework splits signature elements and secret values into shares for joint reconstruction.
- Hash-based signatures: A trusted dealer splits each one-time signature, signing key, and integrity data into shares before deleting the originals.The aggregator reconstructs commitment values, while signers verify integrity and return shares of the response and authentication path.
- Hash-based signatures: The construction extends to T-out-of-N by assigning one-time-key identifiers to disjoint signer coalitions, preventing identifier reuse across coalitions.The setup distributes coalition assignments to participants, and security depends on never using a key twice.
- Hash-based signatures: The stateful hash-based framework has centralized setup, is infeasible for stateless schemes because of CRV storage, and incurs growth in the number of coalitions.These constraints limit how broadly the framework can be deployed.
- Group actions: Group-action signatures rely on the Group Action Inverse Problem and adapt Schnorr-style identification with Fiat-Shamir to threshold settings.GRASS assumes hard GAIP and 2-weak pseudorandomness, while GRASS+ replaces replicated sharing with multiplicative non-abelian sharing and achieves adaptive security under a GAIP variant.
- Group actions: Distributed cyclic group actions are evaluated sequentially: each party applies its secret action to the previous intermediate result, preserving secret shares under GAIP.Linear secret sharing permits the parties to compute the action of the combined secret, but the computation requires many rounds.
- Group actions: Existing isogeny-based implementations are computationally intensive and inherently sequential, although they offer small keys and signatures.The sequential evaluation leads to a high number of protocol rounds.
- Group actions: Non-abelian group-action evaluation lacks an obvious Shamir-sharing route, so replicated sharing is practical mainly for small N despite broader generality.The approach also generalizes code-based schemes requiring non-abelian actions.
4 Generic Approaches
Generic approaches construct threshold signatures by evaluating or transforming an underlying signing algorithm with FHE, linearly homomorphic encryption, MPC, or ZKPs. These methods trade generality, efficiency, security scope, or computation and communication overhead, while STARKs provide a post-quantum transparent ZKP option.
- Threshold Fully Homomorphic Encryption: Threshold FHE can homomorphically evaluate a signing circuit and jointly decrypt the result, yielding a one-round threshold signature framework.The universal thresholdizer is intended as a black-box transformation from signatures and can provide active security in later improvements.
- Threshold Fully Homomorphic Encryption: FHE-based thresholdization is broadly applicable but likely incurs computation and communication overhead and may require modifying the underlying signature.Its main protocol advantage is minimizing interaction to one round while preserving functional interchangeability.
- Linearly Homomorphic Encryption: A linearly homomorphic framework is less general than universal thresholdization but can be more efficient for signatures whose operations are linear.It was instantiated for a Dilithium variant whose response uses additions and multiplication by a public scalar, with rejection sampling replaced by noise flooding.
- Multi-Party Computation: Generic MPC can jointly evaluate signing algorithms, but practical performance is difficult for nonlinear operations requiring conversions between secret-sharing representations.Specific lattice-based constructions use MPC for rejection sampling, while other work evaluates GPV signatures and considers active security and UC composability.
- Multivariate Signatures: Existing multivariate candidates have a significant security caveat: LUOV and Rainbow have been broken for some parameter sets.The cited attacks reflect the broader history of cryptanalytic attacks on these schemes.
- Zero-Knowledge Proofs: STARKs are scalable, transparent, post-quantum ZKPs that can be made non-interactive with Fiat–Shamir when the underlying proof of knowledge remains quantum-secure.The passage introduces STARKs as a route toward constructing threshold signatures, while multivariate approaches include OV-based schemes amenable to linear-system evaluation.
5 Conclusion
The paper classifies techniques for constructing threshold post-quantum signatures, showing that existing tools require adaptation to the obstacles of different paradigms. General black-box approaches offer broad transformations but often incur inefficiency or structural limitations.
- 5 Conclusion: Threshold PQ signature techniques reuse classical ideas, especially linear secret sharing and aggregation of partial responses.The paper identifies Schnorr-like threshold signatures such as FROST as a common template.
- 5 Conclusion: Lattice-based signatures require additional mechanisms to preserve vector shortness during thresholdization.The paper cites noise flooding, homomorphic commitments, and ad-hoc techniques as typical solutions.
- 5 Conclusion: Group-action signatures can reuse discrete-log-based techniques, but sequential threshold evaluation leads to protocols with many rounds.
- 5 Conclusion: Hash-based signatures resist additive aggregation, making efficient threshold constructions difficult.
- 5 Conclusion: Black-box transformations through FHE, MPC, or ZKPs are generally inefficient and require underlying schemes adapted to those techniques.FHE and MPC are practical mainly when the underlying scheme is friendly to them, while ZKPs require an algebraic verification representation.