Web search engines (e.g. Google, Yahoo, Microsoft Live Search...) are widely used to find certain data among a huge amount of information in a minimal amount of time. However, these useful tools also pose a privacy threat to the users: web search engines profile their users by storing and analyzing past searches submitted by them. To address this privacy threat, current solutions propose new mechanisms that introduce a high cost in terms of computation and communication. In this paper the authors present a novel protocol specially designed to protect the users' privacy in front of web search profiling.