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 ]