The matching protocol

Two users should match when their preferences are mutually compatible and their phone books share at least one contact — without either the server or the other user learning any phone number. Vouch does this with DH-based Private Set Intersection (PSI) on ristretto255.

The protocol in one paragraph

Each device holds a random ristretto255 scalar k. Contacts are normalised to E.164 and hashed to curve points; the device publishes P·k for each contact plus own_token = P(own_phone)·k. The server pairs preference-compatible users and hands each the other’s published set; each device applies its own key on top (order-preserved) and posts the result. Equal 32-byte values in the two doubly-encrypted lists ⇔ a shared contact (P·k_a·k_b == P·k_b·k_a); re-encrypted own-tokens detect direct acquaintances, which are suppressed. The server learns only intersection cardinality and index linkage — never a phone number.

Why this is safe against the server

The server only ever sees points of the form P·k (and later P·k_a·k_b). A ristretto255 point reveals nothing about the phone number P was derived from without the scalar k, which never leaves the device. Commutativity of scalar multiplication is what makes the match work at all: applying k_a then k_b lands on the same point as k_b then k_a, so a shared contact produces byte- identical results on both sides — while the server, lacking either scalar, cannot invert any of it.

Direct-acquaintance suppression

If A already has B’s number, they’re not “meeting through a mutual contact” — they already know each other. Each side’s own_token is re-encrypted with the other’s key and checked against the intersection; a hit there means a direct relationship, and that pairing is suppressed rather than surfaced as a match.

Keeping client and server bit-compatible

The crypto runs in two languages — Python on the server, libsodium in the browser. vectors/ holds cross-language test vectors so the two implementations stay byte-for-byte compatible; a mismatch would silently break matching, so the vectors are part of the test suite.

Related

• Client protocol specification — the exact behaviour a client must implement: state, storage, ordering, polling schedule, error handling.
• Architecture — where this sits in the system.
• API Reference — the endpoints that carry the published sets (/me/contact-set, /sync, /pairs/{pair_id}/response).