Paper 2016/1148

Splinter: Practical Private Queries on Public Data

Frank Wang, Catherine Yun, Shafi Goldwasser, Vinod Vaikuntanathan, and Matei Zaharia

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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. 14th USENIX Symposium on Networked Systems Design and Implementation
Keywords
function secret sharingprivacyimplementation
Contact author(s)
frankw @ mit edu
History
2017-02-24: last of 2 revisions
2016-12-21: received
See all versions
Short URL
https://ia.cr/2016/1148
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1148,
      author = {Frank Wang and Catherine Yun and Shafi Goldwasser and Vinod Vaikuntanathan and Matei Zaharia},
      title = {Splinter: Practical Private Queries on Public Data},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1148},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1148}},
      url = {https://eprint.iacr.org/2016/1148}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.