5
$\begingroup$

I was explaining MPC to a high school student. He was excited and asked me for some examples. The only ones that I could think of are by using garbled circuits. Are there some simple MPC protocols for operations such as addition, multiplication, exponentiation, max, min that I could easily explain to an high school student?

Edit: I got good responses for addition and average operations. Are there any simple protocols for other operations as well?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Whenever I try to explain MPC to non-CS people I have this example: Economics teacher wants to find out how many students have failed a math exam and the students would like to keep their math marks private. How do they solve the problem? Teacher sends a random number X to the first student - if the student failed they send X+1 to the next student, otherwise send X. This sheet of paper gets sent to every student and in the end the professor can compute the total amount of students who failed at math without knowing who failed the course. $\endgroup$
    – Dragos
    Apr 29, 2019 at 23:45
  • $\begingroup$ @Dragos could you turn this comment into an answer, too. $\endgroup$
    – kelalaka
    Apr 30, 2019 at 10:05
  • $\begingroup$ @Dragos The above protocol assumes users are semi-honest and there are no collusions. Is there a way to turn the above protocol to be secure against colluding users or malicious users? $\endgroup$
    – satya
    May 1, 2019 at 18:18
  • 2
    $\begingroup$ There's a classic protocol for secure two party AND using physical cards, and also several variants with fewer cards or other objects. See e.g. eprint.iacr.org/2015/1031 $\endgroup$
    – pscholl
    May 2, 2019 at 7:30

2 Answers 2

Reset to default
6
$\begingroup$

Here's a simple example for addition which can be extended to other operations as well.

Suppose there $X$ number of children in a classroom and everyone has a score ranging from 0 to 100. We want to calculate the average of the scores of all students without the teacher or the other students knowing what their classmates have scored.

Here's how we can achieve this.

Step 1 :

Make them each right down the score that they have got on a piece of paper and make sure no one is colluding. This only works if everyone does it honestly.

Step 2:

Tell each student to select $X$ numbers and write them down preferably on small bits of paper since there are $X$ number of students such that these numbers will add up to the score they want to keep secret. The range can be from $-∞$ to $+∞$.

Step 3 : Tell each student to distribute $ X-1$ bits to every other student so that each students ends up with $X$ bits in the end.

Step 4 : Now that each student has $X$ bits of paper , tell them to add up all numbers they have in front of them and write the value they got on the board.

Step 5: Add all these numbers and you will get average of the scores of each student.

You could calculate the average without anyone knowing what their score was.

You can cross verify by taking the average of the actual scores.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Is there a way to make this protocol maliciously secure? $\endgroup$
    – satya
    May 1, 2019 at 18:25
2
$\begingroup$

A fun one(and how I was introduced to MPC) could be to compute the average constipation rate of the class or something like that, where each student has a constipation rate between 0 and 100. This could be done using a sum protocol initialized with random value written on a piece of paper. The value is chosen by the teacher; upon receiving a paper, the student adds his/her value and write down the result on a new piece of paper and passes that along. In the end, you publish the average value. This would require students to play honestly.

It is also a way to also introduce real world(specification) vs ideal world paradigm.

The awkwardness of the process was hilarious when we did it.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.