Robust Threshold DSS Signatures

We present threshold DSS (Digital Signature Standard) signatures where the power to sign is shared by n players such that for a given parameter t < n/2 any subset of 2t + 1 signers can collaborate to produce a valid DSS signature on any given message, but no subset of t corrupted players can forge a signature (in particular, cannot learn the signature key). In addition, we present a robust threshold DSS scheme that can also tolerate n/3 players who refuse to participate in the signature protocol. We can also endure n/4 maliciously faulty players that generate incorrect partial signatures at the time of signature computation. This results in a highly secure and resilient DSS signature system applicable to the protection of the secret signature key, the prevention of forgery, and increased system availability.Our results significantly improve over a recent result by Langford from CRYPTO’95 that presents threshold DSS signatures which can stand much smaller subsets of corrupted players, namely, t ≈ √n, and do not enjoy the robustness property. As in the case of Langford’s result, our schemes require no trusted party. Our techniques apply to other threshold ElGamal-like signatures as well. We prove the security of our schemes solely based on the hardness of forging a regular DSS signature.