Abstract Web search engines (WSEs) allow information retrieval from the Internet, a really useful service which is not provided without cost: users’ queries and related information (e.g., query time, browser type, etc.) are stored and analyzed in the WSE database. The stored logs may contain sensitive information (e.g., health issues, location, religion, etc.) and identifiers (e.g., full name, IP address, cookies, etc.), which poses a serious threat to users’ privacy. In the literature, there are several proposals that try to address this situation. In general, current schemes consider the WSE as the only adversary, and do not address the presence of other attackers or, if addressed, the introduced query delay is unaffordable in real environments. In this paper, we propose a distributed protocol, where a group of users collaborate to protect their privacy in front of WSEs and dishonest users, while introducing a reasonable delay. The performance of the new scheme is evaluated in terms of privacy level and delay. The former is analyzed using a set of query logs belonging to real users and provided by AOL. The latter involves the implementation, deployment and evaluation of the protocol in a real environment.