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 operations against
only a few database entries. We achieve these results by requiring each client to add a few fake queries, and send 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 (ε, δ) -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 process eight million queries
in 117 minutes, or just under two hours. That is around four
orders of magnitude faster than the state of the art.
