A Crash Course on MPC, Part 8

Two-Party MPC with Active Security

Daniel Escudero
Mar 8 · 15 min read
Traditional plates from El Carmen de Viboral, Colombia

In lecture 2 we studied a basic secure computation protocol by which two parties, Alejandra and Bonifacio, can compute any function of two private inputs x and y while revealing only its output. This was done by using additive secret-sharing, which is a method by which a secret value can be distributed among the two parties in such a way that no individual party knows anything about the secret, but the two parties together can completely determine its value.

The protocol worked as follows, superficially. The function to be computed is assumed to be composed of additions and multiplications only. The parties begin by distributing shares to each other of their inputs, and then they proceed “operation-by-operation”, obtaining shares of each intermediate result, until they reach the final output. Addition operations are easy to handle, and in fact they can be done without interaction, but multiplications require certain subprotocol to be processed. The approach that was proposed back in lecture 2 to handle multiplications consisted of assuming certain correlated shared data, called multiplication triples, that were used to make the multiplication of shared values much easier.

The protocol from lecture 2 is only passively secure, a fact that was left as an exercise back then. The goal of this post is to extend this protocol from passive to active security. Recall that, what this means, is that now the corrupt party (either Alejandra or Bonifacio) will be allowed to misbehave arbitrarily, and the protocol should still preserve the privacy of the input from the other party. To achieve this, we follow roughly the same design as the previous passively secure protocol, assuming certain preprocessing data is available “for free”, and focusing only in the online phase. We begin with a quick recap of how the passively secure protocol works below.

Recap of the Passively Secure Protocol

Let’s use a similar example as in lecture 2. Alejandra has a number x and Bonifacio has another number y, and they want to compute the function given by z = f(x, y) = (x-y)*(x+y) mod M, for certain integer M. In order to execute this computation securely the parties resort to additive secret-sharing: To ‘hide’ a given value w lying in the range 0,…,M-1, Alejandra gets w1 and Bob gets w2, also in the same range, such that w=w1+w2 mod M. If w1 is chosen uniformly at random, then one can easily show that w2 will also look uniformly random (regardless of the value of w), so, on their own, Alejandra and Bob don’t know anything about the value w from their shares w1 and w2. We denote the ‘fact’ that w is secret-shared as described above by [w].

The protocol starts by Alejandra and Bob each secret-sharing their inputs towards the other party. At this point, the parties hold shares of the inputs [x] and [y]. What follows in the protocol is to devise methods to compute [u] and [v], where u=x+y and v=x-y (everything happens modulo M, and I will mostly omit this in the notation from now on), and then [z] where z=u*v. Computing [u] and [v] is easy using the linearity of the secret-sharing scheme: the parties simply add/subtract their shares of [x] and [y] to obtain [u] and [v], respectively.

The computation of [z] is a bit more complicated. For this, Alejandra and Bonifacio rely on the so-called multiplication triples, which are triples of the form ([a],[b],[c]) where a and b are random and c=a*b. Let’s assume the parties get these shares somehow, either by running some complex protocol between them (that we won’t get into), or some external party provided these to them. Either way, these triples are used to compute [z] from [u] and [v] as follows (taken verbatim from lecture 2):

Once the shares [z] are computed, the parties can get the result of the computation by sending to each other these shares, and adding them together to reconstruct the result z.

Problems when the adversary is actively corrupt

As mentioned before, the protocol above breaks if the corrupt party suddenly starts misbehaving. To see why this is the case, let’s focus for example on the final phase of the protocol: the reconstruction of [z]. Imagine that the shares are z1 (held by Alejandra) and z2 (held by Bonifacio), and suppose that Alejandra is the corrupt party. At reconstruction time, Alejandra should send Bonifacio her share, z1, but since she can misbehave arbitrarily, nothing prevents her from sending, instead of z1, some other value z1', which for notational convenience we write as z1+δ, where δ=z1'-z1. Bonifacio, who is clueless that Alejandra is cheating, uses z1', together with his share z2, to reconstruct the output as z1'+z2=(z1+z2)+δ. The correct output is z=z1+z2, but instead, Bonifacio is obtaining z+δ. This is clearly a security problem.

