  Many proximity-based mobile social networks are developed to facilitate
connections between any two people, or to help a user to find people with
matched profile within a certain distance. A challenging task in these
applications is to protect the privacy the participants' profiles and personal
interests.
  In this paper, we design novel mechanisms, when given a preference-profile
submitted by a user, that search a person with matching-profile in
decentralized multi-hop mobile social networks. Our mechanisms are
privacy-preserving: no participants' profile and the submitted
preference-profile are exposed. Our mechanisms establish a secure communication
channel between the initiator and matching users at the time when the matching
user is found. Our rigorous analysis shows that our mechanism is secure,
privacy-preserving, verifiable, and efficient both in communication and
computation. Extensive evaluations using real social network data, and actual
system implementation on smart phones show that our mechanisms are
significantly more efficient then existing solutions.

Social and Information Networks;Cryptography and Security