Threshold Signatures with Private Accountability via Secretly Designated Witnesses

Threshold signature is a powerful cryptographic technique with a large number of real-life applications. As designed by Boneh and Komlo (CRYPTO’22), TAPS is a new threshold signature integrating privacy and accountability. It allows a combiner to combine t signature shares while protecting t and the signing group from the public. It also enables a tracer to trace a threshold signature to its original signing group. Despite being valuable, TAPS neglects the witnessing of tracing, i.e., leaves the tracing activity unrestrained. In this paper, we introduce Accountable and Private Threshold Signature with Hidden Witnesses (HiTAPS) that not only provides privacy and accountability, but also incorporates witnessed tracing. In specific, we first utilize Dynamic Threshold Public-Key Encryption (DTPKE) and ElGamal encryption to designate a set of t^′ witnesses for endorsing the tracing activity. We then compute a keyed-hash tag for the t^′ witnesses to initiate the tracing activity secretly. Moreover, we present an optimized protocol HiTAPS2 to reduce communication overhead of the combiner. We formalize the definitions, security, and privacy for HiTAPS. We formally prove its security and privacy. To evaluate the performance of HiTAPS and HiTAPS2, we build a prototype based on pypbc. Experimental results show that HiTAPS takes 217(370) ms to combine (track) a threshold signature of 5 signers (witnesses). The optimized HiTAPS2 only takes 137 ms to combine a threshold signature of 5 signers.