Verifiable Privacy-Preserving Member and Order Queries on a List

Esha Ghosh, Olga Ohrimenko, Roberto TamassiaarXiv 2014 · DOI · arXiv

TL;DR

This paper introduces a novel framework for privacy-preserving authenticated lists, enabling clients to query list membership and element order without revealing sensitive information beyond the query itself. They present an efficient construction using bilinear accumulators and maps, offering strong integrity and privacy guarantees under standard cryptographic assumptions.

What Problem Does This Paper Address?

In cloud computing, users often outsource data storage and processing to untrusted servers. Authenticated Data Structures (ADS) provide a way for clients to verify the integrity of data and query results returned by the server. However, traditional ADS often leak more information than necessary. For instance, a proof of membership might reveal the element's rank in a sorted list, or a proof of non-membership might reveal adjacent elements. This leakage compromises user privacy. This paper addresses this gap by proposing a "privacy-preserving authenticated list" (PPAL) that ensures proofs reveal only the requested information, not extraneous details about the list's structure or content. This is crucial for applications dealing with sensitive data, like medical records or financial information, where partial results are allowed but full data exposure is not.

Methods

The authors propose a PPAL scheme built upon two core cryptographic primitives:

  • Bilinear Aggregate Signature Scheme: This allows for efficient aggregation of multiple signatures into a single, short signature. This is leveraged to create a compact digest signature for the entire list and sublists, enabling efficient integrity verification.
  • Bilinear Accumulators: These are used to construct "member witnesses" for each element in the list. These witnesses, combined with randomization, allow for encoding the element's rank without revealing it directly.

The construction involves a three-party setup: the owner (who creates the list and authentication information), the server (who stores the list and answers queries), and the client (who issues queries and verifies responses).

Key algorithms include:

  • KeyGen: Generates secret and public keys.
  • Setup: The owner generates authentication information (member witnesses, order witnesses, digest signature) for the list.
  • MemberQuery: The server, given a query element, returns a proof of its membership.
  • OrderQuery: The server, given two or more elements, returns them in their correct order within the list, along with a proof of this ordering.
  • MemberVerify: The client verifies the membership proof.
  • OrderVerify: The client verifies both the membership and the order proof.

The scheme's privacy is achieved by ensuring that the proofs (member and order witnesses) are constructed in a way that hides the actual rank of elements and only reveals relative order information that can be transitively inferred from the query results.

Datasets

Not discussed in the paper. The paper focuses on a theoretical construction for an abstract ordered list.

Key Insights and Ideas

  • Privacy Beyond Integrity: The paper highlights that traditional ADS focus on integrity but often fail on privacy. They formalize "privacy-preserving authenticated data structure" by introducing the concept of "obliviousness," ensuring proofs don't leak information beyond the query answer.
  • Hiding Rank and Revealing Order: A core challenge is to prove an element's membership and its relative order with other elements without revealing its exact position (rank) in the list. The use of randomized bilinear accumulators and carefully constructed order witnesses addresses this.
  • Transitive Inference is Allowed: The privacy definition allows clients to infer order relationships if they can be derived transitively from multiple queries. This is a practical and necessary aspect of order queries.
  • Efficiency with Bilinear Maps: The construction leverages the power of bilinear maps and aggregate signatures to achieve efficient proofs and verification, aiming for linear time and space complexity.

Key Results

The paper presents a formal model for privacy-preserving authenticated lists and provides an efficient construction that achieves:

  • Integrity: Proofs forged by a malicious server will be detected by the client.
  • Context Obliviousness: The client cannot learn information about the list beyond what is explicitly queried.
  • Relative Order Obliviousness: The client cannot infer non-transitive order relationships between elements not explicitly queried.
  • Efficiency: The construction aims for linear time and space complexity for the owner and server, and sublinear (proportional to query size) for the client's verification. The paper includes a comparison table showing their construction outperforms previous work in terms of performance and assumptions.

Limitations and Future Work

The authors acknowledge the following:

  • Static List: The current construction is for static lists. Future work could explore dynamic behavior, allowing for updates to the list while maintaining privacy and integrity.
  • Non-Membership Proofs: The paper focuses on membership and order queries, not non-membership proofs. Extending the scheme to support privacy-preserving non-membership proofs is a direction for future research.
  • Random Oracle Model: The security proofs are given in the random oracle model, which is a standard but idealized assumption. Future work might explore constructions that rely on weaker or standard cryptographic assumptions.
  • Other Data Structures: The paper focuses on lists. Extending these concepts to other data structures like trees or graphs for privacy-preserving authenticated queries is a promising avenue.

Summary updated

Abstract

We introduce a formal model for membership and order queries on privacy-preserving authenticated lists. In this model, the queries are performed on the list stored in the cloud where data integrity and privacy have to be maintained. We then present an efficient construction of privacy-preserving authenticated lists based on bilinear accumulators and bilinear maps, analyze the performance, and prove the integrity and privacy of this construction under widely accepted assumptions.
BibTeX
@misc{ghosh2014verifiable,
  author = {Esha Ghosh and Olga Ohrimenko and Roberto Tamassia},
  title = {{Verifiable Privacy-Preserving Member and Order Queries on a List}},
  year = {2014},
  eprint = {1405.0962},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1405.0962},
}
Figure