按年被提到
20242025 · 2 次2026
系统、数据库与网络›互联网协议与匿名网络·arXiv:2406.06761 · cs.CR

Wally: Batched Private Nearest Neighbor Search at Scale

Hilal Asi, Fabian Boemer, Nicholas Genise, Muhammad Haris Mughees, Tabitha Ogilvie, Rehan Rishi, Kunal Talwar, Karl Tarbe, Akshay Wadia, Ruiyu Zhu, Marco Zuliani · 2024
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2024-12-30 · 最近 2025-01-15
3不同的人
2活跃月份
3讨论串
4被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We present Wally, a batched private nearest-neighbor search protocol that uses differential privacy to break the linear computation barrier of fully-oblivious schemes. In Tiptoe, the server must process the entire database per query to hide the access pattern, resulting in low throughput (909 QPS) and high communication (17.4 MB) on a 3.2M-entry database. Sublinear alternatives like Pacmann require 614 MB of client storage and an offline streaming phase. Wally's key insight is that fully-oblivious schemes are prohibitively expensive at scale, but the same scale also provides an opportunity. Large-scale systems naturally have many concurrent clients. Wally batches queries from non-coordinating clients, each independently adding fake queries to hide which clusters it accesses. The fake query counts follow a negative binomial distribution, which is non-negative and infinitely divisible, allowing independent sampling without coordination. Clients send queries at random times through an existing anonymization service, avoiding a centralized shuffler. The server sees only an anonymized, noisy stream of cluster accesses that is provably (epsilon, delta)-differentially private, computing over only the relevant clusters. The client encrypts its query under SHE so the server returns only encrypted similarity scores. On a 3.2M-entry database with 500K-query batches, Wally achieves 7-29x higher throughput and 6.7-31x lower communication than Tiptoe, and 15,000x lower client storage than Pacmann, with strong (epsilon=0.1, delta=2^{-26})-DP and comparable accuracy. We also propose optimizations to SHE and keyword PIR yielding 2-3x improvements in PIR and 20-25% in BFV operations, and release an open-source BFV library in Swift.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论internetter · 2024-12

“I don't completely understand the maths of how this works, but no, they don't. Here's a theoretical way I wrote in another comment: > I think they have more efficient ways, but theoretically what you could do is apply each row in your database to this encrypted value, in such a way that the encrypted value becomes the name of the POI of the best match, …”

Apple Photos phones home on iOS 18 and macOS 15原评论 ↗
评论abalone · 2025-01

“This has gone a bit under the radar but Apple went and built a private search engine that doesn’t know what you’re searching for. It’s called Wally and it powers queries like caller ID and landmark recognition in photos. * Homomorphic encryption is nothing short of dark magic that makes it impossible for the server to know what you are searching for or w…”

Apple built a search engine using homomorphic encryption原评论 ↗
被提交为 story · 1 次