Realizing Distributed RSA using Secure Multiparty Computations

Abstract

This thesis describes the basic theory of multiparty computation (MPC) in addition to a fully functional distributed Rivest-Shamir-Adleman (RSA) protocol for three players implemented in Virtual Ideal Functionality Framework (VIFF) using secure MPC (SMPC). MPC can be used to solve problems where n players, each with a private input xi, wants to compute a function with public output f(x1, x2, , xn) = y, such that the private inputs remains secret for each player, but the output y is public. A cornerstone in MPC is the concept of secret sharing. In secret sharing, a dealer has a secret and gives each participating player a share of the secret in such a way that a certain number of the players are needed in order to reconstruct the secret. The number of players needed to reconstruct the secret is referred to as the threshold of the scheme. VIFF is a high level programming framework that allows programmers to create applications using SMPC for any number of players in an easy, efficient and secure manner. The distributed RSA solution implemented in VIFF includes distributed key generation, decryption and signature, which are the main functions needed for the distributed RSA scheme, and is based on the distributed RSA algorithm proposed by Dan Boneh and Matthew Franklin in 1997. Four improvements compared to Boneh and Franklin's algorithm are described, two related to the run-time and two related to the security of the algorithm. The run-time improvements are regarding the distributed trial division step and the local trial division on the revealed N, both implemented. The security improvements are related to the way a random number is used to secure a revealed number. The first security improvement is related to the distributed trial division, whereas the second security improvement is regarding the alternative step in the biprimality test. The first security improvement, which is also the more important of the two, has been implemented in this thesis. At last some benchmarks regarding the key generation, decryption and signature process are presented, which indicates that the current implementation is best suited for scenarios where the distributed RSA keys can be generated in advance, whereas the decryption and signature process is fast enough for any type of scenario. The key generation process can become much faster with a few adjustments described at the end of the thesis.