Matching two or more users with related interests is an important and general primitive, applicable to a wide range of scenarios including job hunting, friend finding, and dating services. Existing on-line matching services requires participants to trust a third party server with their preferences. This raises security and privacy issues. In this paper, we tackle this problem by introducing two privacy-preserving protocols: server-led matching and user-led matching. In the first protocol, potential matching pairs (e.g., users, companies) are selected by the server, which collects and combines each party’s preference. In the second, entities are allowed to express their preference for any party—regardless of whether the other party is known to the server. With server-led matching, users reveal no information to the server; the server’s role is simply to relay messages. In user-led matching, the server only learns which users match. Our protocols are scalable, i.e., preferences can be matched in constant time. We formally define security and functionality requirements for generic server-led and user-led matching protocols, and provide security proofs for our instantiations within this framework.