The issue highlighted above does not only appear in the final phase of the protocol. In general, this problem arises whenever a secret-shared value needs to be reconstructed, which happens in the output phase but also when computing the multiplication [u*v] using the multiplication triples, since there the secret-shared values [d] and [e] must be opened.

At this point it is useful to contrast this with the actively secure protocols we have studied already in the previous two lectures. These protocols, such as the one we are considering here, also relied in some form of secret-sharing (Shamir secret-sharing in that case), and also required reconstructing secret-shared values. However, in that setting, an active adversary was not able to change the shares of the corrupt parties in such a way that the reconstruction of the secret resulted in a different value, which is the problem we are having in our current context.

The reason for this has to do with the concept of error detection (and correction), explained in lecture 5: In the honest majority setting using Shamir secret-sharing, there is enough “redundancy” in the sharings, and the adversary cannot successfully fool the honest parties into reconstructing an incorrect value without breaking this underlying structure. On the other hand, in the secret-sharing scheme Alejandra and Bonifacio are using here, there is no redundancy at all: any pair (w1,w2) can be seen as valid shares of the value w=w1+w2.

Achieving Active Security

Our task now is to find a solution to the problem of opening secret-shared values in such a way that an actively corrupt party cannot change the value of the reconstructed secret. As hinted above, the main source of this attack vector lies in the lack of redundancy in the basic additive secret-sharing scheme the parties have been using so far, so the way we will approach the problem is precisely by adding some extra redundancy on top of the current scheme, that allows the parties to detect cheating attempts when reconstructing secret-shared values.

This redundancy comes in the form of MACs, short for Message Authentication Codes. In the symmetric-cryptography setting, a message authentication code refers to a cryptographic construction used to provide integrity, allowing a party to verify the ‘correctness’ of some given data via some secret key and some extra information attached to this data. Conceptually, such a primitive could prove useful in our setting, where we want to ensure that the shares sent by Alejandra to Bonifacio and back are “correct”.

Unfortunately, we cannot simply plug directly a MAC scheme into our secret-sharing scheme and hope it will fix all of our problems, since we still need to take care of other aspects, like keeping “linearity”, for example. However, the high level idea of giving Bonifacio some piece of secret information that he can use to check the correctness of Alejandra’s shares is the key to the techniques we will discuss below to achieve active security, and, for historical reasNotice that here the parties are adding a ‘constant’ (a value known to both) to a secret-shared value.ons, these are also called MACs, although they don’t quite follow the syntax of usual secret-key MACs.

Adding redundancy to Alejandra’s share

Assume that Alejandra and Bonifacio have shares w1 and w2 of a value w. The goal is to provide Bonifacio with some secret information that he can use so that, when Alejandra sends her share w1', he can check that w1'=w1 (of course, we would also need to endow Alejandra with similar information so that she can verify the correctness of Bob’s share, but for illustration purposes we will not consider this case yet). The scheme we will use works as follows: Bonifacio gets the key (α, β), where α and β are random numbers (in the right interval 0,…,M-1, which I have missed to write in several places, deliberately), and the extra information that Alejandra gets is τ=α*w1+β. Observe that this τ doesn’t reveal Alejandra anything about α since the product α*w1 is being maked by β.

At reconstruction time, Alejandra will not only send her share w1 to Bonifacio, but she will also send the extra information τ=α*w1+β. Notice that, if Alejandra is corrupt, she may send incorrect w1' and τ’. To verify that w1'=w1, Bonifacio uses his secret key (α, β) to compute α*w1'+β, and checks that this is equal to the τ’ provided by Alejandra. If this is the case, Bonifacio concludes that w1'=w1, and if the check doesn’t pass he concludes that w1' is incorrect.

It should be easy to see that if Alejandra sends the right w1, together with the right τ, then the check that Bonifacio performs will pass. The challenge lies in showing that if w1' is not equal to w1, then the check will fail. Unfortunately, this is not 100% guaranteed, as there is always a way for Alejandra to cheat: she can try to guess α, which, with the help of the τ=α*w1+β she knows, can lead her to learn β. If her guess is correct, she can compute τ’ as τ’=α*w1'+β, and in that case, the check that Bonifacio performs will surely pass. This shows that the key (α, β) has to be hard to guess, which in turns implies that M, the modulus, which defines the range over which the key is chosen, has to be very large.

