Post Office Problem

Dennis Shasha

Omniheurist Course

Computer Science



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.

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.