Splinter: Practical Private Queries on Public Data

Authors: 

Frank Wang, Catherine Yun, Shafi Goldwasser, and Vinod Vaikuntanathan, MIT CSAIL; Matei Zaharia, Stanford InfoLab

Abstract: 

Many online services let users query public datasets such as maps, flight prices, or restaurant reviews. Unfortunately, the queries to these services reveal highly sensitive information that can compromise users’ privacy. This paper presents Splinter, a system that protects users’ queries on public data and scales to realistic applications. A user splits her query into multiple parts and sends each part to a different provider that holds a copy of the data. As long as any one of the providers is honest and does not collude with the others, the providers cannot determine the query. Splinter uses and extends a new cryptographic primitive called Function Secret Sharing (FSS) that makes it up to an order of magnitude more efficient than prior systems based on Private Information Retrieval and garbled circuits. We develop protocols extending FSS to new types of queries, such as MAX and TOPK queries. We also provide an optimized implementation of FSS using AES-NI instructions and multicores. Splinter achieves end-to-end latencies below 1.6 seconds for realistic workloads including a Yelp clone, flight search, and map routing.

NSDI '17 Open Access Videos Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

Presentation Video

Download Video

Presentation Audio

BibTeX
@inproceedings {201469,
author = {Frank Wang and Catherine Yun and Shafi Goldwasser and Vinod Vaikuntanathan and Matei Zaharia},
title = {Splinter: Practical Private Queries on Public Data},
booktitle = {14th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 17)},
year = {2017},
isbn = {978-1-931971-37-9},
address = {Boston, MA},
pages = {299--313},
url = {https://www.usenix.org/conference/nsdi17/technical-sessions/presentation/wang-frank},
publisher = {{USENIX} Association},
}