Multi-Party Computation: Answers

Let us think about the answers to the tutorial questions on Multi-Party Computation — the millionaire's problem.

Images sourced via Creative Commons and edited for Oxbridge Inspire

1. Yao initially proposed a solution for the two party case, his technique is called ‘Garbled Circuits’. Here, one party creates a circuit that can compute the function and scrambles it and passes it to the other party who evaluates it with their own inputs and the inputs of the other party that are also scrambled and sent over. The key part is that even evaluating the scrambled circuit produces the correct result of the function!
2. The main problem with MPC from a security perspective is having corrupted parties. Cryptographers can come up with a protocol that securely evaluates the function but the participants to the protocol may try to cheat, and not follow it exactly, in order find out the other parties’ inputs. This is the real challenge in creating a secure protocol!
3. Any situation where the input data is private. Consider private auctions, it is important that each parties’ input (their bid) remains private, otherwise other parties will have a big advantage. Also, consider the situation where the government want to use private data to solve some problem.

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.