Paper 2023/1076

Non-Interactive Threshold BBS+ From Pseudorandom Correlations

Sebastian Faust, Technical University of Darmstadt
Carmit Hazay, Bar-Ilan University
David Kretzler, Technical University of Darmstadt
Leandro Rometsch, Technical University of Darmstadt
Benjamin Schlosser, Technical University of Darmstadt

The BBS+ signature scheme is one of the most prominent solutions for realizing anonymous credentials. Its prominence is due to properties like selective disclosure and efficient protocols for creating and showing possession of credentials. Traditionally, a single credential issuer produces BBS+ signatures, which poses significant risks due to a single point of failure. In this work, we address this threat via a novel $t$-out-of-$n$ threshold BBS+ protocol. Our protocol supports an arbitrary security threshold $t \leq n$ and works in the so-called preprocessing setting. In this setting, we achieve non-interactive signing in the online phase and sublinear communication complexity in the number of signatures in the offline phase, which, as we show in this work, are important features from a practical point of view. As it stands today, none of the widely studied signature schemes, such as threshold ECDSA and threshold Schnorr, achieve both properties simultaneously. To this end, we design specifically tailored presignatures that can be directly computed from pseudorandom correlations and allow servers to create signature shares without additional cross-server communication. Both our offline and online protocols are actively secure in the Universal Composability model. Finally, we evaluate the concrete efficiency of our protocol, including an implementation of the online phase and the expansion algorithm of the pseudorandom correlation generator (PCG) used during the offline phase. The online protocol without network latency takes less than $15 ms$ for $t \leq 30$ and credentials sizes up to $10$. Further, our results indicate that the influence of $t$ on the online signing is insignificant, $< 6 \%$ for $t \leq 30$, and the overhead of the thresholdization occurs almost exclusively in the offline phase. Our implementation of the PCG expansion is the first considering correlations between more than $3$ parties and shows that even for a committee size of $10$ servers, each server can expand a correlation of up to $2^{16}$ presignatures in about $600$ ms per presignature.

Available format(s)
Public-key cryptography
Publication info
Threshold SignatureBBS+Pseudorandom Correlation FunctionsPseudorandom Correlation Generators
Contact author(s)
sebastian faust @ tu-darmstadt de
carmit hazay @ biu ac il
david kretzler @ tu-darmstadt de
leandro rometsch @ stud tu-darmstadt de
benjamin schlosser @ tu-darmstadt de
2024-02-19: last of 5 revisions
2023-07-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastian Faust and Carmit Hazay and David Kretzler and Leandro Rometsch and Benjamin Schlosser},
      title = {Non-Interactive Threshold BBS+ From Pseudorandom Correlations},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1076},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.