International Association
for Cryptologic Research

In academic MPC papers, protocols are typically optimized for a certain environment. Thus, one may consider very powerful machines connected via a very fast and high bandwidth network, or one may consider mobile phones communicating, and so on. However, in some cases, the environment is not known and tradeoffs need to be made. In this talk, we will describe some of the challenges encountered in building a product based on MPC that is deployed in very different environments by different customers. For a test case, we will consider specific challenges that arose for two-party RSA key generation, and how the "best academic protocol" needed to be modified for generic deployment, and in particular in settings with very poor bandwidth. The talk will present what changes were made to the protocol and why, together with general lessons learned that we believe are of importance to the research community.

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.