2 posts tagged with "Cryptography"

As briefly mentioned in the previous article on the broad overview of secure multiparty computation, homomorphic encryption is one way to achieve secure Multiparty Computation (MPC). It is widely used to implement various MPC algorithms.

Homomorphic Encryption Definition​

Let

$$y = f(x_1, x_2, ..., x_n)$$

where $f$ is a function to be computed and $x_1, ..., x_n$ are 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))$$

In other words, homomorphic encryption functions allow one to perform computations on encrypted data. However, computation on the encrypted data gives you encrypted outputs, which are not useful unless they can be decrypted to produce sensible values. Therefore, homomorphic encryption functions need to come with a corresponding decryption function that can be used to recover the final encrypted results.

Let's denote the decryption function as $dec$, we should have the following relation:

$$\begin{align*} dec(enc(f(x_1, x_2, ..., x_n))) &= dec(f(enc(x_1), enc(x_2), ..., enc(x_n))) \\ &= f(x_1, x_2, ..., x_n) \end{align*}$$

Finding a pair of encryption and decryption functions ($enc-dec$) that would work perfectly regardless of what function $f$ is can be challenging. However, it is possible to create homomorphic encryption functions when restrictions are added to the form of function $f$.

For example, suppose function $f$ can only consist of multiplications. The following set of homomorphic encryption-decryption functions might just work:

$$enc(x) = x^e \mod n \\ dec(x) = x^d \mod n$$

Where $e$, $d$ and $n$ are some carefully chosen numbers so that $(x^e)^d = x \mod n$ for any given $x$. For the curious readers, please refer to this WikiPedia page to learn about how these numbers are generated to satisfy the above equation.

To illustrate how this works, let's consider a simple function $f(x_1, x_2, x_3) = x_1 * x_2 * x_3$ that only consists of multiplications. It is clear that:

$$\begin{align*} f(enc(x_1), enc(x_2), enc(x_3)) &= f(x_1^e \mod n,x_2^e \mod n, x_3^e \mod n) \\ &= (x_1^e \mod n) * (x_2^e \mod n) * (x_3^e \mod n) \\ &= x_1^e * x_2^e * x_3^e \mod n \\ &= (x_1 * x_2 * x_3)^e \mod n \\ &= f(x_1,x_2,x_3)^e \mod n \\ &= enc(f(x_1,x_2,x_3)) \end{align*}$$

This fulfills the requirement that $enc(f(x_1, x_2, ..., x_n)) = f(enc(x_1), enc(x_2), ..., enc(x_n))$.

For the decryption process:

$$\begin{align*} dec(f(enc(x_1), enc(x_2), enc(x_3))) &= dec(f(x_1,x_2,x_3)^e \mod n) \\ &= (f(x_1,x_2,x_3)^e \mod n)^d \mod n\\ &= (f(x_1,x_2,x_3)^e)^d \mod n\\ &= f(x_1,x_2,x_3) \mod n \end{align*}$$

We can indeed recover the correct result of multiplication from the output of computing function $f$ on the encrypted inputs.

The homomorphic system above, called unpadded RSA (since it leverages the RSA cryptosystem), is one example of the so-called partially homomorphic crypto systems. As the name suggests, they are "partial" because they don't work on any arbitrary function $f$. There are many other partially homomorphic crypto systems which you can find here.

Homomorphic Encryption and Secure Multiparty Computation​

Now you might wonder: how does homomorphic encryption help us achieve secure multiparty computation? The answer to this question requires some creativity as you would have to utilize homomorphic encryption in different ways under different circumstances. Let's illustrate with an example based on the unpadded RSA homomorphic crypto system.

Consider three people Alice, Bob and Charlie each holding on to some number $a$, $b$, $c$ that they wish to keep secret. They want to collectively compute the product of their numbers without revealing their individual numbers to each other. Their objective could be reached with the kind help of two other people Sarah and Nancy.

They proceed as follows:

1. Sarah generates the unpadded RSA $dec-dec$ pair, and sends the $enc$ function to Alice, Bob and Charlie.
2. Alice, Bob and Charlie compute $a' = enc(a)$, $b' = enc(b)$, $c' = enc(c)` respectively and send them to Nancy.
3. Nancy multiplies the numbers she received from Alice, Bob and Charlie to obtain $d' = a' * b' * c'$, and send $d'$ back to Sarah.
4. Sarah then computed $d = dec(d')$ and sends it back to Alice, Bob and Charlie.

Now, $d$ is really just the multiplicative product $a * b * c$.

In the above procedure, none of Alice, Bob and Charlie revealed their secretive numbers to anyone else but all of them learned the multiplicative product of the numbers they had.

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$.