Paper 2026/573

Two-Party BBS+ Signature in Two Passes

Tian Qiu, Nanyang Technological University

Guofeng Tang, Singapore Management University

Yuqing Niu, Singapore Management University

Bowen Jiang, Singapore Management University

Jun Zhou, East China Normal University

Haiyang Xue, Singapore Management University

Guomin Yang, Singapore Management University

Abstract

The BBS+/BBS signature scheme is a key building block for anonymous credentials and privacy-preserving authentication and is currently being standardized and increasingly deployed in practice. To avoid the problem of single-point-of-failure, many threshold BBS+ protocols have been recently proposed for general $t$-out-of-$n$ settings. In practice, however, a $2$-out-of-$2$ policy between a server and a mobile device is sufficient to distribute trust while keeping the system lightweight. Yet, existing threshold designs still require at least three rounds/passes and multi-kilobyte communication in the two-party setting. In this work, we focus on the two-party setting and show that one can achieve reduced interaction while maintaining low computational and communication overhead. Specifically, we present a two-pass two-party BBS+ signing protocol that requires only 0.85KB of communication per signature, about 27% of the currently most bandwidth-efficient work (S&P'25) in the $2$-out-of-$2$ setting. It achieves competitive signing times (roughly 62ms for one party and 46ms for the other) and remains efficient even for large message vectors (e.g., $\ell = 500$), making it attractive for practical deployments. Overall, our protocol is only slower than the fastest OT-based design (S&P'23) but uses nearly two orders of magnitude less bandwidth. We provide a full simulation-based security proof in the standard real-ideal paradigm. As an extension, our protocol can be generalized to a $2$-out-of-$n$ threshold setting naturally.

@misc{cryptoeprint:2026/573,
      author = {Xiaofei Wu and Tian Qiu and Guofeng Tang and Yuqing Niu and Bowen Jiang and Jun Zhou and Haiyang Xue and Guomin Yang},
      title = {Two-Party {BBS}+ Signature in Two Passes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/573},
      year = {2026},
      url = {https://eprint.iacr.org/2026/573}
}