  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.

Cryptography and Security