Scalable Private Search with Wally

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Asi, Hilal, Boemer, Fabian, Genise, Nicholas, Mughees, Muhammad Haris, Ogilvie, Tabitha, Rishi, Rehan, Talwar, Kunal, Tarbe, Karl, Wadia, Akshay, Zhu, Ruiyu, Zuliani, Marco
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Cryptography and Security Databases
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

_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