An Asynchronous Protocol for Distributed Computation of RSA Inverses and its Applications

This paper presents an efficient asynchronous protocol to compute RSA inverses with respect to a public RSA modulus N whose factorization is secret and shared among a group of parties. Given two numbers x and e, the protocol computes y such that ye ≡ x (mod N). A synchronous protocol for this task has been presented by Catalano, Gennaro, and Halevi (Eurocrẏpt 2000), but the standard approach for turning this into an asynchronous protocol would require a Byzantine-agreement sub-protocol. Our protocol adopts their approach, but exploits a feature of the problem in order to avoid the use of a Byzantine agreement primitive. Hence, it leads to efficient asynchronous protocols for threshold signatures and for Byzantine agreement based on the strong RSA assumption, without the use of random oracles.