This article presents Wally, a private search system that supports efficient semantic and keyword search queries in large databases. When enough clients make queries, Wally's performance is significantly better than previous systems. In previous private search systems, for each client query, the server had to perform at least one expensive cryptographic operation for each database entry. As a result, performance degraded proportionally with the number of entries in the database. At Wally we eliminate this limitation. Specifically, for each query, the server performs cryptographic operations on only a few database entries. We achieve these results by asking each client to add some fake queries and send each query over an anonymous network to the server at independently chosen random instants. Additionally, each client also uses somewhat homomorphic encryption (SHE) to hide whether a query is real or fake. Wally provides differential privacy guarantee (ε, δ), which is an accepted standard for strong privacy. The number of fake queries each client makes depends inversely on the number of clients making queries. Therefore, the overhead of false queries disappears as the number of clients increases, allowing scalability to millions of queries and large databases. Specifically, Wally can process eight million queries in 117 minutes, or just under two hours. This is about four orders of magnitude faster than the state of the art.
