Chapter 1: What is Multiparty Computation?

There's a reason that multiparty computation remains so obscure and esoteric among all but cryptographers. Example problems, when offered, are somewhat complex at best, or overtly so at worst; the most basic of protocols tend to be difficult to follow for the uninitiated; and the research itself tends to be on the most subtle differences between problems.

With that in mind, in this chapter we will examine three different multiparty computation problems (and some of their solutions) that offer the most intuitive look into the field, subtleties and all. We stress that this is intended to be an intuitive introduction to a few of the major issues in the field; more formal definitions are given in the next chapter.

The first, the Millionaire Problem, is a classic cryptography problem offered by Andrew Yao in his 1982 paper which helped to found the entire field of multiparty computation. It gives the perfect example of a two-party computation, complete with a short and easy-to-understand protocol, while also offering an easy demonstration of how dishonest parties can cheat each other in non-optimally private protocols.

The second, Secret Voting, is an extremely intuitive example with a large amount of research behind it. It expands the problem from two parties into many, and demonstrates the difficulties that come with that extended utility. It also allows us to look into the different subtleties that can come up in these types of problems, and how those different (seemingly minute) alterations in the problem can drastically alter the protocol.

The third, the Fourth Grader Problem, is a problem and protocol created here as a final intuitive example. It is the first time we will look at a protocol in which multiple functions are included, and we can contrast the problems created by cheating and those created by collusion, a special type of cheating.

With all of that behind us, we can look at a more technical definition of multiparty computation, and analyze the different variations built into that definition. While still not as formal as the one to be presented in the next chapter, it will give us a taste of the types of descriptions used on protocols throughout this website (especially in the research section) in order to describe what variations a particular protocol uses.

Section 1: The Millionaire Problem

Alice and Bob are millionaires. One day, they get to arguing, both insisting fervently that they are the richer of the two. Neither of them is willing to tell the other exactly how much money they have, though—that's far too private! Thankfully, they're both computer scientists (why did you think they were millionaires?), so they design a protocol by which they can determine which one is richer without having to tell the other too much information.

To formalize this problem a little bit, let's say that Alice has \(i\) million dollars, and Bob has \(j\) million. This is only an example, so we'll say that \(i,j\) are integers and \(1\leq i,j\leq 10\): Yao's protocol originally did the same, after all. Alice and Bob want to devise a scheme so that they both learn the value of \(f(i,j) = i<j\), but so that Bob does not learn \(i\) and Alice does not learn \(j\).

The Protocol

Let's look at (a rewording of) Yao's original protocol:

1. Alice and Bob agree on a number of bits to use for encryption, \(N\).
2. Alice creates a public/private-key pair. If you don't know what that means, check out the refresher page.
3. Bob picks an \(N\)-bit random number \(x\), and encrypts it under Alice's public key to get \(k\).
4. Bob sends Alice the number \(k−j+1\).
5. Alice adds the values \(0\) through \(9\) to this value, getting \(k-j+1 ... k-j+10\).
6. Alice decrypts each of these values under her private key, getting a list of random-looking numbers \(y_u\). The \(j\)-th, \(y_j\), is \(x\), but she can't determine which one that is.
7. Alice picks a random \(\frac{N}{2}\)-bit prime number \(p\).
8. Alice finds the remainder of each value of \(y_u\pmod{p}\), and calls this set \(z_u\).
9. Alice sends Bob eleven values: the first \(i\) values of \(z_u\) unchanged; the remaining values of \(z_u\) with 1 added to each one; and \(p\).
10. Bob calculates \(x\pmod{p}\).
11. Bob decides that, if the \(j\)-th number Alice sent is equal to \(x\pmod{p}\), \(i\geq j\). Otherwise, \(i<j\).
12. Bob tells Alice what the conclusion is.

It can be hard to visualize this protocol in action, so here's an interactive animation that will allow you to see it step by step:

Making Protocols Private

This protocol definitely gets Alice and Bob their answer, but does it satisfy that other requirement: that neither of them learns the other's variable? It's here that we can start talking about what 'privacy' really means.

One tempting option is to say that in order for the protocol to preserve Alice's privacy, Bob can't know what \(i\) is at the end of the protocol. Sadly, we can't quite define it this way.

Let's say, for example, that Bob just guesses, and decides that \(i=5\). If he happens to be correct, he's learned something, even if the protocol is secure. You may say he hasn't 'learned' anything, but what if this were her password, or her SSN? No matter how he arrived at his answer, if he's correct, he can still use it. That may seem semantic, but semantics are paramount here: they are what will allow us to turn the abstract idea of 'privacy' into a concrete, mathematical primitive. So what if we specify that Bob can't know what \(i\) is, but using only information he got from the protocol?

