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.
Introduction
In modern cloud-based data management, there is a growing need to verify properties of data without compromising the privacy of the underlying dataset. While Zero-Knowledge Sets (ZKS) allow provers to verify membership without revealing the set's contents, they typically fail to handle ordered data efficiently. Standard Authenticated Data Structures, such as Merkle trees, often leak metadata through their proof paths, potentially revealing an element's exact rank or the total size of the list. This leakage is unacceptable in sensitive domains like private auctions, financial auditing, or corporate performance comparisons.
This paper addresses this gap by introducing two novel cryptographic models: Zero-Knowledge Lists (ZKL) and Privacy-Preserving Authenticated Lists (PPAL). These frameworks enable "leakage-free" order queries, allowing a user to learn that "Element A precedes Element B" without discovering the list's total size, the elements' actual ranks, or information about any other items in the set.
Methodology
The authors propose two distinct frameworks tailored for different operational contexts:
Zero-Knowledge List (ZKL)
The ZKL model is a two-party scheme (Prover and Verifier) that extends Zero-Knowledge Sets by incorporating homomorphic integer commitments. To prove that element $x$ precedes $y$, the prover demonstrates that the difference between their committed ranks ($rank(y) - rank(x) - 1$) is a non-negative integer. This proof is conducted entirely within a zero-knowledge framework, ensuring no rank values are leaked.
Privacy-Preserving Authenticated List (PPAL)
The PPAL model is a three-party architecture (Owner, Server, and Client) optimized for cloud environments. It utilizes several advanced cryptographic primitives:
- Blinded Bilinear Accumulators: Element ranks are encoded into member witnesses and blinded with randomness to prevent information "stitching" across multiple queries.
- Bilinear Maps: These allow the client to verify the mathematical relationship (order) between elements using blinded witnesses without learning actual ranks or blinding factors.
- Bilinear Aggregate Signatures: This technique enables the server to combine multiple signatures into a single, compact proof, significantly enhancing batch query efficiency.
Performance and Results
The proposed models were evaluated through rigorous asymptotic complexity analysis. The PPAL construction, in particular, demonstrates significant efficiency gains over existing redactable signature schemes.
As shown in the comparison table, PPAL achieves a proof size and verification time of $O(m)$, where $m$ is the number of elements in the query. This is a substantial improvement over previous schemes that often required $O(n^2)$ storage or time. Furthermore, the server-side query time is optimized to $O(\min(m \log n, n))$, making it highly practical for large-scale cloud databases.
Key insights from the analysis include:
- Rank as a Secret: Treating the position of an item as a committed secret allows for proving order through differences without revealing absolute values.
- Efficiency Trade-offs: While ZKL provides a robust two-party model, it is computationally intensive. PPAL achieves massive speedups by assuming a trusted data owner, scaling linearly with query size rather than the entire element universe.
Conclusion and Future Work
The ZKL and PPAL models provide a strong foundation for verifiable, privacy-preserving order queries. Both models are proven to be complete (honest proofs always work), sound (malicious servers cannot fake an order), and zero-knowledge (no information leakage beyond the query result).
However, some limitations remain. The high efficiency of PPAL relies on a trusted data owner during the initial setup. Additionally, the current constructions focus on static lists; future research could focus on developing efficient mechanisms for dynamic lists where elements are frequently added or reordered. Finally, while the security proofs are robust within the Random Oracle Model, exploring proofs in the Standard Model would provide even stronger security guarantees.
Summary updated