Enabling Privacy-Preserving Image-Centric Social Discovery The increasing popularity of images at social media sites is posing new opportunities for social discovery applications, i.e., suggesting new friends and discovering new social groups with similar interests via exploring images. To effectively handle the explosive growth of images involved in social discovery, one common trend for many emerging social media sites is to leverage the commercial public cloud as their robust backend data center. While extremely convenient, directly exposing content-rich images and the related social discovery results to the public cloud also raises new acute privacy concerns. In light of the observation, in this paper we propose a privacy-preserving social discovery service architecture based on encrypted images. As the core of such social discovery is to compare and quantify similar images, we first adopt the effective Bag-of-Words model to extract the “visual similarity content” of users’ images into image profile vectors, and then model the problem as similarity retrieval of encrypted high-dimensional image profiles. To support fast and scalable similarity search over hundreds of thousands of encrypted images, we propose a secure and efficient indexing structure. The resulting design enables social media sites to obtain secure, practical, and accurate social discovery from the public cloud, without disclosing the encrypted image content. We formally prove the security and discuss further extensions on user image update and the compatibility with existing image sharing social functionalities. Extensive experiments on a large Flickr image dataset demonstrate the practical performance of the proposed design. Our qualitative social discovery results show consistency with human perception.