Unfortunately, choosing a large M is not enough to ensure that the check fails (with high probability) whenever w1' is not equal to w1. Imagine that M=2⁶⁴, which is reasonably large so that Alejandra cannot guess the key easily. For notational convenience let us write w1'=w1+δ and τ’=τ+γ, where τ=α*w1+β. The check that Bonifacio performs is whether α*w1'+β, and checks that this is equal to τ’. With the notation introduced above, this translates into checking that α*δ-γ=0. Recall that all of this happens modulo M, so modulo 2⁶⁴ in our case. Now, Alejandra chooses δ to be 2⁶³ and γ=0 (so the share sent by her is equal to the correct share plus 2⁶³, and she does send the correct τ), which means that the check passes if and only if α*2⁶³=0 mod 2⁶⁴. How can this equation be satisfied? It is easy to see that this holds if and only if α is even, which is pretty bad as this happens with probability 1/2. We see then that by sending appropriate incorrect shares, Alejandra can fool Bonifacio into believing that this share is correct 50% of the time, too large to be acceptable.

The good news is that the issue from above completely disappears if we choose M to be a (large) prime number p, which was clearly not the case in the example we considered before. The reason why this works is simple. Using the notation from above, Alejandra sends w1'=w1+δ and τ’=τ+γ, and we want to ensure that if the check passes, that is, if α*δ=γ, then w1'=w1, at least with high probability. This amounts to showing that δ=0. To see this we show the contrapositive, that is, if δ is non-zero, then the probability that α*δ equals γ is very small. Notice that if α*δ=γ mod p and simultaneously δ is non-zero, we can multiply at both sides of this equation by the inverse of δ modulo p, denoted by δ^-1, which satisfies δ*δ^-1=1 mod p and exists since δ is not zero modulo p and p is a prime, to obtain α=γ*δ^-1 mod p. Since Alejandra chose γ and δ, the equation above shows that she would have learned α. All in all, we see that not only Alejandra can cheat by guessing α, this is in fact the only way for her to cheat, which happens with low probability if p is large enough.

Authenticated secret-sharing

To write in a more concise way what we have seen so far, we extend the basic additive secret-sharing scheme we have used for a while as follows. To secret-share a value w (defined modulo a prime p), the parties receive the following information:

It is customary to say that the shares that the parties have are authenticated. When a value w is secret-shared as above we write <w> (in contrast to [w], which used to denote the basic additive sharing). To reconstruct this shared value, the parties proceed as follows:

This new way of distributing secrets ensures that no party can successfully cheat (with high probability) when reconstructing a value, which fixes the main problem we had with the basic protocol when the adversary was active. Furthermore, this scheme is “linear” in the sense that parties can add shared values together to obtain shares of the sum. This only requires the “α part” of the keys of both parties to be the same for both shared values that the parties want to add, and the “β part” of the result will correspond to the sum of the “β parts” of each shared value.

I don’t want to get into much more details regarding how this addition operation works, since it may be a bit heavy in terms of notation, which is a bit annoying to handle in Medium. I hope the idea is clear though: with this new secret-sharing scheme the parties can still locally add/subtract secret-shared values, which is what we need in order to handle addition (and subtraction) operations, as well as multiplications assuming the existence of multiplication triples (<a>,<b>,<c=a*b>).

Modifying the input phase

With the tools that have been developed so far you should be able to build an MPC protocol to securely compute additions and multiplications. As discussed towards the end of lecture 2, this is in principle enough to compute any functionality. The protocol would work by the parties secret-sharing their inputs using the new secret-sharing scheme developed above, and then handling every addition operation locally by adding their shares, and multiplications by using preprocessed triples. The only missing step (besides how to precompute these multiplication triples, which I’ll get to towards the end of the post) lies in the input phase: how can the parties distribute authenticated shares of their inputs?

