Wally: Scaling Private Search to Millions via Vanishing Noise and Differential Privacy

TL;DR

Private search has long been trapped between two extremes: efficient but insecure "query obfuscation," and cryptographically secure but prohibitively slow "fully oblivious" systems. Wally, a new system from Apple and Royal Holloway researchers, breaks this deadlock. By relaxing the privacy requirement to (ϵ, δ)-differential privacy and leveraging large user volumes, Wally achieves 7-28x higher throughput and 30x lower bandwidth than the previous state-of-the-art (Tiptoe), making private search truly scalable.

The Problem: The "All-or-Nothing" Tax

Why is private search hard? If a server doesn't scan every item in a database to answer your query, it learns which items you weren't looking for. This "scanning tax" makes systems like Tiptoe or traditional Private Information Retrieval (PIR) incredibly heavy on CPU and bandwidth. For a 3.2M entry database, Tiptoe demands 17MB of data per query—a non-starter for mobile or high-frequency search.

Wally's core insight is simple: In a massive search engine, you are never alone. Instead of trying to be perfectly invisible to the server (full obliviousness), Wally aims to be statistically indistinguishable within a crowd (Differential Privacy).

Methodology: Privacy Through Collective Noise

Wally uses a multi-layered approach to protect queries:

1. Cluster-Based Search: The database is partitioned into $K$ clusters. Clients download centroid embeddings and identify the top $\Delta$ clusters closest to their query.
2. Vanishing Fake Queries: To hide which clusters are being accessed, clients inject fake queries sampled from a Negative Binomial distribution. Crucially, the number of fake queries per user decreases as the total number of users increases. In a system with 500,000 users, the overhead becomes negligible.
3. Vectorized SHE (BFV Scheme): Instead of the server sending back entire clusters, the client sends an encrypted query vector. The server computes a secure dot-product using the BFV homomorphic encryption scheme, returning only the encrypted similarity scores.
4. Timing & Anonymity: Queries travel through an anonymous network (like OHTTP) and are buffered into 1-second slots to prevent the server from using "arrival time" to fingerprint users.

System Architecture

Why This Works: The Math of Security

The technical genius of Wally lies in Theorem 1 of the paper. By using the Negative Binomial mechanism, the server’s view of the query traffic across all clusters becomes a "noised histogram." The privacy proof shows that this histogram satisfies $(ϵ,\delta )$-DP, meaning an adversary cannot determine with high confidence whether a specific user's query was included in the batch.

At the hardware level, Wally optimizes SHE operations through:

• Baby-Step Giant-Step (BSGS): Reducing the number of expensive ciphertext rotations.
• Plaintext CRT: Increasing precision without bloating the evaluation keys.

Experiments: Performance vs. Accuracy

Wally was tested against Tiptoe and Pacmann (a concurrent graph-based system).

Wally isn't just faster; it's more accurate. By probing more clusters ($\Delta =5$), it achieves an MRR (Mean Reciprocal Rank) of 0.18, significantly better than Tiptoe’s 0.11, while still remaining 6x faster and 7x lighter on data.

Practical Insights & Future Work

Wally proves that Differential Privacy is the "Goldilocks" zone for private systems at scale. However, it does require a minimum "crowd size" to be effective. In small-scale deployments (e.g., a few hundred users), the fake-query overhead would be too high, making Tiptoe a better choice.

Key Takeaways for Engineers:

• Crowd-Sourced Privacy: If you have >100k users, DP is often a better tool than full PIR.
• SHE is Ready: With optimized libraries (like Apple's open-source Swift HE library), homomorphic dot-products are fast enough for real-time applications.
• The Metadata Hurdle: Retrieving high-bandwidth metadata (images, bios) still requires clever two-stage retrieval using Keyword PIR (like MulPIR).

Wally marks a transition from "academic curiosity" to "production-ready" private infrastructure, potentially changing how we think about privacy in Siri, Google Search, or Spotlight.

Reference: Asi et al., "Scalable Private Search with Wally", Apple Inc. & Royal Holloway University.