Private Web Search with Tiptoe

Private Web Search with Tiptoe

Speakers: Alexandra Henzinger, Fourth-Year PhD Student, MIT

Conference: RSAC 2024

YouTube: https://www.youtube.com/watch?v=H2cKglVMt6Q

Overview

In an era where personal data is increasingly valuable and vulnerable, the privacy implications of everyday online activities, particularly web search, are profound. Alexandra Henzinger's talk at RSAC 2024, "Private Web Search with Tiptoe," introduces a groundbreaking prototype for a private web search engine designed to protect user queries from the search engine itself. This research addresses a critical vulnerability: current large-scale search engines, by their very nature, must see a user's query to return relevant results, leading to the accumulation of vast amounts of sensitive personal data. This data is a prime target for breaches, resale, and training AI models that could inadvertently expose private information.

Tiptoe represents a significant leap forward by ensuring that the search engine servers learn nothing about what a user is searching for, nor what URL is returned as a result. This is achieved through sophisticated cryptographic protocols where all queries and responses are transmitted as fixed-length cryptotexts, indistinguishable from random data to the server. Henzinger, a fourth-year PhD student at MIT advised by Henry Corgan Gibbs, along with collaborators Emma Domerman from Burnley and Nicholls Zelovic from MIT, demonstrates that strong query privacy at web scale is not only theoretically possible but also practically achievable, challenging long-held assumptions about the trade-offs between utility and privacy in information retrieval.

The talk highlights Tiptoe's ability to search over hundreds of millions of web pages in mere seconds, supporting both text and image data, with the potential to extend to other document types like code, video, or audio. While acknowledging that Tiptoe's search quality is not yet on par with commercial giants like Google or Bing, it significantly improves upon previous state-of-the-art private search systems and offers an acceptable level of relevance for many use cases. This work underscores the technical feasibility of a truly private web search experience, paving the way for future advancements in privacy-preserving technologies across various applications.

Background

▶ Watch: The problem: sensitive search queries reveal personal data (2:00)

The prevailing model for web search today inherently compromises user privacy. When a user submits a query to a search engine, the query string is sent over an encrypted channel (like HTTPS) to the server. While this protects the query in transit from external eavesdroppers, the search engine server itself must decrypt and process the query to identify and rank relevant web pages. This fundamental requirement means that even privacy-focused search engines like DuckDuckGo, or those accessed via anonymizing proxies like Tor, still possess the user's query content on their servers. Consequently, these entities accumulate immense repositories of sensitive user data, creating attractive targets for data breaches, potential resale to third parties, or use in training machine learning models that could later infer sensitive personal information.

Prior attempts to build search systems with strong query privacy, where the search engine learns nothing about the user's query, have been largely limited in scale. The state-of-the-art academic system, for instance, could privately search over Wikipedia, a corpus of approximately 5 million documents. This pales in comparison to the hundreds of millions or billions of documents indexed by major web search engines. The core challenge lies in the nature of standard information retrieval (IR) and search algorithms. These algorithms are typically not "crypto-friendly"; they involve numerous query-dependent random accesses to vast search indices. Performing such operations efficiently and effectively on data that remains encrypted from the server's perspective has historically been computationally prohibitive.

It's important to note the specific limitations that Tiptoe, by design, does not address. The system does not hide the frequency or timing of a user's searches. It also does not guarantee the integrity of the search results returned by the engine, meaning a malicious server could theoretically return incorrect or manipulated results (though this specific vulnerability is not explored in detail in the talk). Furthermore, Tiptoe's privacy guarantees are confined to the interaction between the user and the search engine. Once a user receives and clicks on a URL, subsequent HTTP or HTTPS requests to the destination website or other services could still leak browsing behavior to internet service providers or other third parties, falling outside Tiptoe's scope of protection. Despite these limitations, Tiptoe tackles the most critical privacy concern in web search: the server's knowledge of the query content itself.

Key Findings

▶ Watch: Existing private search systems don't scale to web size (4:40)