That doesn't really work either. Let's say that Bob truly, TRULY wants to know how much money Alice has, so he tries every number until he finds the ones that Alice got from the decryptions of \(k-j+1\dots k-j+10\). If he does that, it's very easy to figure out \(i\): he just needs to see which ones she added 1 to! The barrier here is that such a calculation could take Bob years, decades, centuries if they chose a good enough encryption. So we need to add in some concept of what Bob could reasonably do. Otherwise, if you give someone an infinite amount of time, they will crack any code.

In cryptography, we tend to talk about 'reasonableness' in terms of polynomial time (sometimes P-time, though in this website we will almost always write "polynomial"). In general, if the amount of time spent breaking a protocol is in \(O(n^k)\) for any constant \(k\), we can say that something private might be learned by the wrong party. On the other hand, if the amount of time spent would be in \(O(b^n)\) for a constant \(b\), we can feel safe calling it unreasonable that it can be brute-forced. In this case, the amount of time spent is in \(O(2^N)\) where \(N\) is the number of bits in \(i\), so it's unreasonable that Bob would brute force it.

As a short aside, let's note that Bob still technically could learn something in a 'reasonable' amount of time, no matter how hard a problem is. The chance is minute, but he may end up guessing the correct answer, even on his first try. This is where cryptography focuses on the idea of negligible probabilities. Just like how we called polynomial time 'reasonable,' negligible probabilities are so unreasonably tiny that we don't worry about it—and, accordingly, negligible functions are any functions which can be bounded from above by an inverse polynomial.

So we specify that Bob can't learn \(i\) using information from the protocol in a reasonable amount of time. Even so, we aren't quite done. Let's say that Bob started with the value \(j=9\), Alice and Bob do Yao's protocol, and Bob learns that \(i>j\). Bob knows that, according to the initial conditions of the protocol, \(1\leq i\leq 10\), so \(i\) must be equal to 10!

Yet again, we're missing something in our definition. We need to specify that anything that could be learned from the final function value does not count as information that can be called private. If we want to talk about multiparty privacy, we should say that Bob can't learn anything extra about Alice's information other than what he could have already learned from \(j\) and \(f(i,j)\), all in a reasonable amount of time.

The above concept goes by many names in the research, because researchers love nothing more than to play with definitions in order to see what changes. If a protocol fits the definition above, it may be said to preserve optimum privacy; if it does not, it is usually not called anything at all, because it is probably being used as a stepping stone towards a different protocol that does. If Bob is attempting to breach that privacy, he may be called a passive adversary, making a protocol that defeats him resistant to passive adversaries. For more information on adversaries, see the next chapter.

Cheating

That's all well and good then, as long as Alice and Bob agree to follow the protocol exactly as it's written. Alice doesn't know which value Bob will be able to interpret since he picked \(x\) randomly, and Bob would have to spend an unreasonable amount of time to figure out how to decrypt all ten values \(k-j+1\dots k-j+10\).

But what if Bob gets to the end of the protocol and has gotten the answer that \(i>j\), but he's unhappy enough about that to lie? The next step is for him to tell Alice what he's learned, so he can just tell her that \(i\leq j\) and she'll never know (and will presumably be forever cowed by his enormous bankroll)!

This is what we call cheating, and we would call Bob dishonest, a cheater, or, sometimes, a malicious adversary. Cheating is one of the most difficult things for protocols to deal with because, in order for a protocol to be useful practically, we need to ensure that honest parties (non-cheaters) will catch the cheaters. Since there are always flukes and dumb luck, we generally say that cheaters should only succeed in cheating—that is, convince any honest party that they weren't cheating—with negligible probability.

Using the word dishonesty does cause a small amount of confusion, however, because we have to draw the difference between Bob lying and Bob being dishonest. It is absolutely impossible for a protocol to alert honest parties that Bob is being dishonest if he is simply lying about his value of \(j\) from the very beginning. There is absolutely nothing preventing Bob from lying to Alice by having only 3 million dollars in the bank, but running the protocol with \(j=6\) in order to (hopefully) impress her.

Dishonesty in this context could mean a few different things. If Bob uses \(j=5\) up to step 5 above, then switches to \(j=8\) afterwards, that is dishonesty, even if he's technically 'following the rules' of the protocol. If Bob were to lie in the final step in order to convince Alice that the opposite result was true, as we mentioned above, that would also clearly be dishonest.

A protocol which prevents any cheating would not allow any of these to occur: it would put the most strict constraints on itself, and would generally say that no malicious adversary can convince any honest party that the protocol was done correctly. Obviously, Yao's protocol does not stand up to this: Bob could switch \(j\)'s and Alice wouldn't notice.

But both of those examples represents a different type of cheating that a protocol can defend against. Bob switching \(j\)'s is a case of a malicious adversary not using their input consistently; if Bob didn't even use a \(j\) at all and simply used a random number throughout, that would be another case of this type of dishonesty. Bob lying in the final step represents a type of malicious adversary that any practical protocol should definitely defend against: a malicious adversary being able to alter the outcome of the computation to a value of their choosing.

