International Association
for Cryptologic Research

We present two new, highly efficient, protocols for securely generating a distributed RSA key pair in the two-party setting. One protocol is semi-honestly secure and the other maliciously secure. Both are constant round and do not rely on any specific number-theoretic assumptions and improve significantly over the state-of-the-art by allowing a slight leakage (which we show to not affect security).For our maliciously secure protocol our most significant improvement comes from executing most of the protocol in a “strong” semi-honest manner and then doing a single, light, zero-knowledge argument of correct execution. We introduce other significant improvements as well. One such improvement arrives in showing that certain, limited leakage does not compromise security, which allows us to use lightweight subprotocols. Another improvement, which may be of independent interest, comes in our approach for multiplying two large integers using OT, in the malicious setting, without being susceptible to a selective-failure attack.Finally, we implement our malicious protocol and show that its performance is an order of magnitude better than the best previous protocol, which provided only semi-honest security.

We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol.Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest:1.Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality.2.Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.