Thesis of Besma Khalfoun

Privacy Preserving Online Services


Nowadays, a wide variety of online services (e.g., web search engines, location-based services, recommender systems) are being used by billions of users on a daily basis. Key to the success of these services is the personalization of users’ results, i.e., returning to each user the results that are closer to her interests. For instance, given a web search query sent by two different users, search engines generally rank differently the search results to best fit each user preferences [2]. The latter preferences are generally computed by relying on user profiles that are learnt from past user queries. However, according to the underlying application, user profiles may contain sensitive information about end users. For instance, in the context of location-based services, user profiles contain user mobility data from which it is easy to infer information such as a user’s home and workplace or even her sexual, religious or political preferences if she regularly visits gay bars, worship places or the head quarter of a political party [1]. However, user profiles, which are widely exploited by online service providers due to their inherent business model based on online advertising, might severely threaten user privacy if they end up into the hands of untrusted services. Recent events have shown that the latter risk of data privacy leakage is becoming a reality due to the massive use of cloud services by online service providers and by end users. Indeed, a 2014 study from Gartner found that 94% of organizations either already are or plan to store their consumer data in the cloud. Another study by the same organization envision that the "Cloud Shift" by 2020 will affect more than $1 Trillion in IT spending1. On the same line, cloud providers are experiencing an exponential growth of their storage capabilities2. Due to their success and to the unprecedented value that can be extracted from the data they store (e.g., financial information, health in- formation, trade secrets, intellectual property) cloud providers are becoming the target of devastating attacks3. Examples of such attacks that took place in 2016 include hospital ransomware, millions of Dropbox account details leaked, other millions of Snapchat accounts compromised to cite a few.


In this context, it becomes urgent to devise mechanisms that allow users to securely access online services without fearing that their data will be leaked out from the cloud platforms where it is being stored and processed. For addressing this challenge, the research community in the past years has been very active in devising mechanisms for accessing online services in a privacy-preserving way (e.g., [3, 5, 4, 6]), or for designing novel secure online services (e.g., [7]). However, while the former make rather far reaching trust assumptions, the latter rely on heavy cryptographic techniques. In practice, none of the existing solution can be transposed to reality as the first group of solutions incurs the risk that the assumptions get broken whilst the second group has typically high resource demands and severely degraded service performance.



The objective of this PhD project is to design novel protocols that aim at eliminating these barriers for the success of privacy-preserving online services. This will be guided by the reduction of trust assumptions, while still providing improved performance compared to the state of the art. Examples of online services that might be considered include: location-based services, search engines, recommender systems, etc.


The objective of this PhD project is precisely to address these challenges as follows:

  • Consider various threat models to reduce trust assumptions
  • Provide novel solutions for effective privacy-preserving online services
  • Assess the robustness of the proposed solutions through attacks

The PhD project will be organized as follows:

  • Year 1: Perform an exhaustive study of the related work in the fields of online services’ architectures, protocols for privacy preserving online services, attacks to assess the robustness of privacy preservation solutions, and study the limitations of the existing solutions. Propose novel attack(s) to assess the robustness of privacy preservation under different trust assumptions. Compare the proposed attack(s) to state-of-the-art attacks. Conduct evaluations with real-life datasets.
  • Year 2: Propose a first version of a privacy preserving protocol for privacy preserving online services. Provide a security analysis of the proposed protocol, as well as a first prototype. Provide a performance, robustness and cost analysis of the proposed protocol, as well as a software prototype. Conduct evaluations with real-life datasets.
  • Year 3: Propose an effective and robust privacy preserving protocol for privacy preserving online services, with different trust assumptions. Provide a performance, robustness and cost analysis of the proposed protocol, as well as a software prototype. Conduct evaluations with real-life datasets. Finally, write the PhD thesis and organize the PhD defense.


  1. Sébastien Gambs, Marc-Olivier Killijian, and Miguel Núñez del Prado Cortez. Show me how you move and I will tell you who you are. In: Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS. ACM. 2010, pp. 34–41.
  2. Amy N Langville and Carl D Meyer. Google’s PageRank and beyond: The science of search engine rankings. Princeton University Press, 2011.
  3. Saikat Guha, Bin Cheng, and Paul Francis. Privad: Practical privacy in online advertising. In: USENIX conference on Networked systems design and implementation. 2011, pp. 169–182.
  4. Saikat Guha, Mudit Jain, and Venkata N Padmanabhan. Koi: A location-privacy platform for smartphone apps. In: Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association. 2012, pp. 14–14.
  5. Albin Petit et al. Peas: Private, efficient and accurate web search. In: Trustcom/BigDataSE/ISPA, 2015 IEEE. Vol. 1. IEEE. 2015, pp. 571–580.
  6. Esma Aïmeur et al. Alambic: a privacy-preserving recommender system for electronic commerce. International Journal of Information Security 7.5 (2008), pp. 307–334.
  7. Sergey Yekhanin. Private information retrieval. Communications of the ACM 53.4 (2010), pp. 68–73.

Advisor: Sonia Ben Mokhtar
Coadvisor: Sara Bouchenak