Tiptoe demonstrates that private web search is technically feasible at web scale, addressing a long-standing challenge in information retrieval and cryptography. The prototype successfully implements a search engine where servers learn absolutely nothing, in a strong cryptographic sense, about user queries or the specific URLs returned.

Key findings and contributions include:

• Scalability and Performance: Tiptoe can search over a public web crawl comprising 360 million web pages in approximately 3 seconds of latency per query. This represents a significant leap compared to previous private search systems, which were limited to much smaller datasets (e.g., 5 million Wikipedia documents).
• Broad Document Type Support: The system is capable of searching over both text and image data. The underlying approach is generalizable and can be extended to other document types, such as code, video, or audio, provided suitable embedding models exist.
• Efficiency Metrics: Each query with Tiptoe requires approximately hundreds of queries of server-side computation, roughly 60 megabytes (MB) of client-server communication, and about 0.3 gigabytes (GB) of local client-side storage. When normalized per document searched, Tiptoe achieves roughly 6,000 times less computation and 60 times less communication compared to previous state-of-the-art private search systems.
• Acceptable Search Quality: While Tiptoe's search results are not yet as refined as those from commercial search engines like Google or Bing, evaluations show they are acceptable in many cases. On a standard information retrieval benchmark, Tiptoe ranks human-chosen search results on average at position 7.7 out of the top 100, which is comparable to classic algorithms like TF-IDF (Term Frequency-Inverse Document Frequency) and an improvement over existing private search approaches. The quality is expected to improve with advancements in embedding models and clustering algorithms.
• Architectural Innovation: The system's efficiency gains stem from a novel combination of semantic embedding models, which provide compact and expressive document representations; the use of a fast, additively homomorphic encryption scheme (Simple PR) for efficient computation on encrypted data; and clustering techniques that allow communication costs to scale with the square root of the number of documents (sqrt(N)) rather than linearly.
• Broader Applicability: The core private nearest-neighbor search protocol developed for Tiptoe is highly versatile and can be applied to other privacy-sensitive domains beyond web search, such as building private recommendation engines (e.g., searching over products) or private advertising ecosystems (e.g., searching over ads).

In essence, Tiptoe provides a concrete demonstration that the long-sought goal of private web search is no longer a theoretical aspiration but a tangible engineering challenge, with a clear path for further optimization and real-world deployment.

Technical Deep Dive

▶ Watch: Introducing Tiptoe: a new prototype for strong query privacy (5:20)

Tiptoe's architecture and protocol are built upon two fundamental design steps, meticulously engineered to achieve privacy and scale.

Step 1: Transforming Search into Nearest Neighbor Search

The first critical step involves re-framing the complex and often ill-defined problem of text or image search into a mathematically precise nearest neighbor search problem. Tiptoe accomplishes this by leveraging machine learning and, specifically, semantic embedding models.

1. Semantic Embeddings: The search engine starts with a corpus of documents (e.g., web pages, images). Each document is mapped to a high-dimensional vector, known as an embedding, within an embedding space. These embeddings are typically vectors of a fixed dimension, such as 192. The crucial property of these semantic embedding models is that documents or queries that are close in meaning will map to points in the embedding space that are close in inner product distance. For example, two images of apples that are conceptually similar will have embeddings whose inner product yields a large number, indicating high similarity.
2. Client-Side Model: The exact same embedding model used by the server is downloaded and stored locally on the client device. This requires a fixed cost of client-side storage, typically around 270 MB, comparable to the size of a modern smartphone application.
3. Query Embedding: When a user wishes to make a search query (e.g., "new problem"), the query string is processed locally by the client's embedding model to generate a query embedding, a vector in the same embedding space as the document embeddings.
4. Nearest Neighbor Objective: The problem then reduces to finding the web page whose embedding is the nearest neighbor to the query embedding in the embedding space, based on inner product distance. This approach is not unique to Tiptoe; semantic embeddings are a standard technique employed in many non-private search systems to provide expressive search capabilities. The key advantage is that improvements in embedding models directly translate to improvements in Tiptoe's search quality, independent of the cryptographic protocols.

