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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
