International Association
for Cryptologic Research

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.