In mobile social networks (MSNs), it is a crucial application to establish new connections within near range according to personal preferences. Existing systems are still far from practical applications. And they usually make all the users’ profiles completely public for the convenience of searches. However, in many applications, users’ profiles involve their privacy, which users do not want to publish. Based on homomorphic encryption and threshold scheme, we construct a user profiles matching protocol with strong privacy. The protocol is proven to be secure in the standard model.