  This paper presents Wally, a private search system that supports efficient
semantic and keyword search queries against large databases. When sufficient
clients are making the queries, Wally performance is significantly better than
previous systems. In previous private search systems, for each client query,
the server must perform at least one expensive cryptographic operation per
database entry. As a result, performance degraded proportionally with the
number of entries in the database. In Wally we get rid of this limitation.
Specifically, for each query the server performs cryptographic operations only
against a few database entries. We achieve these results by requiring each
client to add a few fake queries, and sends each query via 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 $(\epsilon, \delta)$-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 fake queries' overhead vanishes as the number of
clients increases, enabling scalability to millions of queries and large
databases. Concretely, Wally can serve $8$M requests at a rate of 3,000 queries
per second. That is around 60x higher than the state-of-the-art scheme.
