The success of online social networking and of mobile phone services has resulted in increased attention to mobile social networking. Matchmaking is a key component of mobile social networking. It notifies users of nearby people who fulfil some criteria, such as having shared interests, and who are therefore good candidates for being added to a user's social network. Unfortunately, the existing matchmaking approaches are troublesome from a privacy point of view. One approach has users' smartphones broadcast their owners' personal information to nearby devices. This approach reveals more personal information than necessary. The other approach requires a trusted server that participates in each matchmaking operation. Namely, the server knows the interests and current location of each user and performs matchmaking based on this information. This approach allows the server to track users. This paper proposes a privacy-preserving matchmaking protocol for mobile social networking that lets a potentially malicious user learn only the interests (or some other traits) that he has in common with a nearby user, but no other interests. In addition, the protocol is distributed and does not require a trusted server that can track users or that needs to be involved in each matchmaking operation. We present an implementation and evaluation of our protocol on Nexus One smartphones and demonstrate that the protocol is practical.