Paper 2014/632

Verifiable Order Queries and Order Statistics on a List in Zero-Knowledge

Esha Ghosh, Olga Ohrimenko, and Roberto Tamassia

Abstract

Given a list L with n elements, an order query on L asks whether a given element x in L precedes or follows another element y in L. More generally, given a set of m elements from L, an order query asks for the set ordered according to the positions of the elements in L. We introduce two formal models for answering order queries on a list in a verifiable manner and in zero-knowledge. We also present efficient constructions for these models. Our first model, called \emph{zero-knowledge list} (ZKL), generalizes membership queries on a set to order queries on a list in zero-knowledge. We present a construction of ZKL based on zero-knowledge sets and a homomorphic integer commitment scheme. Our second model, \emph{privacy-preserving authenticated list} (PPAL), extends authenticated data structures by adding a zero-knowledge privacy requirement. In this model, a list is outsourced by a trusted owner to an untrusted cloud server, which answers order queries issued by clients. The server also returns a proof of the answer, which is verified by the client using a digest of the list obtained from the owner. PPAL supports the security properties of data integrity against a malicious server and privacy protection against a malicious client. Though PPAL can be implemented using our ZKL construction, this construction is not as efficient as desired in cloud applications. To this end, we present an efficient PPAL construction based on blinded bilinear accumulators and bilinear maps, which is provably secure and zero-knowledge (e.g., hiding even the size of the list). Our PPAL construction uses proofs of $O(m)$ size and allows the client to verify a proof in $O(m)$ time.~The owner executes the setup in $O(n)$ time and space. The server uses $O(n)$ space to store the list and related authentication information, and takes $O(\min(m\log n, n))$ time to answer a query and generate a proof. Both our ZKL and PPAL constructions have one round of communication and are secure in the random oracle model. Finally, we show that our ZKL and PPAL frameworks can be extended to support fundamental statistical queries (including maximum, minimum, median, threshold and top-t elements) efficiently and in zero-knowledge.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. Applied Cryptography and Network Security 2015
DOI
10.1007/978-3-319-28166-7_8
Keywords
order queriesorder statisticszero-knowledgeintegrityleakage-free redactable signaturescloud securitycloud-privacy
Contact author(s)
esha_ghosh @ brown edu
History
2016-03-11: last of 2 revisions
2014-08-21: received
See all versions
Short URL
https://ia.cr/2014/632
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/632,
      author = {Esha Ghosh and Olga Ohrimenko and Roberto Tamassia},
      title = {Verifiable Order Queries and Order Statistics on a List in Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2014/632},
      year = {2014},
      doi = {10.1007/978-3-319-28166-7_8},
      note = {\url{https://eprint.iacr.org/2014/632}},
      url = {https://eprint.iacr.org/2014/632}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.