Cryptology ePrint Archive: Report 2014/632
Verifiable Member and Order Queries on a List in Zero-Knowledge
Esha Ghosh and Olga Ohrimenko and Roberto Tamassia
Abstract: We introduce a formal model for order queries on lists in zero knowledge in the traditional authenticated data structure model.
We call this model Privacy-Preserving Authenticated List (PPAL).
In this model, the queries are performed on the list stored in the (untrusted) cloud where data integrity and privacy have to
be maintained. To realize an efficient authenticated data structure, we first adapt consistent data query model.
To this end we introduce a formal model called Zero-Knowledge List (ZKL) scheme which generalizes consistent membership queries in zero-knowledge
to consistent membership and order queries on a totally ordered set in zero knowledge. We present a construction of ZKL based on zero-knowledge set
and homomorphic integer commitment scheme. Then we discuss why this construction is not as efficient as desired in cloud applications and
present an efficient construction of PPAL based on bilinear accumulators and bilinear maps which is provably secure and zero-knowledge.
Category / Keywords: zero-knowledge consistent query datastructure, zero-knowledge list,privacy-preserving authenticated data structure, integrity, bilinear accumulators, bilinear aggregate signature, redactable signatures, cloud security
Date: received 17 Aug 2014, last revised 17 Aug 2014
Contact author: esha_ghosh at brown edu
Available format(s): PDF | BibTeX Citation
Version: 20140821:010459 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]