Saved in:
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.06761 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909564299902976 |
|---|---|
| author | Asi, Hilal Boemer, Fabian Genise, Nicholas Mughees, Muhammad Haris Ogilvie, Tabitha Rishi, Rehan Talwar, Kunal Tarbe, Karl Wadia, Akshay Zhu, Ruiyu Zuliani, Marco |
| author_facet | Asi, Hilal Boemer, Fabian Genise, Nicholas Mughees, Muhammad Haris Ogilvie, Tabitha Rishi, Rehan Talwar, Kunal Tarbe, Karl Wadia, Akshay Zhu, Ruiyu Zuliani, Marco |
| contents | This paper presents Wally, a private search system that supports efficient search queries against large databases. When sufficiently many clients are making queries, Wally's performance is significantly better than previous systems while providing a standard privacy guarantee of $(ε, δ)$-differential privacy.
Specifically, for a database with 3.2 million entries, Wally's queries per second (QPS) is 7-28x higher, and communication is 6.69-31x smaller than Tiptoe, a state-of-the-art private search system. In Wally, each client adds a few fake queries and sends each query via an anonymous network to the server at independently chosen random instants. We also use somewhat homomorphic encryption (SHE) to reduce the communication size.
The number of fake queries each client makes depends inversely on the number of clients making queries. Therefore, the overhead of fake queries vanishes as the number of honest clients increases, enabling scalability to millions of queries and large databases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_06761 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Scalable Private Search with Wally Asi, Hilal Boemer, Fabian Genise, Nicholas Mughees, Muhammad Haris Ogilvie, Tabitha Rishi, Rehan Talwar, Kunal Tarbe, Karl Wadia, Akshay Zhu, Ruiyu Zuliani, Marco Cryptography and Security Databases This paper presents Wally, a private search system that supports efficient search queries against large databases. When sufficiently many clients are making queries, Wally's performance is significantly better than previous systems while providing a standard privacy guarantee of $(ε, δ)$-differential privacy. Specifically, for a database with 3.2 million entries, Wally's queries per second (QPS) is 7-28x higher, and communication is 6.69-31x smaller than Tiptoe, a state-of-the-art private search system. In Wally, each client adds a few fake queries and sends each query via an anonymous network to the server at independently chosen random instants. We also use somewhat homomorphic encryption (SHE) to reduce the communication size. The number of fake queries each client makes depends inversely on the number of clients making queries. Therefore, the overhead of fake queries vanishes as the number of honest clients increases, enabling scalability to millions of queries and large databases. |
| title | Scalable Private Search with Wally |
| topic | Cryptography and Security Databases |
| url | https://arxiv.org/abs/2406.06761 |