Hi all,

Long-time follower, first time poster. I have an interest in darknets
and saw this paper
(http://www.ieee-security.org/TC/SP2013/papers/4977a080.pdf) today in a
message under "Freedom Hosting Owner Arrested, Tormail Compromised,
Malicious JS Discovered", which naturally got me quite worried. It did
remind, however, about a few ideas I have had in the past about
guarantees of anonymity in a network.

Consider a broadcast network: an eavesdropper cannot tell who a message
is intended for from just the transmission itself. By using asymmetric
encryption, the contents of the message can also be made unreadable to
the eavesdropper and all unintended recipients, still preserving perfect
single fact anonymity.

Over time, an attacker could determine the intended recipient by looking
at who sent messages within a certain time frame from receiving a
message: the information gain from this is increased substantially if
certain information about the protocol of the messages is known (e.g. if
we're anonymising a real-time protocol, timed traffic analysis can
reveal an intended recipient with a high degree of certainty). This can
be defeated by including noise in the network: peers constantly produce
garbage packets.

I believe that this would yield information theoretically secure
anonymity, as an attacker is looking for hay in a haystack, so to speak.
Obviously, the problem with this protocol is that it is horrendously
inefficient.

I am inclined to believe that we can preserve the anonymity properties
of this protocol while reducing its network load, in exchange for
reliability. The original protocol implies that the intended recipient
will always get the message, but if we allow for the possibility of
delivery failure we can reduce traffic.

The protocol I propose is thus as follows: peers send hop-to-hop
encrypted packets to a subset of the other nodes on the network. Each
packet contains the payload (encrypted for the intended recipient) and a
TTL counter. If a peer cannot decrypt the payload, the message is not
intended for them and so the TTL is decreased and the new message is
then broadcast out to another random subset of the peers on the network.
Again, we include noise packets.

For a TTL of t and a subset network ratio of s, we thus expect ts
transmissions for a single packet, where we intend ts < n so as to
obtain a more efficient solution.

Other possible considerations are non-fully connected networks, although
I believe that a theoretically secure routing protocol must fulfil at
least one of the two axioms:
1) all peers must eventually receive the message; or
2) the message is not guaranteed to reach its intended recipient.

Thoughts? Also, is there any literature on or implementations of
theoretically secure networks?