Improved remailer reordering

One simple way this can work is by batching messages up.  This could be
done by running the remailer at regular intervals, choosing the intervals
so that you tend to have enough messages on hand based on average arrival
times.  But a simpler way is to simply wait until you have N messages on
hand, then to promptly mix them up and send them out.  This way you have
a predictable number of messages to mix each time.  Note that in a system
like this you might as well send them all out as soon as the Nth message
comes in; there is no point in holding on to them for any extra time as
it adds latency without improving mixing.

The interesting thing I came up with is that there is a simple modification
to this batching scheme which gives better mixing with less average latency.
To describe it I need some mathematics.

One way to measure the benefit of a given degree of message-mixing is by
looking at the uncertainty of position of a given message coming in and
going out.  If we had batches of 4, for example, a given message coming
in has its position known with certainty.  Going out, it may be any one of
four messages, and the probability of it being any one of them is 1/4.

A measure that is used for situations like this is entropy.  It is defined
as the negative of the sum of the product of each probability times its
log.  (I will use log to the base 2 for the calculations for simplicity.)
That is, E = - sum pi * log pi.

For the incoming message, we have just {1} as the probability distribution.
We know exactly where it is and the probability is 1 that it is there.
For the outgoing we have {1/4,1/4,1/4,1/4} as the distribution.  It may
be any of these four messages with equal probability.  Applying the entropy
formula to these we get E=0 for the incoming, and E=2 for the outgoing.
If we had batches of 8 instead the distribution would have been {1/8,1/8,
1/8,1/8,1/8,1/8,1/8,1/8}, for E=3.  Note that entropy is a log measure
like the Richter scale.  An increase from 2 to 3 is just as big as an
increase from 1 to 2.

To consider different batching strategies, consider a remailer where the
messages come in one per hour, at 1:00, 2:00, 3:00, etc.  A four-fold
batching strategy would save up messages until there were four, then
randomly reshuffle them and send them out.  For this case we'd wait until
the 4:00 message, then shuffle numbers 1,2,3,4 and send them out, say,
at 4:01, in some random order, maybe 2,1,4,3. Then we'd save up more
until 8:01 at which time we might send out 7,5,8,6.  Note first that there
is no point in waiting till after 4:01; once we have the four messages we
might as well go.  Note too that the average latency for messages in this
system is 1.5 hours (the four messages have latencies of 0,1,2 and 3 hours).

Four-fold batching produces entropy E of 2 and average latency L of 1.5
hours.  Three-fold batching has E=1.58 and L=1; two-fold batching has
E=1 and L=.5.  Generally, N-fold batching has E=log base 2 of N, L=(N-1)/2.

Okay, with this background, we can consider the alternative which gives
improvement.  It is to have some "rollover" of messages.  Instead of sending
all of the messages in a batch out, you retain some of them and use them
to start the next batch.  I call an (M,N) rollover system one which uses
batches of M messages but retains N as rollover, sending M-N out each time.
By this definition the four-fold latency system above could be called a
(4,0) rollover where the 0 means we don't roll any over and send them all
out.
The simplest rollover case is (2,1). This uses batches of 2 messages,
where you choose one at random to send out and keep one. Then when the
next message arrives you again choose at random between the new one and
the old one, send that out, and keep the other.
In the timing example above, suppose we have the message from 1:00. Then
at 2:00 when that message arrives, we pick one of the two messages at
random and send it out. Suppose it is number 2. We retain number 1 until
3:00. Then we choose at random between 1 and 3. Maybe we pick 1 this
time. We keep 3 until 4:00, then choose at random between 3 and 4, and
so on.
Each message has a 1/2 chance of being sent out immediately, a 1/4 chance
of being sent out after 1 hour, a 1/8 chance of going out after 2 hours,
a 1/16 chance of going out after 3 hours, and so on. This means that the
outgoing probability distribution is {1/2,1/4,1/8,1/16,...}. The entropy
of this probability distribution is 1/2+2/4+3/8+4/16+5/32+6/64+... from
the formula above, which works out to be 2. The average latency is
0+1/4+2/8+3/16+4/32+5/64+..., which works out to be 1.
So, (2,1) rollover batching produces E=2 and L=1. This is the same entropy
as (4,0) batching with less average latency. Alternatively, it is more
entropy than (3,0) batching with the same average latency. It also has
the advantage that you never have to hold more than two messages, compared
with three or four for the alternatives. So this scheme has several ad-
vantages over simple batching.
Now, it does have one disadvantage, which is that there is no upper bound
on the latency of a message. With the (4,0) batching you may have had
more latency, but you at least know that nothing would have more than 3
message-times. With (2,1) there is a small chance of having very large
latencies. In fairness, though, it should be pointed out that in a real
system messages arrive at irregular intervals rather than the clockwork
model I used above, so even (4,0) would have random latency ceilings. Also,
it might be possible to modify (2,1) so that messages never waited more than
some maximum number of hours without seriously hurting the entropy.
I haven't tried working out the details of other rollover methods, but I
suspect that this will be a general method of improving entropy at little
cost in latency.  In real life we would want large entropies but starting
with a (10,0) I'll bet many rollover systems would be superior.
Hal

About message mixing:

   A measure that is used for situations like this is entropy.  

Indeed.  This is exactly the mathematical measure for what I've called
"privacy diffusion" in a remailer network.  It is, namely a measure of
of the uncertainty to a watcher of what ingoing message corresponds to
what outgoing message.

As soon as you begin to write down some of the equations for this
value, several things become distinct possibilities:

-- duplicate messages may decrease security
-- retries may reduce security
-- interactive protocols may reduce security
-- there is such a thing as a needlessly lengthy remailer path
-- noise messages might not be worth the bother
-- multiple different routes may reduce security

One thing becomes blaringly obvious:

-- it's reordering that's mathematically significant; that's what goes
directly into the equations.


   To consider different batching strategies, consider a remailer where the
   messages come in one per hour, at 1:00, 2:00, 3:00, etc.  

Since the particulars of the time don't matter for this analysis, I'd
suggest using the terminology "message interval", since the entropy
calculation is time-scale invariant.

Hal's suggestion for rollover schemes is a good one.  I'll be working
on the math for it.

Eric