With the old secret-sharing scheme, simple additive secret-sharing, this was quite trivial: Alejandra knows her input x, so to secret-share it she doesn’t really need to do anything! If Alejandra defines her share to be x1=x and Bonifacio defines his to be x2=0, we see they automatically get additive shares of x since these satisfy x=x1+x2. Unfortunately, this is not so easy with the new authenticated shares. This comes from the fact that Bonifacio needs to get a key (α2, β2) that Alejandra cannot know, but Alejandra has to get some information related to this key, namely, the tag τ1=α2*x1+β2 (of course, there is also a symmetric issue with Bonifacio’s share).

This issue can be handled in a similar way as the input phase in the protocol from lecture 6. There, the secret-sharing scheme was Shamir’s, which suffers from a similar issue: the shares are quite “structured” and cannot be distributed by a single party easily while guaranteeing that the sharing is done correctly. The solution for Alejandra to share her input x is the following:

Extension to n Parties

The solution above was proposed in [1]. This can be extended to more than two parties as follows: if the participants are P1,…,Pn, then each party Pi will have a key (αi, βi), and each party Pj will hold a tag of its share under this key, that is, τj=αi*xj+βi. The problem is that each party now has to hold n tags, one for each other party.

A different approach that keys the information each party has to hold to a constant was proposed in [2]. The idea, in brief terms, is to let the parties have normal (i.e. unauthenticated) additive shares of the secret [x], but on top of that, they will have shares of a random value [α], together with [α*x]. The authenticated sharing of x becomes <x>=([x], [α*x], [α]). Observe that these sharings are much smaller since each party only needs to save shares of three values. In particular, the share size does not grow with n.

Now we turn to linearity. The value of α is “global” in the sense that it is the same for all the secret-shared values in the computation. If the parties want to add two authenticated shared values <x>=([x], [α*x], [α]) and <y>=([y], [α*y], [y]), the parties simply compute locally <x>=([x+y], [α*(x+y)], [α]), so the scheme is linear. The only missing step then would be to deal with openings.

To reconstruct an authenticated shared value <x>=([x], [α*x], [α]), the parties first reconstruct x’ from [x] (observe that x’ could be different to x if the corrupt parties cheat), and then they compute locally [z]=x’*[α]-[α*x]. Then, the parties open [z] to z’, and check that z’=0. If this is the case, then the parties conclude that x’=x, and else they abort. I left it as an exercise to the reader to verify that this works, that is, if z’=0 then it is because x’=x, at least with high probability.

A Word or Two About the Preprocessing

I would like to end this lengthy post with some comments regarding preprocessing. The topic of this post was dishonest-majority computation with active security, assuming all necessary preprocessing material was given for free. In particular, we assume the existence of authenticated triples (<a>, <b>, <c=a*b>). Generating these is not trivial, and, in fact, has been the focus of essentially all of the works during the last decade in the context of dishonest majority computation.

The BeDOZa protocol [1] proposes to use semi-homomorphic encryption (encryption that allows addition of ciphertexts) to obtain these triples, while the SPDZ protocol, first described in [3] and then refined in [2], proposes the use of somewhat homomorphic encryption (encryption that enables addition of ciphertexts as well as a few — only one is needed — multiplications). This was later on improved in the MASCOT protocol [4] by using oblivious transfer instead of homomorphic encryption, although in Overdrive [5] the homomorphic encryption approach was revisited and improved, which yields even more performant preprocessing.

The main bottleneck of the approaches based on homorphic encryption is that certain zero-knowledge proofs are needed in order to ensure that active adversaries behave correctly. It is fine if you don’t know what these are, but the point is that they add considerable overhead to the complexities that are already present when working with homomorphic encryption. These zero-knowledge proofs have been improved in TopGear [6].

I hope I get the chance to eventually blog about instantiating the preprocessing phase using perhaps some of the protocols mentioned above, but it is not on the table at the moment, unfortunately. However, my hope is that the contents of this post help you understand how actively secure dishonest majority protocols work, except for the generation of the preprocessing. This is already useful on its own since, for example, the preprocessing could be generated by an external trusted party, which is much better than trusting such party to perform the whole computation on the private inputs.

References

The Sugar Beet: Applied MPC

Developments in secure computation

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store