Advertisement
Published in:
2009 | OriginalPaper | Chapter
Reducing the Complexity in the Distributed Computation of Private RSA Keys
Author : Peter Lory
Published in: Information Security and Privacy
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Catalano, Gennaro and Halevi (2000) present a protocol for the distributed computation of inverses over a shared secret modulus. The most important application of their protocol is the distributed computation of the private RSA key from the public key. The protocol is attractive, because it requires only two rounds of communication in the case of honest but curious players. The present paper gives a modification of this protocol, which reduces its complexity from
O
(
n
3
(log
n
)
2
+
n
2
(log
n
) (log
N
) + (log
N
)
2
) to
O
(
n
3
log
n
+
n
2
log
N
+ (log
N
)
2
) bit-operations per player, where
n
is the number of players and
N
is the RSA modulus. The number of communication rounds is the same as in the original protocol.