Step 2: Private and Large-Scale Nearest Neighbor Search Protocol

Once the search problem is transformed into a nearest neighbor search, Tiptoe employs a novel cryptographic protocol to solve it privately and at web scale. This step relies on two primary tools: clustering and a specialized homomorphic encryption scheme.

1. Clustering for Course Search:

• Server-Side Clustering: Ahead of time, the server groups its vast collection of document embeddings into clusters based on topical similarity. For example, all documents related to "medical conditions" might fall into one cluster.
• Centroid Publication: The server then publishes a list of the centroids (average embeddings) for each of these clusters.
• Client-Side Cache: The user pre-fetches and caches this list of cluster centroids locally. For a public web crawl, this list is relatively small, around 20 MB.
• Local Cluster Selection: At query time, after generating its query embedding, the client compares its query embedding to the cached cluster centroids to identify the closest cluster. This step is performed entirely locally by the client, without revealing the query or the selected cluster to the server.
• Privacy Requirement: The protocol must ensure that the server learns neither the user's specific query embedding nor the identity of the chosen cluster, as both pieces of information could leak sensitive details about the user's search intent.

1. Refining Search Results with Homomorphic Encryption:

• Additively Homomorphic Encryption: Tiptoe utilizes an additively homomorphic encryption scheme. Specifically, it employs Simple PR, a scheme developed jointly by some of Henzinger's collaborators at MIT and Google. The crucial property of this encryption scheme is that it allows for matrix-vector products on encrypted data. If M is a public (unencrypted) matrix and V is an encrypted vector, one can compute M Enc(V) to obtain Enc(M V) without decrypting V.
• Server's Search Index Matrix: The server constructs a massive search index matrix. The number of entries in this matrix corresponds to the total number of documents in the corpus (e.g., hundreds of millions), resulting in a matrix size of hundreds of gigabytes or even terabytes. The matrix is organized such that each column I contains all the document embeddings belonging to cluster I.
• Client's Encrypted Query Vector: At query time, the client, knowing its query embedding (Q) and the index of the closest cluster (C), constructs a special vector. This vector is composed of all zeros, except at the position corresponding to cluster C, where it places the query embedding Q. The client then encrypts this vector and sends it to the server. To the server, this encrypted vector appears as a stream of random bits, revealing nothing about Q or C.
• Server-Side Computation: The server, receiving the encrypted client vector, performs the matrix-vector product between its large search index matrix and the encrypted client vector. Due to the properties of additively homomorphic encryption and the way the client's vector is constructed, this computation effectively multiplies the document embeddings within the selected cluster C by the encrypted query embedding Q, while multiplying embeddings in all other clusters by encrypted zeros.
• Encrypted Scores and Client Decryption: The result of this server-side computation is an encrypted vector containing the encrypted inner product scores between the query embedding and all document embeddings within the chosen cluster. The client receives this encrypted result, decrypts it using its secret key, and can then identify the document with the highest inner product score (i.e., the most relevant document within that cluster).

System Architecture and Costs

Tiptoe's overall architecture comprises three main components:

1. Indexing Batch Jobs: These run offline, ahead of time. They take the raw document corpus and an embedding model, generate embeddings for all documents, cluster these embeddings, build the large search index matrix, and pre-process the cryptographic operations on this matrix for efficiency.
2. Ranking Service: This is the core service where the private nearest neighbor search protocol, as described above, takes place. The user sends an encrypted query function and receives encrypted relevance scores.
3. URL Service: After identifying the best-matching document, the user interacts with the URL service to privately fetch the actual URL. This service uses similar cryptographic techniques but is simpler as it doesn't involve complex ranking logic.

Protocol Costs:

