Private Web Search with Tiptoe

on YouTube ↗40m

" summary

Tiptoe claims cryptographic query privacy: servers learn nothing about queries or returned URLs by combining semantic embeddings and an additively homomorphic scheme (implemented with SimplePIR) plus clustering. The prototype searches ~360M pages with ~3s median latency, ~hundreds core-seconds server work per query, ~60 MB client↔server traffic, and ~0.3 GB client storage. It shows ~6,000× less compute and ~60× less bandwidth than Coeus but ranks ground-truth results at ~7.7 (vs ~2 for top nonprivate models) and struggles with rare-string lookups.

AI-written summary · about

" chapters (31)

1. 0:00Introduction
2. 1:03Private web search importance
3. 4:57Limitations of private search
4. 5:41Tiptoe private search engine
5. 7:05Search as nearest-neighbor problem
6. 8:09Tiptoe architecture and ranking
7. 9:12Semantic embeddings for search
8. 12:02Client-side clustering for search
9. 13:46Homomorphic encryption for matrix ops
10. 16:21Tiptoe nearest-neighbor protocol
11. 17:22Server costs and SimplePIR
12. 18:04Tiptoe system workflow
13. 19:07Performance on 360M pages
14. 20:55Search quality vs non-private
15. 22:20Tiptoe results and limits
16. 23:04Future of private search
17. 24:05Q&A
18. 24:50Client storage needs
19. 25:31Cluster selection and queries
20. 26:55Security assumptions
21. 28:03Weighted cluster requests
22. 29:47Side channels and memory access
23. 31:09Why not download the entire database?
24. 32:14Balancing encrypted query and response sizes
25. 33:19Design trade-offs and crypto choices
26. 34:01Combining crypto with ML
27. 35:05Privacy beyond web search
28. 36:33Linear scan necessity
29. 37:56Sublinear PIR future
30. 38:38Next steps for Tiptoe
31. 39:20Closing remarks

" related talks

• 18mPrivacy-Preserving Web SearchLara Perinetti · Berlin Buzzwords 2023
• 36mThe Forbidden Index: How We Turned OpenSearch Into a Privacy-Preserving SuperheroU. Mishra, A. Khanna · OpenSearchCon Europe 2026
• 27mMetadata-private data transferWill Scott · Protocol Berg 2023
• 46mPrivacy Preserving IoTChristopher J Biggs · linux.conf.au 2020
• 14mToward Provably Private Insights into AI UsePeter Kairouz, Daniel Ramage, Albert Cheu, Rakshita Tandon, Artem Lagzdin, Brett McLarnon, Katharine Daly, Marco Gruteser, Stanislav Chiknavaryan, Timon Van Overveldt, Zoe Gong · PEPR '26
• 45mChallenges in Scaling Privacy Enhancing Technologies to Campus Level IoT TestbedSharad Mehrotra · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)
• 01h 16mCommercial opportunities for designing privacy in: Embedding privacy ...John Borking, Casey Chappelle, Tom Ilube, Jason Pridmore · CPDP 2015
• 32mBLENDER: Enabling Local Search with a Hybrid Differential Privacy ModelBrendan Avent, Aleksandra Korolova, David Zeber, Torgeir Hovden, Benjamin Livshits · 26th USENIX Security Symposium (USENIX Security '17)