Paper 2023/1438

Private Web Search with Tiptoe

Alexandra Henzinger, Massachusetts Institute of Technology
Emma Dauterman, UC Berkeley
Henry Corrigan-Gibbs, Massachusetts Institute of Technology
Nickolai Zeldovich, Massachusetts Institute of Technology

Tiptoe is a private web search engine that allows clients to search over hundreds of millions of documents, while revealing no information about their search query to the search engine’s servers. Tiptoe’s privacy guarantee is based on cryptography alone; it does not require hardware enclaves or non-colluding servers. Tiptoe uses semantic embeddings to reduce the problem of private full-text search to private nearest-neighbor search. Then, Tiptoe implements private nearest-neighbor search with a new, high-throughput protocol based on linearly homomorphic encryption. Running on a 45-server cluster, Tiptoe can privately search over 360 million web pages with 145 core-seconds of server compute, 56.9 MiB of client-server communication (74% of which occurs before the client enters its search query), and 2.7 seconds of end-to-end latency. Tiptoe’s search works best on conceptual queries (“knee pain”) and less well on exact string matches (“123 Main Street, New York”). On the MS MARCO search-quality benchmark, Tiptoe ranks the best-matching result in position 7.7 on average. This is worse than a state-of-the-art, non-private neural search algorithm (average rank: 2.3), but is close to the classical tf-idf algorithm (average rank: 6.7). Finally, Tiptoe is extensible: it also supports private text-to-image search and, with minor modifications, it can search over audio, code, and more.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. SOSP 2023
Private web search
Contact author(s)
ahenz @ csail mit edu
edauterman @ berkeley edu
henrycg @ csail mit edu
nickolai @ csail mit edu
2023-09-29: revised
2023-09-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexandra Henzinger and Emma Dauterman and Henry Corrigan-Gibbs and Nickolai Zeldovich},
      title = {Private Web Search with Tiptoe},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1438},
      year = {2023},
      doi = {10.1145/3600006.3613134},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.