Generally, an insecure protocol (one that is not built against cheating) cannot prevent either. But a protocol may also only defend against the latter type, which would allow cheaters to act abnormally without being caught, but to be unable to turn the outcome of the protocol to their particular advantage.

Section 2: Secret Voting

We move on to a usage case that may seem more familiar: a secret ballot. Secret voting can get quite complicated, but we will give the simplest of examples. Let's say we have \(n\) people in a room, and they want to choose between two options, which we will call option 0 and option 1. As a democratic bunch, the group of participants want to define a way that they can choose between the options fairly, but privately. After a discussion amongst themselves, they decide that these are the (basic) constraints they want on their vote:

• If a majority of the group wants option \(b\in\{0,1\}\), then that is the option the vote will result in. This is a correctness constraint. For simplicity, we will assume that \(n\) is odd so there will always be a majority voting for one option.
• Nobody can vote more than once, or otherwise change the result of the vote. This is another correctness constraint.
• Nobody's vote is public; that is, nobody can tell how anybody else voted. This is a privacy constraint.
• Nobody can vote out of spite. This property is subtle, and refers to independence of inputs: it's not fair for someone to base their vote on somebody else's vote, or they could simply be cancelling a vote out. As another example, independence of inputs is extremely important in a private auction, or else someone could always win the highest bid by one dollar.
• Everyone finds out what the result was at (approximately) the same time. This is a fairness constraint: if we don't account for this, then we could prevent the protocol from finishing correctly. As an example, if the first person to get the result doesn't like that result, it is unfair for that person to be able to stop participating and prevent others from receiving the answer.

Section 3: The Fourth Grader Problem

We wish to give one final example that we think is the most intuitive of all. A classroom of students ("fourth graders") all have 'crushes' on one other student each; they all want to know if their crush likes them back. This, of course, is not easy: if they admit to liking their crush, but the crush is not requited, they would find that extremely embarrassing. As such, we must find a way to ensure that:

• All fourth graders learn if their crush is requited (correctness).
• No fourth grader learns about anybody's crush, excepting the case where their own crush is requited (privacy).
• No fourth grader A, who has a crush on B, can be convinced by B that A's crush is requited unless B had a crush on A before the protocol started (independence of input).
• No fourth grader can learn whether their crush is requited unless the other fourth graders also learned whether their crushes were requited (fairness).

We assume the fourth graders are numbered \(i=\{1,\dots,n\}\) and that each has input \(x_i\in\{1,\dots,n\}\backslash\{i\}\cup\{\varnothing\}\), where we say \(\{\varnothing\}\) is the equivalent of not having a crush. So we define our protocol as follows:

1. The fourth graders all agree on some public-key encryption scheme (e.g. RSA, DH) \(\mathcal G,E,D\), as well as a security parameter \(k\). We restrict ourselves to encryption schemes where the public keys are indistinguishable from random.
2. All fourth graders sample two key pairs: party \(p_i\) samples \((pk_i,sk_i)\leftarrow\mathcal G(1^k)\) and \((\pi{k_i},\sigma{k_i})\leftarrow\mathcal G(1^k)\).
3. All fourth graders write their \(pk_i\) on the white board, keeping their other values private.
4. All fourth graders \(p_i\) encrypt their second public key \(\pi{k}_i\) under their crush's public key, and call this value \(e_i=\mathcal E(pk_{x_i},\pi{k}_i)\). Any student with no crush encrypts a value chosen uniformly at random and sets \(e_i\) to this encryption. All parties write \(e_i\) on the white board.
5. All fourth graders \(p_i\) decrypt their crush's \(e_i\) under their primary secret key \(s_k\), to get \(d_i=\mathcal D(s_k,e_i)\). We note that, if their crush is requited, then \(d_i=\pi{k_{x_i}}\); otherwise, \(d_i\) is random.
6. All fourth graders encrypt their input \(x_i\) under \(d_i\), calling this \(c_i=\mathcal E(d_i,x_i)\); anyone without a crush can encrypt a value at random, or set \(c_i\) to a random value, as they prefer. Everyone writes their \(c_i\) on the board.
7. All fourth graders check whether \(\mathcal D(\sigma{k_i},c_{x_i})=i\); if so, their crush is requited.

Section 4: Defining Multiparty Computation

A set of \(m\) people \(P\) are trying to communicate with each other to evaluate the values of some set of up to \(m\) functions \(F\). Each person \(P_i\) is in possession of some private variable \(x_i\). When the communication is done, each person \(P_i\) wants to know the value of \(F_i(x_1,x_2,x_3,\cdots,x_m)\). The security constraints and privacy constraints under which everyone is operating change problem to problem. Generally, however, every person in \(P\) wants their privacy maintained, in that, they want no other person in P to learn the value of their private variable \(x_i\). Additionally, the protocol may guarantee some security: no people not in \(P\)—or adversaries—to learn anything at all, or to be able to alter the evaluation of any of their functions.