Robust and efficient sharing of RSA functions

We present two efficient protocols which implement robust threshold RSA sig nature schemes, where the power to sign is shared by N players such that an y subset of T + 1 or more signers can collaborate to produce a valid RSA si gnature 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 corre ct signature is computed even if up to T players behave in an arbitrarily m alicious way during the signature protocol. This, in particular, includes t he cases of players who refuse to participate or who introduce erroneous va lues into the computation. Our robust protocols achieve optimal resiliency as they can tolerate up to (N - 1)/2 faults, and their efficiency is compar able 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 funct ion. We show that adding robustness to the existing threshold RSA schemes reduce s to solving the problem of how to verify an RSA signature without a public verification exponent. Our technical contribution focuses on solving this problem Once a solution to this problem exists it can be applied to any exi sting threshold RSA signature scheme in order to achieve a robust threshold safe prime RSA signature scheme.