Web Search Engines store and analyze queries made by their users in order to build their profiles and offer them personalized search results (i.e., results are ranked according to each user’s preferences). Even though this service is positive for the users, their profiles may contain sensitive information that can threaten their privacy. Literature in this field stresses the existence of a trade-off between the level of privacy achieved and the quality of service received. Current proposals try to maximize this trade-off, yet we argue that there is still room for improvement. In this paper, we present a new approach which improves the trade-off by grouping users who share similar profiles. Moreover, our new proposal is based on a hybrid P2P architecture that outperforms current schemes in terms of scalability. The proposed system has been tested in terms of performance and privacy achieved, using real data from the AOL dataset. Simulation results show that: (i) the system protects users’ privacy when they behave honestly, and penalizes selfish users; (ii) it supports a large number of users; (iii) the runtime required to group users is affordable; and (iv) groups are dynamic and their topology is unpredictable, which we argue that is positive from the privacy point of view.