Abstract: Social search systems such as Aardvark and Facebook Questions allow users to pose questions to their social network in real time. Upon receiving a question on a particular topic, Aardvark for example forwards the question to available ``experts'' close to the querier in the social network to facilitate immediate, relevant answers to questions that prove too complex for web searches, e.g., when ``Googling it'' is not likely to yield adequate answers. While such systems have tremendous potential to tap into expertise, they are monolithic and do not provide adequate privacy. For example, Aardvark and Facebook have complete knowledge of the social network's structure, and users cannot pose anonymous queries or hide their areas of expertise. Thus the success of these systems will be limited to more general categories of questions and expertise, since many users will avoid asking or answering questions related to sensitive topics such as health, political activism, sexual orientation, and even innocuous questions which may make the querier seem ignorant. We propose Pythia, the first distributed peer-to-peer (P2P) social-network architecture that provides queriers and experts with anonymity and yet provides a mechanism to locate relevant experts. Through simulation on social network graphs, we show it is possible to strike a balance between privacy, timely satisfaction of queries, and proximity of experts to queriers, while maintaining scalability. Furthermore we explore statistical attacks specific to this domain, and show how queriers and experts can maintain their anonymity over time to defend against such attacks. We thus provide the first blueprint of a privacy-aware, P2P system for social search, and hope to spur future research into the development of such systems.
