Post Office Enhancement

I think the post office problem does not receive any help from the ability to send out any message you have previously been sent, as opposed to just your own.

If you give me a protocol P using the enhancement, I claim that I can produce a protocol P' which does not but is just as good. By just as good I mean P' is still secure and takes no longer in the 1-day-per-send case.

I'll try to prove this. Start with protocol P which uses the enhancement. I think it is reasonable to assume that P is secure and has no cycles. A cycle is a dependency chain of message events which loops back on itself. I also will assume P has no multiple-triggers. This means that for any message-event in the protocol, there is only one on-events clause which can cause it. If there is more than one trigger, just eliminate all but the first one -- the one which acts as the actual trigger in the 1-day-per-send case. This certainly does not slow down the protocol. Also, it cannot make it less safe since it was safe before, and now message events are only more strict than they were before.

Use induction on n, the number of days in the 1-day-per-send case. Base case: suppose P only takes 1 day (optimally). Then it is impossible that the enhancement is being used, since if it were, some person would have to be sending a message indirectly, which cannot occur on the first day. Thus we can let P' = P.

Now suppose we know the hypothesis to be true through n-1 days. The new protocol (using enhancement) P takes n days. Here is the idea. We will change P a little and split it up into two groups: P1 and P2, where any message m is sent in either P1 or P2 but never both, and P2 represents all the activity of the last day in the 1-day-per-send case. Then we use the inductive hypothesis on P1 (which takes only n-1 days) to arrive at P1' which does not use the enhancement, and just stick P2 onto the end of it to get P', which is just as fast and does not use the enhancement. We know P2 doesn't use the enhancement since it is only a one-day protocol, and every message being sent in it has never been sent before, so the only person who can send message m is the original owner of that message.

We just have to see how to split P into P1 and P2 now. We'll do this by going through all the messages, and make sure they are split between the first n-1 days and the last day. That is, if message m is sent in the last day, it is never sent before, and if it is ever sent before, then is is not sent during the last day.

Suppose m is split between the two sections (first n-1 vs. last day). If m is sent only once during the first section, take out that send and move it to the last day.