• Communication: The client-server communication scales with sqrt(N * D), where N is the number of documents and D is the embedding dimension. This scaling is achieved by balancing the upload (which scales with the width of the server matrix) and download (which scales with the height) quantities.
• Server Operating Cost: The server must compute a large matrix-vector product for every query. The efficiency is largely due to Simple PR, which allows for pre-processing the server's matrix. This pre-processing makes the matrix-vector product almost as efficient as computing it on unencrypted data, requiring only 264-bit operations per embedding entry for every document in the corpus.

This intricate interplay of machine learning embeddings, clustering, and specialized homomorphic encryption allows Tiptoe to achieve strong privacy guarantees at a scale previously thought impractical for private search.

Demo / Proof of Concept

▶ Watch: Tiptoe searches hundreds of millions of pages in seconds (6:30)

Tiptoe is presented as a functional prototype, rigorously evaluated to demonstrate its capabilities and performance characteristics. The evaluation was conducted over a substantial dataset: a public web crawl containing approximately 360 million web pages.

Performance Benchmarking:

The Tiptoe prototype was benchmarked against PIR (Private Information Retrieval), a previous state-of-the-art academic system designed for private search over Wikipedia, which indexes roughly 5 million pages. To ensure a fair comparison despite the difference in corpus size, costs were normalized per number of documents searched.

• Client Storage: Tiptoe requires a relatively large 0.3 GB of client-side storage. This breaks down into roughly 270 MB for the user-held embedding model (a fixed cost that does not scale with corpus size) and 20 MB for the list of cluster centroids (which scales with sqrt(N), so for 100x more documents, it would be 200 MB).
• Computation: Tiptoe achieved a remarkable improvement, requiring approximately 6,000 times less computation per query compared to PIR.
• Communication: Similarly, Tiptoe demonstrated 60 times less communication per query than PIR.
• Latency: The end-to-end latency for a single search query over the 360 million web pages was on the order of 3 seconds.

These significant performance gains are attributed to three key factors:

1. Semantic Embeddings: Providing compact yet expressive document representations.
2. Simple PR: Utilizing a fast homomorphic encryption scheme for efficient computation.
3. Clustering: Enabling communication to scale with sqrt(N) instead of linearly, a critical optimization for large datasets.

Search Quality Assessment:

To evaluate the quality of Tiptoe's search results, the system was run on a standard information retrieval benchmark and compared against a suite of non-private search algorithms.

• Comparison with Non-Private Systems: The best deep learning-based non-private algorithms typically rank human-chosen relevant search results, on average, at position 2 out of their top 100 results. Tiptoe, being a private system, achieved an average rank of 7.7 for human-chosen results within its top 100.
• TF-IDF Comparability: This performance is roughly comparable to the classic TF-IDF (Term Frequency-Inverse Document Frequency) algorithm, which ranks documents based on the frequency and rarity of query words.
• Future Improvements: The researchers emphasize that Tiptoe's search quality is directly tied to the quality of the embedding and clustering algorithms plugged into the system. As these underlying machine learning components improve, so too will Tiptoe's search quality.

Search Result Characteristics:

Tiptoe generally performs best on conceptual queries. For example, a query like "how to make apple pie" would likely return relevant results. However, the system is less effective at exact string match queries, particularly for rare strings such as specific names, addresses, or phone numbers. Such queries are less likely to return highly relevant results compared to traditional exact-match search engines. This highlights a current trade-off between the semantic understanding provided by embeddings and the precision of literal string matching.

The prototype clearly demonstrates the practical viability of private web search at a scale previously considered unattainable, offering a concrete foundation for future research and development in this critical area.

Defensive Implications

▶ Watch: How Tiptoe works: ML embeddings and private nearest neighbor search (7:30)

The development and demonstration of Tiptoe carry significant defensive implications for individuals, organizations, and the broader cybersecurity landscape. By proving the technical feasibility of private web search at scale, Tiptoe offers a blueprint for a future where sensitive query data is no longer a liability.

