Tight Security for BBS Signatures
Paper 2025/1973
Tight Security for BBS Signatures
Rutchathon Chairattana-Apirom
, University of Washington
Dennis Hofheinz
, ETH Zurich
Stefano Tessaro
, University of Washington
Abstract
This paper studies the concrete security of BBS signatures (Boneh, Boyen, Shacham, CRYPTO '04; Camenisch and Lysyanskaya, CRYPTO '04), a popular algebraic construction of digital signatures which underlies practical privacy-preserving authentication systems and is undergoing standardization by the W3C and IRTF.
Sch\"age (Journal of Cryptology '15) gave a tight standard-model security proof under the $q$-SDH assumption for a less efficient variant of the scheme, called BBS+--here, $q$ is the number of issued signatures. In contrast, the security proof for BBS (Tessaro and Zhu, EUROCRYPT '23), also under the $q$-SDH assumption, is \emph{not} tight. Nonetheless, this recent proof shifted both standardization and industry adoption towards the more efficient BBS, instead of BBS+, and for this reason, it is important to understand whether this tightness gap is inherent. Recent cryptanalysis by Chairattana-Apirom and Tessaro (ASIACRYPT '25) also shows that a tight reduction to $q$-SDH is the best we can hope for.
This paper closes this gap in two different ways. On the positive end, we show a novel tight reduction for BBS in the case where each message is signed at most once--this case covers in particular the common practical use case which derandomizes signing. On the negative end, we use a meta-reduction argument to prove that if we allow generating multiple signatures for the same message, then {\em no} algebraic reduction to $q$-SDH (and its variants) can be tight.
Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2026
Keywords
BBS Signatures
Pairing-based Signatures
Anonymous Credentials
Tight Security
Contact author(s)
rchairat
cs washington edu
hofheinz
inf ethz ch
tessaro
cs washington edu
History
2026-02-20: revised
2025-10-22: received
See all versions
Short URL
License
CC BY
BibTeX
@misc{cryptoeprint:2025/1973,
author = {Rutchathon Chairattana-Apirom and Dennis Hofheinz and Stefano Tessaro},
title = {Tight Security for {BBS} Signatures},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1973},
year = {2025},
url = {https://eprint.iacr.org/2025/1973}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.