Redactable Signature Schemes and Zero-knowledge Proofs: A comparative examination for applications in Decentralized Digital Identity Systems.

Bryan Kumara, Mark Hooper, Carsten Maple, Timothy Hobson, Jon Crowcroft

Introduction

In the evolving landscape of Decentralized Identifiers (DIDs) and Verifiable Credentials (VCs), the primary challenge lies in balancing user privacy with system performance. Users require the ability to prove specific attributes (e.g., age or residency) without disclosing extraneous personal information. This paper evaluates two primary cryptographic candidates for selective disclosure: Redactable Signature Schemes (RSS) and Zero-Knowledge Proofs (ZKP).

Cryptographic Approaches

Redactable Signature Schemes (RSS)

The authors implemented an RSS based on the Pointcheval-Sanders (PS) digital signature protocol. Utilizing bilinear pairings, this scheme allows a holder to redact specific segments of a signed message while maintaining the validity of the signature. Crucially, the scheme is re-randomizable, ensuring that redacted signatures cannot be trivially linked back to the original full credential, thereby preserving user unlinkability.

Zero-Knowledge Proofs (ZKP)

The study examined zk-Creds, a protocol leveraging Groth16 ZK-SNARKs. In this model, identity attributes are treated as constrained variables within an arithmetic circuit. While ZKPs offer high expressiveness—allowing for complex logical predicates (e.g., "age > 18") without revealing the underlying data—they require a Common Reference String (CRS). The generation of this CRS typically necessitates a "trusted setup" ceremony, which represents a significant logistical and security hurdle for decentralized systems.

Experimental Setup

Performance was benchmarked using a Rust-based implementation. The test dataset consisted of a standard W3C-compliant Verifiable Credential containing name, date of birth, and address. To simulate a high-privacy, high-computation scenario, benchmarks for RSS involved redacting all fields except for the "country" attribute.

Comparative Performance

The evaluation focused on three primary metrics: runtime for proof generation (derivation), verification speed, and data size.

Performance benchmarks for the Redactable Signature Scheme (RSS) components.

As shown in the RSS performance data (Table 1), deriving a redacted signature takes approximately 824.84 ms, with verification requiring 310.77 ms. The resulting derived signature size is 1344 bytes.

Client-side performance metrics for Zero-Knowledge Proof (ZKP) operations.

In contrast, ZKP proving times (Table 2) range from 784 ms for simple possession to 916 ms for clone-resistant proofs. While proving times are roughly comparable to RSS, ZKP verification is significantly more efficient, ranging from 1.5 ms to 6 ms—representing a 50x to 200x speed advantage over RSS. Furthermore, ZKP proof sizes (744 - 1064 bytes) are generally more compact than RSS derived signatures.

Discussion and Strategic Implications

The choice between RSS and ZKP involves a trade-off between immediate practicality and long-term scalability.

  1. The Trusted Setup Barrier: RSS is advantageous for early-stage deployments because it avoids the complexity and security risks associated with a ZKP trusted setup. If the "toxic waste" from a setup is not destroyed, the entire system's integrity is compromised.
  2. Verification Efficiency: For high-traffic verifiers (e.g., automated gates or high-volume web services), the extreme speed of ZKP verification makes it the superior choice for mature ecosystems.
  3. Privacy and Expressiveness: While RSS reveals the structure (number of fields) of the original document, ZKPs provide total structural obfuscation and support complex logical proofs that RSS cannot handle.

Conclusion

The authors propose a "staged" deployment strategy. Redactable Signature Schemes serve as an ideal "Day 1" solution due to their simplicity and lack of trusted setup requirements. However, as decentralized identity systems mature and require higher verification throughput and more complex privacy logic, transitioning to Zero-Knowledge Proofs becomes the optimal path. Future research should address the quantum vulnerability of both schemes, exploring lattice-based or hash-based alternatives for long-term security.

Summary updated

Abstract

Redactable Signature Schemes and Zero-Knowledge Proofs are two radically different approaches to enable privacy. This paper analyses their merits and drawbacks when applied to decentralized identity system. Redactable Signatures, though competitively quick and compact, are not as expressive as zero-knowledge proofs and do not provide the same level of privacy. On the other hand, zero-knowledge proofs can be much faster but some protocols require a trusted set-up. We conclude that given the benefits and drawbacks, redactable signatures are more appropriate at an earlier stage and zero-knowledge proofs are more appropriate at a later stage for decentralized identity systems
BibTeX
@misc{kumara2023redactable,
  author = {Bryan Kumara and Mark Hooper and Carsten Maple and Timothy Hobson and Jon Crowcroft},
  title = {{Redactable Signature Schemes and Zero-knowledge Proofs: A comparative examination for applications in Decentralized Digital Identity Systems.}},
  year = {2023},
  eprint = {2310.15934},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.15934},
}
Figure