Post Office Problem
You are given
You are to create a protocol that any person
can initialize by sending a message.
You will be judged first by whether it is secure whether or not
some letters arrive late.
Second, by how many days it will take if no letters arrive late.
A collection of N people who together know some plan
(each person knows 1/Nth of the plan)
The goal is for every person to learn all the plan
without letting the spy know.
A spy who will know the plan if he knows the part
held by a fraction f
of the people.
A collection of post offices through which each person can send letters
(and the person can specify through which post office to send it)
A number indicating how many post office visits the spy can make
(a visit to post office A and B counts as two visits)
Letters arrive in a day usually but may take up to five days
Participants know when spy has visited a post office and which one,
but only on the day that the spy does the visits.
[The class of 2002 has decided not to use this.]
Participants may send many parts of the information at once
[In second week, this holds. So you may use this.]
The architecture group will write a verifier that will take
the above parameters and the protocol (in a format to be specified
by the architecture group) and will test to see whether the spy
could acquire the fraction f of the plan.
Note that the spy knows the protocol in advance and knows where
every letter is but cannot look inside the envelopes unless
he is at the postoffice.
In that case, he may not change the letters or their destinations
or even delay them.
The plan members may make their protocol conditional on when
a spy visits.
Here is one (in tar format)
written by Ofer Gill in 2002.