[messaging] secret handshakes (was: Recognizing senders of metadata-hidden messages)

[Brian Warner]

On 7/24/15 1:09 AM, Jeff Burdges wrote:

> p.s. It's maybe worth asking : How should two devices identify when
> they come into radio proximity without revealing their identity to
> eavesdroppers? There is a more you can do with the proximity based
> transport, but maybe something is relevant.

Sounds like a "Private Handshake" (Jaap-Henk Hoepman, 2007,
http://arxiv.org/pdf/0804.0074.pdf) or "Secret Handshake"
(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.9132).

Two nodes, each a member of some (possibly-overlapping) set of groups,
can figure out which groups they're both in without revealing any of the
others. Hoepman's approach costs O(a+b) bytes in two roundtrips, where
'a' and 'b' are the number of groups that Alice and Bob belong to (or an
upper bound on it, if you don't want to reveal the exact number), and is
a pretty simple extension of plain DH.

I'm thinking you could define a bunch of pairwise groups (they're just
random strings like H("Alice"+"Bob")), only with the devices that you'd
previously met, and then when your radio sees the presence of another
device, run the private handshake protocol to discover if they're a
friend without revealing anything else about yourself. Maybe negotiate
to do a few dozen or hundred at a time if there's the fixed-size upper
bound is too small. And I bet there's even better protocols in the RFID
/ mobile-credentials literature.

cheers,
 -Brian