Lecture 20: Verifiable MPC

For instance, suppose that rather than calculating \(a + b + c\), we actually wanted to compute \(2a + 3b - c + 10\).

Since we are using additive secret sharing, and scalar multiplication also commutes over addition, each party can just compute its share of the result.

	\(a\)	\(b\)	\(c\)		\(2a + 3b - c + 10\)
	\(a_1\)	\(b_1\)	\(c_1\)		\(2a_1 + 3b_1 - c_1 + 10\)
	\(a_2\)	\(b_2\)	\(c_2\)		\(2a_2 + 3b_2 - c_2 + 0\)

This is not as easy to compute. This time we cannot rely solely on commutativity of addition; we need to consider the distributive law as well.

Recall the relationships between the secret variables and their additive shares (all equations will be mod \(2^\ell\), but from now on I’m going to omit writing the modulus for brevity): \[\begin{align*} a &= a_1 + a_2 \\ b &= b_1 + b_2. \end{align*}\]

Hence, we want to compute: \[\begin{align*} c &= a \cdot b \\ &= (a_1 + a_2) (b_1 + b_2) \\ &= a_1 b_1 + a_1 b_2 + a_2 b_1 + a_2 b_2. \end{align*}\]

BU knows how to compute the term \(a_1 b_1\) on its own, and the Council knows how to compute \(a_2 b_2\) on its own. But it’s unclear how to compute the cross-terms \(a_1 b_2\) and \(a_2 b_1\) – that is, it’s unclear how to calculate these terms without the computing parties sending their shares to each other, but that would break data confidentiality.

I’ll show you today one way to resolve this problem. It relies on two useful insights.

Insight #1: let’s add a third computing server.

	\(a\)	\(b\)		\(c = a \cdot b\)
	\(a_1\)	\(b_1\)		\(\color{red}{??}\)
	\(a_2\)	\(b_2\)		\(\color{red}{??}\)
	\(a_3\)	\(b_3\)		\(\color{red}{??}\)

At first glance, this might look to make the calculation even harder to perform. Now the distributive law says that we must calculate:

\[\begin{align*} c &= (a_1 + a_2 + a_3) (b_1 + b_2 + b_3) \\ &= a_1 b_1 + a_1 b_2 + a_1 b_3 \\ &\quad + a_2 b_1 + a_2 b_2 + a_2 b_3 \\ &\quad + a_3 b_1 + a_3 b_2 + a_3 b_3. \\ \end{align*}\]

Insight #2: Let’s give each computing party two of the three shares. This is called replicated secret sharing.

• This is still not enough information for each individual computing party to reconstruct any secrets.
• But now a threshold of \(t = 2\) of the \(n = 3\) parties will collectively have enough information to reconstruct secrets.

	\(a\)	\(b\)		\(c = a \cdot b\)
	\(a_1, a_2\)	\(b_1, b_2\)		\(c_1 = a_1b_1 + a_1b_2 + a_2b_1\)
	\(a_2, a_3\)	\(b_2, b_3\)		\(c_2 = a_2b_2 + a_2b_3 + a_3b_2\)
	\(a_3, a_1\)	\(b_3, b_1\)		\(c_3 = a_3b_3 + a_3b_1 + a_1b_3\)

The punchline here is that: now there exists a computing server that can calculate each of the 9 terms in this product! So the three computing servers can calculate \(a \cdot b\) by working together in such a way that nobody has learned either \(a\) or \(b\).

\[\begin{align*} c &= (a_1 + a_2 + a_3) (b_1 + b_2 + b_3) \\ &= \color{red}{a_1 b_1} + \color{red}{a_1 b_2} + \color{gray}{a_1 b_3} \\ &\quad + \; \color{red}{a_2 b_1} + \color{blue}{a_2 b_2} + \color{blue}{a_2 b_3} \\ &\quad + \; \color{gray}{a_3 b_1} + \color{blue}{a_3 b_2} + \color{gray}{a_3 b_3}. \\ \end{align*}\]

