Paper 2023/275

Revisiting BBS Signatures

Stefano Tessaro, University of Washington
Chenzhi Zhu, University of Washington

BBS signatures were implicitly proposed by Boneh, Boyen, and Shacham (CRYPTO ’04) as part of their group signature scheme, and explicitly cast as stand-alone signatures by Camenisch and Lysyanskaya (CRYPTO ’04). A provably secure version, called BBS+, was then devised by Au, Susilo, and Mu (SCN ’06), and is currently the object of a standardization effort which has led to a recent RFC draft. BBS+ signatures are suitable for use within anonymous credential and DAA systems, as their algebraic structure enables efficient proofs of knowledge of message-signature pairs that support partial disclosure. BBS+ signatures consist of one group element and two scalars. As our first contribution, we prove that a variant of BBS+ producing shorter signatures, consisting only of one group element and one scalar, is also secure. The resulting scheme is essentially the original BBS proposal, which was lacking a proof of security. Here we show it satisfies, under the q-SDH assumption, the same provable security guarantees as BBS+. We also provide a complementary tight analysis in the algebraic group model, which heuristically justifies instantiations with potentially shorter signatures. Furthermore, we devise simplified and shorter zero-knowledge proofs of knowledge of a BBS message-signature pair that support partial disclosure of the message. Over the BLS12-381 curve, our proofs are 896 bits shorter than the prior proposal by Camenisch, Drijvers, and Lehmann (TRUST ’16), which is also adopted by the RFC draft. Finally, we show that BBS satisfies one-more unforgeability in the algebraic group model in a scenario, arising in the context of credentials, where the signer can be asked to sign arbitrary group elements, meant to be commitments, without seeing their openings.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Digital SignaturesBBS SignaturesPairing-based SignaturesAnonymous Credentials
Contact author(s)
tessaro @ cs washington edu
zhucz20 @ cs washington edu
2023-02-27: approved
2023-02-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Stefano Tessaro and Chenzhi Zhu},
      title = {Revisiting BBS Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2023/275},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.