Accounting for the large number of queries sent by users to search engines on a daily basis, the latter are likely to learn and possibly leak sensitive information about individual users. To deal with this issue, several solutions have been proposed to query search engines in a privacy preserving way. A first category of solutions aim to hide users’ identities, thus enforcing unlinkability between a query and the identity of its originating user. A second category of approaches aims to obfuscate the content of users’ queries, or at generating fake queries in order to blur user profiles, thus enforcing indistinguishability between them. In this paper we propose PEAS, a new protocol for private Web search. PEAS combines a new efficient unlinkability protocol with a new accurate indistinguishability protocol. Experiments conducted using a real dataset of search logs show that compared to state-of-the-art approaches, PEAS decreases by up to 81.9% the number of queries linked to their original requesters. Furthermore, PEAS is accurate as it allows users to retrieve up to 95.3% of the results they would obtain using search engines in an unprotected way.