There’s just one downside here: the computing parties have two shares of \(a\) and \(b\), but only one share of \(c\). So we cannot continue and multiply \(c\) times some other secret.

This is easy to fix with some communication: each computing party gives its share to one other party.

• \(P_1\) sends \(c_1\) to \(P_3\).
• \(P_2\) sends \(c_2\) to \(P_1\).
• \(P_3\) sends \(c_3\) to \(P_2\).

Now our invariant is maintained: each computing party starts with 2 out of 3 shares of each input, and completes multiplication with 2 out of 3 shares of each output.

To summarize, we have constructed a secure multiplication scheme with:

• One round of network communication between the computing parties.
• Correctness, since the \(n = 3\) parties work together to calculate all 9 terms shown by the distribute property.
• Perfect privacy, since each party has only 2 of the 3 additive shares of each secret.
• A threshold of \(t = 2\) parties that can reconstruct the answer (because they collectively hold all 3 shares).

Importantly: \(+\) and \(\times\) are a Turing-complete set of gates! That is, we can write any data analytic as a circuit with \(+\) and \(\times\) gates. (This may not be the fastest way to compute \(f\), but it will always work in principle.)

For instance, given the circuit below along with secret shares of \(s\), \(t\), and \(x\) it is possible for the 3 computing parties to work together to calculate:

• secret shares of the intermediate value \(w\)
• secret shares of the final result \(y\)

and then reconstruct only the output \(y\).

Hence, the protocol we have constructed today can do a secure computation of any function, as long as:

• There is an honest majority of 2 honest servers out of 3.
• The one adversarial server is run by a passive eavesdropper Eve (i.e., it still follows the protocol).

It turns out that you can also perform MPC in the dishonest majority setting, and against an actively-malicious adversary Mallory.

Here is one way to stop Mallory: we can add a fourth computing party for redundancy.

• Using replicated secret sharing, we can build a secure computation protocol with \(n = 4\) parties and a threshold of \(t = 2\) parties required to reconstruct.
• The data holders send 3 of 4 additive shares to each computing party.

	\(a\)	\(b\)		\(c = a \cdot b\)
	\(a_1, a_2, a_3\)	\(b_1, b_2, b_3\)		\(c_1\)
	\(a_2, a_3, a_4\)	\(b_2, b_3, b_4\)		\(c_2\)
	\(a_3, a_4, a_1\)	\(b_3, b_4, b_1\)		\(c_3\)
	\(a_4, a_1, a_2\)	\(b_4, b_1, b_2\)		\(c_4\)

The math for multiplication has gotten a bit more complicated, so I won’t write out explicitly how the shares of \(c\) are calculated.

\[\begin{align*} c &= (a_1 + a_2 + a_3 + a_4) (b_1 + b_2 + b_3 + b_4) \\ &= a_1 b_1 + a_1 b_2 + a_1 b_3 + a_1 b_4 \\ &\quad + \; a_2 b_1 + a_2 b_2 + a_2 b_3 + a_2 b_4 \\ &\quad + \; a_3 b_1 + a_3 b_2 + a_3 b_3 + a_3 b_4 \\ &\quad + \; a_4 b_1 + a_4 b_2 + a_4 b_3 + a_4 b_4 \end{align*}\]

Fortunately, the punchline is simple:

• For each of the 16 terms, there are two parties who know how to compute it!
• So for any computation that Mallory performs, there is an honest party who can check her math and call her out if she cheats.

Let’s take a step back and admire what we have done so far.

• We have been able to design MPC protocols to compute any data science computation.
• We can protect data confidentiality and integrity against a malicious Mallory.

Recall how additive secret sharing works. Say you have secret data \(x\) and convert it into a collection of \(n\) secret shares:

\[ x = x_1 + x_2 + \cdots + x_n \bmod{p}.\]

For now, suppose you don’t even want to compute over this data; you just want to outsource the data to several cloud providers and reconstruct it at some later date.

