Paper 2023/602

Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance

Jack Doerner, Technion – Israel Institute of Technology
Yashvanth Kondi, Aarhus University
Eysa Lee, Northeastern University
abhi shelat, Northeastern University
LaKyah Tyner, Northeastern University

We propose a secure multiparty signing protocol for the BBS+ signature scheme; in other words, an anonymous credential scheme with threshold issuance. We prove that due to the structure of the BBS+ signature, simply verifying the signature produced by an otherwise semi-honest protocol is sufficient to achieve composable security against a malicious adversary. Consequently, our protocol is extremely simple and efficient: it involves a single request from the client (who requires a signature) to the signing parties, two exchanges of messages among the signing parties, and finally a response to the client; in some deployment scenarios the concrete cost bottleneck may be the client's local verification of the signature that it receives. Furthermore, our protocol can be extended to support the strongest form of blind signing and to serve as a distributed evaluation protocol for the Dodis-Yampolskiy Oblivious VRF. We validate our efficiency claims by implementing and benchmarking our protocol.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. IEEE S&P 2023
Threshold CryptographyAnonymous CredentialsBBS+Multi-Party ComputationConcrete Efficiency
Contact author(s)
j @ ckdoerner net
ykondi @ cs au dk
lee ey @ northeastern edu
abhi @ neu edu
tyner l @ northeastern edu
2023-04-28: approved
2023-04-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jack Doerner and Yashvanth Kondi and Eysa Lee and abhi shelat and LaKyah Tyner},
      title = {Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance},
      howpublished = {Cryptology ePrint Archive, Paper 2023/602},
      year = {2023},
      doi = {10.1109/SP46215.2023.00120},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.