[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Trevor Perrin]

On Tue, Feb 18, 2014 at 5:37 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On 2/18/14, Trevor Perrin <trevp at trevp.net> wrote:
>
>>  - Eliminate the central directory and lookup a party's key at a
>> directory of her choice.  So instead of just exchanging fingerprints,
>> Alice and Bob exchange <fingerprint><@directory-name>, and choose
>> directories who they trust not to do these things.
>
> This reveals more information to an attacker passively observing the
> directory server.

Suppose each user chooses their mailbox server as their directory
server.  Now this server has three roles -
 - directory:  return "introduction cert" for a fingerprint
 - rendezvous:  host an anonymous exchange of encrypted secrets
 - mailbox:  receive messages for the user

In all of these roles the server is contacted via Tor.  An attacker
observing traffic in and out of Tor might be able to link clients and
servers by correlation.  If such an attacker colludes with a server,
then clients could be linked to server users (directory and mailbox
protocols) or to each other (rendezvous).

I argue that since this is an existing risk for mailbox and rendezvous
protocols, adding the directory role doesn't significantly increase
it.  Also, measures to reduce this risk (more dummy traffic;
high-latency mixes) could be applied across server roles.


> PIR is a very good idea.

A new risk introduced by directory servers is that they could collude
and detect that lookups for Alice and Bob were performed at around the
same time.

Each user's app could add a random delay of a few hours before
querying the directory server.  Combined with a modest level of dummy
traffic this could give a "pretty good" level of unlinkability (e.g.
each user could perform a directory lookup for herself at random
intervals, several times per day, and/or could register with a dummy
traffic generator which does the same).

Could PIR do better?  My impression was that single-server PIR schemes
were very costly in computation and/or bandwidth.  Is there a scheme
you'd recommend?


Trevor