• So, you can disperse the message among the cloud providers by giving share \(x_i\) to provider \(i\).

• Then, many months or years later, you can retrieve the secret data by fetching all shares and adding them together.

This provides excellent confidentiality: the cloud providers can perform their job of holding onto your data for a long time, but no coalition of \(n-1\) or fewer of them can ever learn the data.

However, if one party provides an incorrect share \(x_i^* = x_i + \Delta\), then your entire secret is going to be incorrect by \(\Delta\):

\[x_1 + x_2 + \cdots + (x_i + \Delta) + \cdots + x_n = x + \Delta.\]

This is bad news for you: it means your data is corrupted, and even worse there’s no way for you to pinpoint which cloud provider is to blame.

Depending on how the economics of this hypothetical “private multi-cloud outsourcing” service works, it could also be bad news for the honest cloud providers: maybe you refuse to pay them as a result of the data corruption, even though they properly did their job and held onto your data for a long time.

Basically what we want is something like filecoin.io, which is a “decentralized storage network” based on “an open-source cloud storage marketplace, protocol, and incentive layer.” (We’re not going to explain the entirety of how filecoin works in today’s lecture, but we will describe some of the main ideas.)

The main differences here are that:

• We are adding confidentiality through secret sharing, and
• There are two stages to the protocol: a dispersal stage and a retrieval stage.

But the other trust questions from the Byzantine generals problem remain. You don’t necessarily trust the other parties entirely, and they don’t entirely trust you either.

Question. How can we provide each party with a verifiability guarantee? That is:

• During dispersal, the cloud providers want to be convinced that they’re holding onto a share of a real secret that you will pay them for.
• During retrieval, you want to be convinced that the shares are correct (even though you have forgotten the secret yourself). Otherwise, you want to be able to pinpoint which provider(s) are sending you bad shares.

Can we do this? Well… not quite.

• The good news is that the secret sharing scheme is linear, so it works fine! The providers could just send shares \(x_i + y_i\), rather than separately sending each of the two summands.
• The bad news is that the Merkle tree is not linear, so provider \(i\) cannot prove that it is sending the right value \(x_i + y_i\).

So let’s replace the Merkle tree with something else.

Using the discrete log problem, we can create a new way to commit and prove properties of the secrets that is amenable to computation.

Commitments have two security guarantees.

Specifically, we will use the hardness of the discrete log problem. Remember that this problem states that for a uniformly random choice of \(x\):

\[ (g, x) \mapsto h = g^x \text{ is easy to compute, but } (g, h) \mapsto x = \log_g(h) \text{ is hard to compute}\]

Question. How can we construct a commitment scheme from discrete logs?

For today, we will only consider a simplified version of the problem where message \(m\) to be committed is itself chosen uniformly at random.

• Admittedly this isn’t usually the case. for instance, the messages that you send to your friends over the Internet probably have a lot of structure to them, such as being phrases or sentences of English words.
• But this will be the case for cryptographic secret shares! That will suffice for us today, so let’s go with this assumption for now.

Here is a commitment scheme designed by Paul Feldman in 1987. As a starting point, assume that all parties agree upon some base element \(g\) (e.g., it is specified in some open standard).

• commit(m): create the commitment \(c = g^m\).
• open(c, m): reveal \(m\), so that the receiver can calculate \(g^m\) itself and check that it is equal to \(c\).

This commitment scheme achieves:

• Binding because there is a one-to-one mapping between messages \(m\) and commitments \(c\), so it is impossible to open to any other message.
• Hiding because inverting \(c\) to recover \(m\) is computationally infeasible according to the discrete log assumption.

Specifically, we will use Feldman commitments to construct a new verifiable secret sharing scheme. The key insights here are that:

So let’s give this property a fancy new name: additive homomorphism. We say that Feldman and Pedersen commitments are additively homomorphic, because given several commitments it is possible (somehow) to compute the commitment to the sum of the underlying messages.

