Secure Multiparty Computation

What is Secure Multiparty Computation?
Secure multiparty computation, also referred to as multiparty computation(MPC) or privacy-preserving computation, aims to allow multiple parties to collectively compute a function over their inputs while keeping their inputs private to themselves. This is useful in situations where the parties have sensitive data that they do not want to share, but still need to be able to perform calculations with that data. One concrete application of MPC could be that the employees of a company want to compute their average salaries, but none want to reveal their exact salaries to others.
Why is MPC Useful?
Computing the average salary privately seems like a trivial application. However, MPC can and is used to tackle even more challenging problems.
In the healthcare domain, for example, multiple hospitals may want to collaborate on a research project, but they may not want to share their individual patient data with each other. MPC allows them to perform calculations on their data without revealing it to the other hospitals.
In the financial industry, for example, multiple banks may want to pool their resources to perform credit checks on potential borrowers, but they do not want to reveal their individual customer data to each other. Secure multiparty computation allows them to perform these credit checks without revealing their data.
In the tech industry, MPC can also find use cases on edge devices. For example, smart thermometers owned by homeowners might want to collectively come up with an intelligent AC schedule based on user behaviors from all devices, yet each individual smart thermometer may not be allowed to share user behavior data that they each collected directly.
What are Some Common Approaches to MPC?
Roughly speaking, the common approaches to MPC can be divided into noise-based and non-noise-based methods. Differential privacy is a representative noise-based method, whereas garbled circuit, homomorphic encryption, and secret sharing are the typical non-noise-based methods. I will briefly describe what each of them is.
Differential Privacy
You might have heard of differential privacy a lot lately. Differential privacy is more often used in the context of sharing information about multiple individuals. It is a mathematical definition of privacy that when the input data is modified slightly, the output of the computation cannot be used to infer things about the individual. Differential privacy can be achieved by adding noises to the input data, model parameters, and even results. Imagine that we want to compute output $$y$$on inputs $$x_1, x_2,x_3...x_n$$with the function $$f$$that is parameterized by the parameter $$\theta$$:$$y = f_\theta(x_1, x_2, ..., x_n)$$Then to achieve differential privacy, you might need to add noise into the input:$$y = f_\theta(x_1+r_1, x_2+r_2,...,x_n+r_n)$$Or add noise into the parameter:$$y = f_{\theta+r_\theta}(x_1, x_2,...,x_n)$$Or add noise into the output:$$y = f_\theta(x_1, x_2,...,x_n) + r$$If the amount of noise is proper, a less accurate but still useful result can be computed. Furthermore, information about the original input cannot be easily inferred from changes in results when small alterations in the input are made.
Garbled Circuit
There is really no easy way to explain how garbled circuit works (we will leave to the next article for a detailed walk-through). Explaining in a very handwavy way, garbled circuit allows secure two-party computation of a function implemented in logical gates. Party A generates the circuit, garbles it (encrypts the circuit), and sends it to party B. Party B garbles its input with the help of party A without revealing his inputs to party A, and then feed the garbled inputs to the garbled circuit. Party B obtains the output which he does not know how to interpret back to party A for interpretation. At last, party A shares the interpretation with party B.
Homomorphic Encryption
Homomorphic encryption is much more intuitive than garbled circuit. Again, let $$y = f(x_1, x_2, ..., x_n)$$ where $$f$$ is the function we want to compute and $$x_1, ..., x_n$$be the inputs. $$enc$$is a homomorphic encryption function if$$enc(f(x_1, x_2, ..., x_n)) = f(enc(x_1), enc(x_2), ..., enc(x_n))$$That is, the encrypted output of a function equals to the output of the function computed on encrypted inputs. If such a homomorphic encryption function (along with the corresponding decryption function) exists, we can use it to allow secure computation between multiple parties. Taking two-party computation as an example, party A could generate a homomorphic encryption-decryption pair, encrypt its input and send over the cipher text along with the encryption key. Party B uses the encryption key received to encrypt its input and compute on function $$f$$using both encrypted inputs. Party B sends the result back to party A for decryption so that both can learn about the computation result.
Secret Sharing
The idea of secret sharing is to shard the inputs into multiple pieces and distribute to multiple parties. That way, no single party would have enough information to learn about the inputs, but collectively, they might be able to do some computation on the inputs. A very simple example would be to split the input $$x = x_1 + x_2 + ... + x_n$$and $$y=y_1 + y_2 + ... + y_n$$then distribute $$x_i$$and $$y_i$$to party $$i$$. Thay way, party i can compute $$z_i = x_i + y_i$$locally, and collectively they can compute $$z = z_1 + z_2 + ... + z_n = x + y$$. This way, we enabled multiple parties to collectively compute the value of $$x+y$$without any party knowing the true values of $$x$$or $$y $$