Efficient Verifiable Range and Closest Point Queries in Zero-Knowledge
Authors: Esha Ghosh (Dept. of Computer Science, Brown University, Providence RI, USA), Olga Ohrimenko (Microsoft Research), Roberto Tamassia (Dept. of Computer Science, Brown University, Providence RI, USA)
Volume: 2016
Issue: 4
Pages: 373–388
DOI: https://doi.org/10.1515/popets-2016-0045
Abstract: We present an efficient method for answering one-dimensional range and closest-point queries in a verifiable and privacy-preserving manner. We consider a model where a data owner outsources a dataset of keyvalue pairs to a server, who answers range and closestpoint queries issued by a client and provides proofs of the answers. The client verifies the correctness of the answers while learning nothing about the dataset besides the answers to the current and previous queries. Our work yields for the first time a zero-knowledge privacy assurance to authenticated range and closest-point queries. Previous work leaked the size of the dataset and used an inefficient proof protocol. Our construction is based on hierarchical identity-based encryption. We prove its security and analyze its efficiency both theoretically and with experiments on synthetic and real data (Enron email and Boston taxi datasets).
Keywords: cloud privacy, security, efficient outsourced computation, public verifiability, zero-knowledge authenticated range queries, hierarchical identity based encryption
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
