Paper 2015/1183

Authenticated Range \& Closest Point Queries in Zero-Knowledge

Esha Ghosh, Olga Ohrimenko, and Roberto Tamassia

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 key-value pairs to a server, who answers range and closest-point 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
zero-knowledge datastructuressecure data outsourcinghierarchical identitiy based encryptionimplementation
Contact author(s)
esha_ghosh @ brown edu
History
2015-12-13: received
Short URL
https://ia.cr/2015/1183
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1183,
      author = {Esha Ghosh and Olga Ohrimenko and Roberto Tamassia},
      title = {Authenticated Range \& Closest Point Queries in Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1183},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1183}},
      url = {https://eprint.iacr.org/2015/1183}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.