Our ubiquitous connection to the internet triggered awareness and concerns regarding privacy preservation issues. However, while privacy is a more and more known subject, a few points remain to be clarified. It is expected from a privacy-preserving web search engine not to track you via your queries and clicks history nor to sell your personal data. Nevertheless, it can use non-personal data to improve search engine relevance. Moreover, using a privacy-focused web search engine means being ready to adapt the way of querying it to add the information the search engine does not have about you. This talk will focus on how we can create a web search engine that preserves its users' privacy while focusing on the relevance of its results and the privacy preservation of its users.