Verifiable Member and Order Queries on a List in Zero-Knowledge

Esha Ghosh, Olga Ohrimenko, Roberto Tamassia

TL;DR

This paper introduces two novel cryptographic models—Zero-Knowledge Lists (ZKL) and Privacy-Preserving Authenticated Lists (PPAL)—that allow a prover to verify the relative order of elements in a list without revealing anything else. These constructions enable "leakage-free" queries, meaning a user can 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.

What Problem Does This Paper Address?

In many real-world scenarios, we need to prove something about data without revealing the data itself. While "Zero-Knowledge Sets" allow you to prove an item belongs to a group without revealing the group's contents, they don't handle ordered data well.

Standard Authenticated Data Structures (like Merkle trees) often leak "metadata." For example, if you use a sorted Merkle tree to prove someone is on a list, the proof's path might inadvertently reveal their exact rank or the total number of people on that list. This is a problem for sensitive applications like:

  • Auctions: Proving a bid was lower than the winner's without revealing the winning bid or how many people participated.
  • Finance: Proving a bank balance is above a certain threshold without revealing the exact balance or the user's transaction history.
  • Corporate Privacy: Allowing regional divisions to compare their sales performance against others without seeing the actual sales figures of their competitors.

The authors aim to bridge this gap by creating a system that supports verifiable order queries while maintaining strict zero-knowledge privacy.

Methods

The authors propose two distinct frameworks:

  1. Zero-Knowledge List (ZKL): A two-party model (Prover and Verifier). It builds on existing Zero-Knowledge Sets but adds homomorphic integer commitments. To prove that element $x$ precedes $y$, the prover demonstrates that the difference between their ranks ($rank(y) - rank(x) - 1$) is a non-negative integer, all within a zero-knowledge proof.
  2. Privacy-Preserving Authenticated List (PPAL): A three-party model (Owner, Server, and Client) optimized for cloud computing.
  3. Blinded Bilinear Accumulators: The core innovation here is encoding element ranks into "member witnesses" that are blinded with randomness.
  4. Bilinear Maps: These allow the client to verify the mathematical relationship (the order) between two elements using the blinded witnesses without ever learning the actual ranks or the blinding factors.
  5. Bilinear Aggregate Signatures: This allows the server to combine multiple signatures into a single, short proof, making batch queries highly efficient.

Datasets

The paper is a theoretical cryptographic study and does not use empirical datasets for training or benchmarking. Instead, it provides a rigorous asymptotic complexity analysis to prove efficiency. The performance is measured against the list size ($n$) and the query size ($m$).

Key Insights and Ideas

  • Rank as a Secret: The fundamental "aha" moment is treating the position (rank) of an item in a list as a secret value that can be committed to. By proving properties of the difference between these secrets, you can prove order without revealing the values themselves.
  • The Power of Blinding: In the PPAL model, the use of blinding factors ensures that even if a client makes multiple queries, they cannot "stitch" the information together to map out the list's structure.
  • Efficiency over Generality: The authors show that while ZKL is powerful, it is computationally expensive. By introducing the PPAL model (which assumes a trusted data owner), they achieve a massive speedup, moving from proofs that depend on the size of the entire "universe" of possible elements to proofs that scale linearly with the number of elements being queried ($O(m)$).
  • Extensibility: The authors demonstrate that simple order queries are "atomic" building blocks. By combining them, they can support complex order statistics like finding the median, the maximum, or the "top-t" elements in zero-knowledge.

Key Results

  • PPAL Efficiency: The PPAL construction achieves a proof size and verification time of $O(m)$, where $m$ is the number of elements in the query. This is a significant improvement over previous "redactable signature" schemes that often required quadratic ($O(n^2)$) storage or time.
  • Server Performance: The server can answer queries and generate proofs in $O(\min(m \log n, n))$ time, making it practical for large-scale cloud databases.
  • Security Guarantees: 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).

Limitations and Future Work

  • Trusted Owner Requirement: The highly efficient PPAL model relies on the data owner being trusted to set up the system correctly. If the owner is malicious, the privacy guarantees could be compromised.
  • Static Lists: The current constructions focus on static lists. While the paper mentions that updates could be handled, it does not provide a detailed, efficient mechanism for dynamic lists where elements are frequently added or reordered.
  • Random Oracle Model: The security proofs are conducted in the "Random Oracle Model," a standard but idealized mathematical assumption in cryptography. Future work could explore proofs in the "Standard Model" for even more robust security guarantees.

Summary updated

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.
BibTeX
@article{ghosh2014verifiable,
  author = {Esha Ghosh and Olga Ohrimenko and Roberto Tamassia},
  title = {{Verifiable Member and Order Queries on a List in Zero-Knowledge}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2014},
  url = {https://openreview.net/forum?id=PFs6XFgbIN7},
}

Loading related content...

Figure