A Crash Course on MPC, Part 8

Two-Party MPC with Active Security

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):

• The parties compute (locally) [d] = [u]-[a] and [e] = [v]-[b].
• The parties reconstruct d and e, turning them into publicly known values.
• The parties compute (again, locally, using the fact that linear operations can be handled without communication) [u*v] = d*[a]+e*[b]+[c]+d*e.

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:

• Alejandra and Bonifacio get w1 and w2 respectively such that w=w1+w2.
• Alejandra and Bonifacio get keys (α1, β1) and (α2, β2), respectively, where is entry is uniformly random.
• Alejandra and Bonifacio get the tags τ1=α2*w1+β2 and τ2=α1*w2+β1, respectively.

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:

1. Alejandra sends w1 and to τ1 Bonifacio, and Bonifacio sends τ2 and w2 to Alejandra. Since one of them may be corrupt these values may not be correct, so we denote them by w1', τ1', w2', τ2'.
2. Alejandra uses her key (α1, β1) to check that τ2'=α1*w2'+β1, and similarly Bonifacio uses his key (α2, β2) to check that τ1'=α2*w1'+β2. If these checks pass then the parties accept the reconstructed value w=w1'+w2'.

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:

1. Get a multiplication triple (<a>,<b>,<c>) and ignore last two components (alternatively, when generating this pair only generate the first part),
2. Bonifacio sends his share of <a>, together with the tag, to Alejandra, who checks that this share is correct. Now Alejandra knows a.
3. Alejandra sends (x-a) to Bonifacio,
4. Alejandra and Bonifacio define the shares of x to be <x>=<a>+(x-a). Notice that here the parties are adding a ‘constant’ (a value known to both) to a secret-shared value.

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

• [1] Bendlin, Rikke, et al. “Semi-homomorphic encryption and multiparty computation.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2011.
• [2] Damgård, Ivan, et al. “Practical covertly secure MPC for dishonest majority–or: breaking the SPDZ limits.” European Symposium on Research in Computer Security. Springer, Berlin, Heidelberg, 2013.
• [3] Damgård, Ivan, et al. “Multiparty computation from somewhat homomorphic encryption.” Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2012.
• [4] Keller, Marcel, Emmanuela Orsini, and Peter Scholl. “MASCOT: faster malicious arithmetic secure computation with oblivious transfer.” Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016.
• [5] Keller, Marcel, Valerio Pastro, and Dragos Rotaru. “Overdrive: Making SPDZ great again.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2018.
• [6] Baum, Carsten, Daniele Cozzo, and Nigel P. Smart. “Using TopGear in Overdrive: a more efficient ZKPoK for SPDZ.” International Conference on Selected Areas in Cryptography. Springer, Cham, 2019.