With rapid developments of mobile devices and online social networks, users of Proximity-based Mobile Social Networks (PMSNs) can easily discover and make new social interactions with others at the cost of their growing privacy concerns. To address this problem, we propose a third party free scheme, P-match, to privately match the similarity with potential friends in vicinity. Unlike most existing work, P-match considers both the number of common interests and the corresponding priorities on each of them individually. The security and performance overhead of our scheme are then thoroughly analyzed and evaluated via detailed simulations.