Paper 2024/379

SyRA: Sybil-Resilient Anonymous Signatures with Applications to Decentralized Identity

Elizabeth Crites, Web3 Foundation
Aggelos Kiayias, The University of Edinburgh & IOG
Markulf Kohlweiss, The University of Edinburgh & IOG
Amirreza Sarencheh, The University of Edinburgh & IOG
Abstract

We introduce a new cryptographic primitive, called Sybil-Resilient Anonymous (SyRA) signatures, which enable users to generate, on demand, unlinkable pseudonyms tied to any given context, and issue signatures on behalf of these pseudonyms. Concretely, given a personhood relation, an issuer (who may be a distributed entity) enables users to prove their personhood and extract an associated long-term key, which can then be used to issue signatures for any given context and message. Sybil-resilient anonymous signatures achieve two key security properties: 1) Sybil resilience, which ensures that every user is entitled to at most one pseudonym per context, and 2) anonymity, which requires that no information about the user is leaked through their various pseudonyms or the signatures they issue on their pseudonyms’ behalf. We conceptualize SyRA signatures as an ideal functionality in the Universal Composition (UC) setting and realize the functionality via an efficient, pairing-based construction that utilizes two levels of verifiable random functions (VRFs), which may be of independent interest. One of the key features of this approach is the statelessness of the issuer: we achieve the core properties of Sybil resilience and anonymity without requiring the issuer to retain any information about past user interactions. SyRA signatures have various applications in multiparty systems, such as e-voting (e.g., for decentralized governance), privacy-preserving regulatory compliance (e.g., AML/CFT checks), and cryptocurrency airdrops, making them an attractive option for deployment in decentralized identity (DID) systems. Furthermore, we demonstrate the practicality of SyRA signatures for use in such systems by providing a performance evaluation of our construction.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Anonymous SignaturesSybil ResilienceDecentralized IdentityPrivacy-PreservingUniversal Composition
Contact author(s)
elizabeth @ web3 foundation
Aggelos Kiayias @ ed ac uk
Markulf Kohlweiss @ ed ac uk
Amirreza Sarencheh @ ed ac uk
History
2024-06-04: revised
2024-02-29: received
See all versions
Short URL
https://ia.cr/2024/379
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/379,
      author = {Elizabeth Crites and Aggelos Kiayias and Markulf Kohlweiss and Amirreza Sarencheh},
      title = {{SyRA}: Sybil-Resilient Anonymous Signatures with Applications to Decentralized Identity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/379},
      year = {2024},
      url = {https://eprint.iacr.org/2024/379}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.