Wireless networks offer novel means to enhance social interactions. In particular, peer-to-peer wireless communications enable direct and real-time interaction with nearby devices and communities and could extend current online social networks by providing complementary services including real-time friend and community detection and localized data sharing without infrastructure requirement. After years of research, the deployment of such peer-to-peer wireless networks is finally being considered. A fundamental primitive is the ability to discover geographic proximity of specific communities of people (e. g, friends or neighbors). To do so, mobile devices must exchange some community identifiers or messages. We investigate privacy threats introduced by such communications, in particular, adversarial community detection. We use the general concept of community pseudonyms to abstract anonymous community identification mechanisms and define two distinct notions of community privacy by using a challenge-response methodology. An extensive cost analysis and simulation results throw further light on the feasibility of these mechanisms in the upcoming generation of wireless peer-to-peer networks.