Robust and Efficient Sharing of RSA Functions

We present two efficient protocols which implement robust threshold RSA signature schemes, where the power to sign is shared by N players such that any subset of T+1 or more signers can collaborate to produce a valid RSA signature on any given message, but no subset of T or less corrupted players can forge a signature. Our protocols are robust in the sense that the correct signature is computed even if up to T players behave in an arbitrarily malicious way during the signature protocol. This, in particular, includes the cases of players who refuse to participate or who introduce erroneous values into the computation. Our robust protocols achieve optimal resiliency as they can tolerate up to (N-1)/2 faults, and their efficiency is comparable with the efficiency of the underlying threshold RSA signature scheme. Our protocols require RSA moduli which are the product of two safe primes, and that the underlying (centralized) RSA signature scheme is unforgeable. Our techniques also apply to the secure sharing of the RSA decryption function. We show that adding robustness to the existing threshold RSA schemes reduces to solving the problem of how to verify an RSA signature without a public verification Received 21 March 1997 and revised 28 September 1999