Tight Security for BBS Signatures

Computer Science > Cryptography and Security [Submitted on 7 Aug 2026] Tight Security for BBS Signatures Rutchathon Chairattana-Apirom, Dennis Hofheinz, Stefano Tessaro 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äge (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. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2608.06724 [cs.CR]   (or arXiv:2608.06724v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2608.06724 Focus to learn more Journal reference: In: Daemen, J., Thome, E. (eds) Advances in Cryptology - EUROCRYPT 2026. Lecture Notes in Computer Science, vol 16541. Springer, Cham Related DOI: https://doi.org/10.1007/978-3-032-25291-3_9 Focus to learn more Submission history From: Rutchathon Chairattana-Apirom [view email] [v1] Fri, 7 Aug 2026 02:37:57 UTC (113 KB) Access Paper: view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-08 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)