Scalable Private Search with Wally

This paper presents Wally, a private search system that supports efficient semantic and keyword search queries against
large databases. When sufficiently many clients are making
queries, Wally’s 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 remove this limitation. Specifically, for each
query the server performs cryptographic…