Multi-Party Computation — the millionaire’s problem

This week we will look at an area of cryptography called Multi Party Computation (MPC).

Images sourced via Creative Commons and edited for Oxbridge Inspire

Consider the following situation: a group of millionaires are at lunch together, and once they finish they ask for the bill. They decide that the richest among them will pay the bill so they set about computing the function of who is the richest. There is a trivial way they could do this, where they all reveal how much money they have and compare their wealth. However, this solution to the problem is not satisfactory to them as they do not want each other to find out how wealthy they are.

This is exactly the problem of MPC — multiple parties wanting to compute a function where each party has an input to the function, with the added condition that the inputs remain private.

When was this idea first thought of?

The area of MPC was first introduced in 1982 by Andrew Yao with the ‘Millionaire’s problem’ that is given above. The challenge for cryptographers working in this area is to come up with protocols to compute functions privately, thus keeping all the parties, the millionaire’s in the above example, happy. The hard part being that we want to be able to compute arbitrary functions privately and not just come up with methods that tackle specific functions.

To start with cryptographers thought that this area of research was simply an intellectual curiosity, the example of millionaires at lunch seems like a fun example that does not hold that much real world importance. However, researchers began to come up with more and more efficient ways of achieving MPC and now it is beginning to become achievable in real world applications.

So where could this be used?

Consider a group of hospitals that each hold data about their patients. It is often mutually beneficial for them to combine their data in order to solve medical problems. However, often this is not allowed by law due to the private nature of the data (you probably would not be very happy if your GP decided it was going to give your medical records out to others who may be interested in them). This is again the exact problem MPC can be used to solve. We have many parties (the hospitals), who want to compute some function on their private data (the medical records).

Questions:

1. Can you find out how Yao proposed to solve the millionaire’s problem?
2. What security problems do you think may be associated with MPC and where are the risks?
3. Are you able to come up with some other examples of where MPC may be used?

This article was written by David Butler, one of the course creators and teachers at Oxbridge Inspire. David is studying for a PhD at the Alan Turing Institute in London.

If you enjoyed this article, you might consider coming to our course in Cambridge this summer on the Mathematics behind Cryptography.