One hundred students are competing for college scholarships. They come from 10 schools (10 students per school). From each school, one student has declared physics as a major; one has declared chemistry; one, biology; one, psychology; one, mathematics; one, economics; one, anthropology; one, linguistics; one, English; and one, history. So, the group has 10 students for each of these majors.

Each of three judges is going to rank the students in 10 ranks from best (rank 1) to worst (rank 10). That is, each judge is to assign ten 1s, ten 2s, and so on up to ten 10s. So, each judge will assign one rank per student.

In previous years, some of the losing students have alleged that the judges were biased, so we want to ensure two "fairness" constraints that will require some planning on the part of the judge. In the rankings done by each judge:

1. Each school will receive 10 different ranking scores.
2. Each major will receive 10 different ranking scores.

So, among the economics majors, for example, each judge should assign one 1, one 2, one 3, and so on up to one 10. Similarly, among the students from Pleasanttown High School, each judge should assign one 1, one 2, and so on up to one 10.

Each student's three scores (one from each judge) will be averaged.

Our problem is to ensure that each judge obeys the constraints but without our knowing how that judge voted. That is, out of respect for the privacy of the judging, we want to know for certain that the judges obeyed the constraints but nothing more.

To show you that this is at least conceivable, suppose we imagine a variant of Monty Hall's game show, Let's Make a Deal, using cards in which all of them are worth zero except one that is worth $10,000. The Master of Ceremonies begins the game by arranging the cards face down. The contestant could choose one, which the MC would turn over and then give the corresponding reward. If the contestant loses, he or she might then challenge the MC to see whether there is in fact one card that is worth $10,000. To prove this, the MC could take the cards, shuffle them in front of the contestant, and then reveal them. The net effect is that the MC has proved that he has not cheated. At the same time, he has not revealed the original position of the prize card.

Problem:
Imagine that each judge is given 100 opaque cards that hold the name, school and major of the student on one side and are blank on the other. Each judge also has 100 adhesives, ten identical 1s, ten identical 2s, and so on up to ten 10s. Can you design a protocol to ensure that each judge meets the constraints, but without allowing anyone to infer a judge's votes?

Answer

Thanks to Michael Rabin for this approach to demonstrating knowledge without revealing secrets. He used it to form a "zero-knowledge" proof for Sudoku.

Comments