Secure Multiparty Computation

What is Secure Multiparty Computation?

Secure multiparty computation (MPC), also referred to as privacy-preserving computation, allows multiple parties to collectively compute a function over their inputs while keeping these inputs private. This can be beneficial in situations where sensitive data are involved. For instance, employees of a company may want to calculate their average salaries without revealing their exact earnings.

Why is MPC Useful?

While calculating average salary privately may seem trivial, MPC can handle more challenging problems. In healthcare, for example, hospitals might want to collaborate on a research project without sharing individual patient data. MPC enables them to perform calculations on their data without revealing it to other institutions.

In the financial sector, banks might wish to pool their resources for credit checks on potential borrowers, but they do not want to expose their individual customer data. Here, MPC permits secure credit checks without data disclosure.

The tech industry also can utilize MPC on edge devices. For instance, smart thermometers owned by homeowners might want to collectively devise an intelligent AC schedule based on user behaviors from all devices. However, each individual smart thermometer may not be allowed to share directly the user behavior data they collected.

What are Some Common Approaches to MPC?

Common approaches to MPC can roughly be divided into noise-based and non-noise-based methods. Differential privacy represents noise-based methods, while garbled circuit, homomorphic encryption, and secret sharing are typical non-noise-based methods.

Differential Privacy

Differential privacy is commonly used when sharing information about multiple individuals. It is a mathematical definition of privacy that ensures slight modifications in the input data do not permit inference about any individual. This can be achieved by adding noise to the input data, model parameters, or results.

Let's say 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)$. Differential privacy can then be achieved by adding noise to the input: $y = f_\theta(x_1+r_1, x_2+r_2,...,x_n+r_n)$ or to the parameter: $y = f_{\theta+r_\theta}(x_1, x_2,...,x_n)$ or to the result itself: $y = f_\theta(x_1, x_2,...,x_n) + r$.

Garbled Circuit

Garbled circuit enables secure two-party computation of a function implemented in logical gates. The process involves party A generating and garbling (encrypting) the circuit, and sending it to party B, who garbles its input with the help of party A without revealing his inputs. Party B obtains the output which he sends back to party A for interpretation.

Homomorphic Encryption

Homomorphic encryption is more intuitive than garbled circuit. Let's take $y = f(x_1, x_2, ..., x_n)$ where $f$ is the function we want to compute and $x_1, ..., x_n$ are the inputs. A homomorphic encryption function $enc$ satisfies $enc(f(x_1, x_2, ..., x_n)) = f(enc(x_1), enc(x_2), ..., enc(x_n))$. This means that the encrypted output of a function equals the output of the function computed on encrypted inputs.

Secret Sharing

Secret sharing involves breaking the inputs into multiple pieces and distributing them among several parties. Therefore, no single party possesses enough information to discern the inputs, but collectively, they can perform some computation. For example, if we distribute $x_i$ and $y_i$ to party $i$ such that $x = x_1 + x_2 + ... + x_n$ and $y=y_1 + y_2 + ... + y_n$, party $i$ can compute $z_i = x_i + y_i$ locally. Collectively, they can compute $z = z_1 + z_2 + ... + z_n = x + y$, thereby enabling multiple parties to collectively compute the value of $x+y$ without any party knowing the true values of $x$ or $y$.