Trustable Relays for Anonymous Communication
Carlos Aguilar Melchor(a),(*), Yves Deswarte(b)
Transactions on Data Privacy 2:2 (2009) 101 - 130
(a) XLIM-DMI laboratory; 123 av. Albert Thomas; 87060 Limoges Cedex; France.
(b) LAAS-CNRS laboratory; 7 avenue du Colonel Roche; 31077 Toulouse Cedex 4; France.
e-mail:carlos.aguilar @unilim.fr; yves.deswarte @laas.fr
Current systems providing anonymous interactive communication are based on networks of
anonymity-providing relays called MIXes. An important issue with
such systems is that a MIX is able to betray its users, and thus it
is necessary to use several MIXes sequentially for each
communication, which distributes the trust among them. This
increases the complexity of the protocols as well as the latency. On
the other side, such distributed systems are resilient and scalable,
and they provide good enough performance for web browsing.
An ideal relay should be unable to betray its users (we will say in
this case that the relay is trustable). In such a setting,
using multiple relays to distribute trust is not necessary, which
simplifies design and reduces costs. Superposed sending provides an
approach to construct trustable relays, the DC-net
relays. Straightforward usage of classic protocols leads to other
approaches and recently we proposed a set of trustable relays, based
on Private Information Retrieval protocols, that provide new
Independently of their practical applications, these relays are
interesting from a theoretic point of view. In this paper, we
present a survey that gathers the different trustable relays we have
been able to identify and gives a unified view of their
* Corresponding author.