In dispersal:

Retrieving \(x\) works similarly as before:

• Each cloud provider sends their share \(x_i\).
• The leader can check that \({g_i}^{x_i}\) equals the appropriate commitment inside the vector.

Now let’s do secure addition of secrets. Suppose that two secrets \(x\) and \(y\) have been dispersed to the same set of cloud providers (even by different leaders!), with corresponding commitment vectors \(\vec{c}_x = [g_i^{x_i} : i \in \{1, \ldots, n\}]\) and \(\vec{c}_y = [g_i^{y_i}: i \in \{1, \ldots, n\}]\).

The cloud providers can form a verifiable secret sharing of their sum \(z = x + y\) by:

• Adding their individual shares \(z_i = x_i + y_i\).
• Componentwise-multiplying \(\vec{c}_x\) and \(\vec{c}_y\) to form a new vector of commitments \(\vec{c}_z = [g_i^{x_i} g_i^{y_i} : i \in \{1, \ldots, n\}]\).

This works because the new commitment corresponding to \(z_i\) equals \(g_i^{x_i} \times g_i^{y_i} = g_i^{x_i + y_i}\), which is a valid Feldman commitment that will properly open and verify during the retrieval stage.

• So: we can retrieve \(z\) without ever learning the summands \(x\) and \(y\) individually!
• Secure multiplication of secrets is more complicated so I will not show it here, but it is possible. From this, we can do verifiably secure computation of everything!

By comparison, the Merkle tree looks nicer: the root \(h\) is independent of \(n\), and each individual proof \(\pi_i\) has size \(\log(n)\).

The good news is that it is possible to combine all of the commitments into a single element that has constant size, independent of both the message length and the number of providers!

• The idea is simple and again is based on the hardness of discrete logarithms.

• Rather than computing \(\vec{c} = [g_1^{x_1}, g_2^{x_2}, \ldots, g_n^{x_n}]\), we will instead compute a single commitment:

  \[\vec{c} = g_1^{x_1} \times g_2^{x_2} \times \cdots \times g_n^{x_n}.\]

This is called a vector commitment. The math of how to open such a commitment is not too difficult but beyond the scope of this course; it uses something called “bilinear maps.”

Relatedly: it is also possible to build a polynomial commitment, which means that you commit to a polynomial with something like \(c = g^{p(x)}\), and then can open the polynomial at a single point of your choice. This is useful when combined with the next comment…

Notice that these constructions have two different thresholds at play here, of how many cloud providers need to collude in order to break different guarantees:

• The privacy threshold \(t\) of cloud providers that would need to be malicious and colluding in order to reconstruct your secret data. (The protocol I showed today is based on additive secret sharing so \(t = n\), but it is possible to extend the techniques using polynomials to support an arbitrary \(t\).)

• The agreement threshold \(f\) of providers that need to be faulty in order to break Byzantine Broadcast.

Without a PKI, we know that \(f < n/3\). But the privacy threshold \(t\) can actually be larger than this.

• That is, we can protect the confidentiality of the data even in circumstances where the attacker controls enough parties that agreement breaks and we can no longer guarantee correct retrieval of the data.

• This is a subtle point, and the papers on verifiable secret sharing missed it for decades!

A dual-threshold verifiable secret sharing scheme supports \(t > f + 1\). The highest privacy threshold possible is \(t = n\). We constructed such a scheme today: the privacy threshold was \(t = n\) but the agreement threshold might be lower if we don’t have a PKI.

One could ask the same question in the asynchronous setting. That is, we could ask for asynchronous verifiable secret sharing. Constructing this primitive is more subtle than what we did today, for several reasons:

To my knowledge, the most efficient asynchronous verifiable secret sharing scheme is one that former BU PhD student Nicolas Alhaddad, former BU undergrad Ziling Yang, and I built last year. It’s also dual-threshold. If you’re interested, here is the paper containing all of the details: https://eprint.iacr.org/2024/326.pdf.