[messaging] Unlinkable rendezvous via human-sized keys (was: Re: Human sized keys)

[Trevor Perrin]

On Sun, Mar 23, 2014 at 7:53 AM, Joseph Bonneau <jbonneau at gmail.com> wrote:
> If N people get together, and then they all lookup a very similar set
> of N-1 intro-certs promptly thereafter, this is going to be
> hard-to-impossible to mask by timing noise and dummy traffic. I suspect that
> if unlinkability is a goal then this approach requires PIR.

Hmm, you're probably right.  Creating dummy lookups is seeming harder
the more I think about it (Who generates them?  How trusted are those
parties?  How much information is going to leak through the noise?,
etc).

My vague understanding of PIR is that "single-server" schemes are less
practical than just sending the whole database, but there are
"multi-server" schemes which are somewhat-efficient and secure as long
as all servers don't collude.  (Is that right?  Could anyone explain
PIR in a separate thread?)

If that's true, maybe the best we could do is "PIR mirrors" which
maintain copies of the well-known intro-cert directories?  Users would
lookup intro-certs by PIR-queries to independent mirrors.

---

We're circling around a few ideas for the "physical meeting ->
introduction secret -> unlinkable online rendezvous" scenario.  Are
there other approaches we're missing?

Ways to arrive at an "introduction secret" based on a physical
meeting, and their downsides:

 1) Secret exchange
  - asking people to think up sufficient entropy on the fly seems
risky and low useability
  - using non-computer tools to generate entropy seems low useability
(shuffling cards, rolling dice, tearing "tickets" in half, etc.)
  - central rendezvous server / DHT needed

 2) "Human-sized" ECDH key exchange
  - smallish keys (32 base32 chars = 80 bit security)
  - low "forward secrecy for linkages" unless you change the key frequently
  - central rendezvous server / DHT needed
  - needs user preparation before meeting

 3) Directory Name + Fingerprint exchange
  - needs PIR to make "intro-cert" lookups unlinkable
  - needs user preparation before meeting


Trevor