International Association
for Cryptologic Research

BBS/BBS+ signatures are the most promising solution to instantiate practical and lightweight anonymous credentials. They underlie standardization efforts by the W3C and the IRTF. Due to their potential for large scale deployment, it is paramount to understand their concrete security, but a number of questions have been left open by prior works. To this end, the security proofs by Au et al. (SCN '06), Camenisch et al. (TRUST '16), and Tessaro and Zhu (EUROCRYPT '23) show reductions from $q$-SDH in groups of prime order $p$, where $q$ is the number of issued signatures. However, these prior works left the possibility open that BBS/BBS+ is "even more secure" than what can be guaranteed by such proofs. Indeed, while the $q$-SDH assumption is subject to an attack that uses $O(\sqrt{p/q})$ group exponentiations (Cheon, EUROCRYPT '06) for several choices of $q$, no attack with a similar complexity appears to affect either of BBS+ and "deterministic" BBS, for which the best known attacks amount to recovering the secret key by breaking the discrete logarithm problem. The assumption that this attack is best possible also seemingly justifies the choice of parameters in practice.

Our result shows that this expectation is not true. We show new attacks against BBS+ and deterministic BBS which, after seeing $q$ signatures, allow us to recover the secret key with the same complexity as solving the $\Theta(q)$-Discrete Logarithm problem, which in turn is proportional to $O(\sqrt{p/q})$ for many choices of $q$. Further, we also extend the attack to a reduction showing that the security of BBS+ and deterministic BBS implies the $\Theta(q)$-SDH assumption.