Post Office Problem
Dennis Shasha
Omniheurist Course
Computer Science
Description
You are given
-
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 indefinitely long
(the sender has no control over this).
-
Participants do not know when spy has visited a post office.
-
Participants may send many parts of the information at once.
A participant may also send a message of the form "I have received a message
from participant p".
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.
To see the original story,
click here
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.
Here is one (in tar format)
written by Ofer Gill in 2002.
You may find it helpful.