1. Data Minimization by Design: For organizations operating search engines or any service involving user queries, Tiptoe provides a powerful example of privacy-by-design. Instead of collecting and storing vast amounts of sensitive query data (and then having to defend it), Tiptoe shows it's possible for the search engine never to learn the query in the first place. This fundamentally reduces the attack surface for data breaches involving query logs. A server compromised by attackers or compelled by legal requests cannot disclose information it never possessed.
2. Protecting User Privacy: For individual users, Tiptoe's approach means that their most intimate thoughts, health concerns, financial queries, political interests, and personal information, often revealed through search, can remain truly private from the search provider. This empowers users with greater control over their digital footprint and mitigates the risk of their data being misused for targeted advertising, profiling, or surveillance. While Tiptoe doesn't hide when or how many searches are made, or subsequent browsing, it addresses the core issue of query content exposure to the search engine itself.
3. Reducing Regulatory Burden: For companies, implementing Tiptoe-like systems could significantly ease the burden of complying with stringent data privacy regulations like GDPR, CCPA, or upcoming AI regulations. If query data is never seen or stored, many compliance obligations related to data protection, retention, and deletion become moot, simplifying legal and operational overheads.
4. Enabling New Privacy-Preserving Applications: Beyond general web search, the core private nearest-neighbor search protocol is a versatile primitive. Defenders in various sectors could leverage this technology to build privacy-preserving systems for:

• Healthcare: Searching medical databases without revealing patient queries or conditions.
• Finance: Securely querying financial records or market data.
• E-commerce: Private product recommendations without exposing user preferences.
• Advertising: Delivering relevant ads without learning user interests directly.
• Enterprise Search: Allowing employees to search sensitive internal documents without revealing their queries to the IT department or system administrators.

1. Shifting Trust Models: Tiptoe represents a shift from a "trust us not to misuse your data" model to a "we cannot misuse your data" model. This cryptographic assurance is a stronger form of security than policy or legal agreements alone. Defenders should advocate for and explore the adoption of such technologies to enhance the integrity and trustworthiness of online services.

In summary, Tiptoe provides a tangible vision for how privacy can be embedded at the architectural level of fundamental internet services. Its defensive implications are profound, offering a path towards fundamentally more secure and privacy-respecting digital interactions.

Key Takeaways

• Private Web Search is Feasible: Tiptoe conclusively demonstrates that building a web search engine that never learns what its users are searching for is technically achievable at web scale, moving beyond theoretical possibilities.
• Web-Scale Performance Achieved: The prototype can search over 360 million web pages with an impressive latency of approximately 3 seconds per query, offering a practical solution for large datasets.
• Efficiency Through Innovation: Tiptoe's performance gains are driven by the strategic combination of semantic embedding models for expressive document representation, clustering techniques to reduce communication costs (sqrt(N) scaling), and a fast additively homomorphic encryption scheme (Simple PR) for efficient computation on encrypted data.
• Manageable Client-Side Resources: Users need to store a fixed 0.3 GB locally, primarily for the embedding model (270 MB) and cluster centroids (20 MB, scaling slowly with corpus size), making it practical for modern devices.
• Acceptable Search Quality with Room for Growth: While not yet matching commercial giants, Tiptoe's search quality is acceptable, comparable to TF-IDF, and is poised to improve as underlying machine learning models and clustering algorithms advance.
• Broad Applicability of Core Protocol: The underlying private nearest-neighbor search protocol is highly versatile and can be adapted to secure other privacy-sensitive applications, such as recommendation engines, private advertising, and other forms of private information retrieval.

About the Speaker(s)

Alexandra Henzinger is a fourth-year PhD student at MIT, actively involved in both the Parallel and Distributed Operating Systems and the Computer Systems Security research groups. Her academic pursuits focus on computer systems and cryptography, with a particular emphasis on private information retrieval, the design and implementation of cryptographic protocols, and private search engines. Alexandra also plays a key role in organizing the MIT security seminar. Prior to her doctoral studies at MIT, she graduated with honors from Stanford University, earning a Bachelor's degree in Computer Science.

This work was conducted in collaboration with Emma Domerman from Burnley, and Henry Corgan Gibbons and Nicholls Zelovic from MIT.