Verifiable Member and Order Queries on a List in Zero-Knowledge
This addresses the need for privacy-preserving authenticated data structures in cloud applications, offering a novel model for zero-knowledge queries on ordered sets.
The paper tackles the problem of performing verifiable membership and order queries on lists stored in an untrusted cloud while preserving data integrity and privacy, resulting in an efficient construction based on bilinear accumulators and maps that is provably secure and zero-knowledge.
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.