Secret Handshakes with Dynamic and Fuzzy Matching

The need for communication privacy over public networks is of growing concern in today’s society. As a result, privacy-preserving authentication and key exchange protocols have become critical primitives in building secure distributed systems. Secret handshakes provide such a service by allowing two members of the same group to secretly and privately authenticate to each other and agree on a shared key for further communication. This paper presents the first efficient secret handshake schemes with unlinkable, reusable credentials that do not rely on random oracles for their security (solving open problems from prior literature). In previous work, secret handshakes were extended with roles, so that a group member A can specify the role another group member B must have in order to successfully complete the protocol with A. We generalize the traditional and role-based secret handshake in two ways. First, we present a secret handshake with dynamic matching, in which each party can specify both the group and the role the other must have in order to complete the handshake. Second, we provide a novel extension of secret handshakes to include attributes, allowing the handshake to be based on approximate (or fuzzy) matching. We demonstrate the practicality and efficiency of our protocols by evaluating a prototype implementation. We integrate our dynamic matching protocol into IPsec, and we detail the performance tradeoffs associated with our fuzzy matching scheme. Our experiments indicate that our solutions offer attractive performance.