** Reference:**
* Advances in Cryptology - EUROCRYPT 2000.*
Lecture Notes in Computer Science, vol. 1807, Pages 190-206,
Springer-Verlag, 2000.

** Abstract: **
We discuss the following problem: Given an integer *phi*, shared
secretly among *n* players and a prime number *e*, how can
the players efficiently compute a sharing of *e^{-1} mod phi*.
The most interesting case is when *phi* is the Euler function of
a known RSA modulus *N*, *phi = phi(N)*. The problem has
several applications, among which the construction of threshold variants
for two recent signature schemes proposed by Gennaro-Halevi-Rabin and
Cramer-Shoup.

We present new and efficient protocols to solve this problem, improving over previous solutions by Boneh-Franklin and Frankel et al. Our basic protocol (secure against honest but curious players) requires only two rounds of communication and a single GCD computation. The robust protocol (secure against malicious players) adds only a couple of rounds and a few modular exponentiations to the computation.

** Keywords: **
Mudular inversion, Threshold computation, RSA Signatures.

** Availability: **
Proceedings version available as Compressed PostScript (51 Kbyte), long version in PDF (364KB).

Shai Halevi's home page.