Patent Document ID: 20040254967
Application ID: 10768933
Patent Flag: 0

Claim One:
1. A method for distributed computation of an RSA inverse value (y) in an asynchronous network from at least two input values (x, e) among n−1 participating network devices comprising t<n/4 faulty devices and a non-faulty leader device, the participating network devices holding share values of the Euler function (&phgr;(N)) of an RSA modulus (N), each participating network device performing the steps of: (a) choosing a first random value (q) and a second random value (r); (b) sharing over integers () the first random value (q), the second random value (r), and the zero value (0); (c) the leader device performing additionally the steps of: (i) receiving a first, second, and third sub-share value (q i, r i, 0 i ) from at least t&plus;1 participating network devices; (ii) broadcasting the identities of said participating network devices; (d) receiving the identities and corresponding sub-share values (q i, r i, 0 i ); (e) deriving a sum-share value (F) from one of the share values, the at least one input value (e), and the corresponding first, second and third sub-share values (q i, r i, 0 i ) defined by the identities, (f) broadcasting the sum-share value (F); (g) receiving 2t&plus;1 sum-share values (F i ); (h) deriving a polynomial (ƒ) interpolating the sum-share values (F i ) and an exponent share value (d P ) dependent on the polynomial (ƒ), and an inverse-share value (y P ) dependent on the exponent share value (d P ) and the RSA modulus (N); (i) broadcasting the inverse-share value (y P ); (j) receiving t&plus;1 inverse-share values (y i ); and (k) obtaining the RSA inverse value (y) from the received inverse-share value (y i ).