Efficient joint random number generation for secure multi-party computation

Abstract

Large availability of smart devices and an increased number of online activities result in extensive personalized or customized services in many domains. However, the data these services mostly rely on are highly privacy-sensitive, as in pace-makers. In the last decades, many privacy breaches have increased privacy awareness, leading to stricter regulations on data processing. To comply with this legislation, proper privacy preservation mechanisms are required. One of the technological solutions, which is also provably secure, is Secure Multi-Party Computation (SMPC) that can compute any function with secret inputs. Mainly, in several SMPC solutions, such as data aggregation, we observe that secret values distributed among parties are masked with random numbers, encrypted and combined to yield the desired outcome. To ensure correct decryption of the final result, it is required that these numbers sum to a publicly known value, for instance, zero. Despite its importance, many of the corresponding works omit how to obtain such random numbers jointly or suggest procedures with high computational and communication overhead. This paper proposes two novel protocols for Joint Random Number Generation with very low computational and communication overhead. Our protocols are stand-alone and not embedded in others, and can therefore be used in data aggregation and other applications, for instance, machine learning algorithms, that require such random numbers. We first propose a protocol that relies on bit-wise sharing of individually generated random numbers, allowing parties to adapt random numbers to yield a public sum. Second, we propose a protocol that uses the sign function to generate a random number from broadcast numbers. We provide security and complexity analyses of our protocols.