Master's Thesis: Performance-Improved Onion Routing

[Johannes Renner]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Nick Mathewson wrote:
>> proposed techniques is presented. Included evaluations cover the
>> performance that is reached on average, but also the degree of
>> anonymity that is achieved when employing different methods of
>> path selection.
>
> What are you using as your anonymity measure?

[Answering here since it seems to be interesting]

To measure a "degree of anonymity", a certain method of path
selection can provide, I do the following:

I generate a (preferably big) amount of paths, without actually
creating any circuit. This list of paths can then be evaluated
regarding the occurrences of specific nodes on the single
positions of the paths. So, as a first metric I simply count the
total number of different nodes that is chosen on the single
positions of the paths. The higher the single numbers for
entry/middle/exit positions, the more anonymity there is.

I know, this metric does not consider that some methods choose
some nodes with a higher probability (means more often) than
others. Therefore, I work towards the conditional probability
that a specific entry node is chosen, given the IP of an exit
node and vice-versa (according to an advice from Mike Perry).
This means, instead of counting the occurrences of single nodes,
I count the total number of different combinations of entry and
exit nodes (EE-combinations). Intuitively, the more different
EE-combinations there are in a sample of n paths, the better the
achieved anonymity.

Further, I calculate the entropy regarding the probabilities of
the different EE-combinations, and from this, a bounded degree
of anonymity 'd'. This is done using the maximum entropy that is
calculated from a sample of size n, where no two paths have the
same EE-combination (which means d=1, iff all of the generated
paths show different EE-combinations). This way it is easy to
compare different methods of path selection regarding the
achieved anonymity by generating samples of the same size. From
these samples, 'd' is calculated and the results can be compared.
For my thesis I generated samples of 100.000 paths (only), so it
will be interesting to increase n to maybe 1.000.000 and repeat
the experiment.

Note, that I only had limited time for writing my thesis, and
the anonymity evaluation was not the most important aspect in
it (even if it is maybe the most interesting). So, all of this
surely offers room for improvements, please send me your ideas!

Have a nice weekend,
Johannes
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFG/SRE1TFW0/n+aNgRAsWeAJsEDErLkwO53/gW+Mq9JB30vA428wCghKF9
Ro1gxrrLjQeib0/KyH4wgjo=
=kLdW
-----END PGP SIGNATURE-----