Paper 2026/651

Robot: Robust Threshold BBS+ in Two Rounds

Tian Qiu, Nanyang Technological University

Bowen Jiang, Singapore Management University

Haiyang Xue, Singapore Management University

Guomin Yang, Singapore Management University

Man Ho Au, The Hong Kong Polytechnic University

Robert H. Deng, Singapore Management University

Kwok-Yan Lam, Nanyang Technological University

Abstract

The BBS+ signature scheme is a widely used foundation for anonymous credential systems. It is favored for its support of selective disclosure and its efficiency in proving credential possession. However, in traditional settings, credentials are typically issued by a single authority, creating a single point of failure and potential security risk. This limitation can be mitigated by adopting a distributed variant, known as the threshold BBS+ scheme. In this work, we present \textit{Robot}, the first two-round threshold BBS+ signature scheme. Robot is round-minimal and achieves robustness, ensuring that every signing execution successfully completes as long as there exist $t+1$ parties behaving honestly. To achieve this, we employ a threshold verifiable random function (TVRF) to robustly generate the public nonces within a single round. Specifically, we utilize an efficient DDH-based TVRF construction, which not only provides our scheme with a round advantage but also enhances its overall performance. Then, by carefully invoking the threshold Castagnos-Laguillaumie and threshold ElGamal homomorphic encryptions, we complete all remaining non-linear operations within the second round. Asymptotically, Robot achieves a constant per-party upload communication and linear computation overhead with respect to the number of signers. Compared with the four-round robust scheme of Wong et al. (NDSS'24, WMC24), which has the same asymptotic complexity, Robot achieves a smaller constant communication cost (2.02 KB vs. 3.23 KB) and nearly halves the runtime. Compared with the three-round robust scheme of Tang and Xue (S\&P'25, TX25), which has linear communication overhead, Robot exhibits better communication and computational efficiency when the number of signers is five or more.

@misc{cryptoeprint:2026/651,
      author = {Guofeng Tang and Tian Qiu and Bowen Jiang and Haiyang Xue and Guomin Yang and Man Ho Au and Robert H. Deng and Kwok-Yan Lam},
      title = {Robot: Robust Threshold {BBS}+ in Two Rounds},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/651},
      year = {2026},
      url = {https://eprint.iacr.org/2026/651}
}