Efficient Techniques for Privacy-Preserving Sharing of Sensitive Information

Emiliano De Cristofaro, Yanbin Lu, Gene Tsudik

TL;DR

This paper introduces Privacy-Preserving Sharing of Sensitive Information (PPSSI), a framework for securely sharing data between parties without revealing more than necessary. They propose two efficient instantiations that address challenges in real-world database querying, offering practical solutions for scenarios like law enforcement investigations and healthcare data sharing.

What Problem Does This Paper Address?

In our increasingly digital world, there's a constant tension between the need to protect sensitive information and the necessity of sharing it for various purposes, from national security to social networking. Imagine a scenario where a government agency (like the FBI) needs to query a database held by another entity (like a local police department or a hospital) to find specific information about an individual. The challenge is to enable this query without the querying party revealing why they are interested in that specific data, and without the data holder revealing more information than requested. This is particularly tricky because simply sharing raw data or using standard database queries can lead to privacy leaks, unauthorized access, and potential liability. The paper tackles this by developing techniques that act as a "privacy shield," ensuring that parties only learn what they are entitled to.

Methods

The core of the proposed solutions, called Privacy-Preserving Sharing of Sensitive Information (PPSSI), relies on Private Set Intersection (PSI) techniques. PSI allows two parties to find the common elements in their respective sets without revealing anything beyond the intersection itself. The paper extends this concept to database querying.

The authors propose two main approaches:

  1. First PPSSI Approach: This method uses a novel database encryption technique combined with (A)PSI-DT (Authorized Private Set Intersection with Data Transfer) protocols without pre-distribution. This ensures both server unlinkability (the server can't tell if the client queried the same thing twice) and forward security (future authorizations don't compromise past privacy). The server encrypts its database, and the client uses "tokens" derived from its query to retrieve matching records.
  2. Second PPSSI Approach (for Very Large Databases): To address bandwidth and liability concerns with very large datasets, this approach introduces an "Isolated Box" (IB). The IB is a non-colluding, untrusted third party that stores the server's encrypted database. The server encrypts its data and sends it to the IB. The client then interacts with the server to generate query tokens and with the IB to retrieve matching records. This approach uses (A)PSI-DT protocols with pre-distribution, meaning the server can pre-process its data.

Both approaches employ specific encryption and hashing techniques to ensure that even if parts of the data are leaked, the sensitive information remains protected. They also introduce mechanisms like counters to handle multi-sets (duplicate values in the database) and data pointers to prevent linking records.

Datasets

The paper does not mention specific real-world datasets used for training. Instead, it focuses on evaluating the performance of its proposed techniques using simulated databases with varying sizes and attributes. They create a test database with 100,000 records and 45 searchable attributes for comparing their second approach against MySQL.

Key Insights and Ideas

  • PSI as a Foundation: The paper demonstrates how the fundamental concept of Private Set Intersection can be adapted and extended to solve complex real-world data sharing problems in database querying.
  • The "Privacy Shield" Concept: PPSSI acts as a cryptographic layer that protects sensitive information during data exchange, ensuring minimal disclosure.
  • Addressing Multi-Sets and Data Pointers: The authors tackle crucial challenges in database querying that naive PSI adaptations struggle with: handling duplicate values (multi-sets) and securely referencing records (data pointers) without leaking information.
  • The "Isolated Box" for Scalability: The introduction of the Isolated Box is a clever architectural innovation to handle very large databases, offloading storage and retrieval to a trusted third party and mitigating bandwidth and liability issues.
  • Trade-offs in Privacy and Efficiency: The paper highlights the inherent trade-offs between different privacy guarantees (e.g., unlinkability, forward security) and computational/communication overhead, offering distinct solutions for different scenarios.

Key Results

  • Efficiency: The proposed PPSSI techniques incur relatively low overhead. The first approach is shown to be about 10% slower than standard MySQL for total query time.
  • Scalability: The techniques are designed to scale efficiently with larger databases and query sets, exhibiting linear complexity for most operations.
  • Performance Comparison: The first PPSSI approach is significantly more efficient than existing single-database Private Information Retrieval (PIR) schemes like GR-PIR.
  • Security Guarantees: The paper provides formal security definitions and proofs for its approaches, demonstrating security against Honest-but-Curious and, in some cases, malicious adversaries.

Limitations and Future Work

  • Collusion: The authors acknowledge that if the server and the Isolated Box collude, client privacy is lost. Similarly, if the client and the IB collude, the client could potentially access the entire encrypted database, raising liability concerns.
  • Server Unlinkability vs. IB: Server Unlinkability is protected with respect to the client, but not necessarily with respect to the IB, as the IB might learn about database changes.
  • Query Types: The current approaches primarily support equality and disjunctive queries. Enabling conjunctive queries would require an exponential increase in client input, which is a significant challenge.
  • Dynamic Databases: While the second approach can handle dynamic databases with modifications, managing updates and deletions adds complexity.
  • Future Work: The authors suggest exploring support for versatile query predicates (like conjunctive queries) and fuzzy queries over non-normalized data. They also mention that selective failure is not considered and is left as future work.

Summary updated

BibTeX
@article{cristofaro2011efficient,
  author = {Emiliano De Cristofaro and Yanbin Lu and Gene Tsudik},
  title = {{Efficient Techniques for Privacy-Preserving Sharing of Sensitive Information}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2011},
  url = {https://openreview.net/forum?id=lu0S5a_Y1e},
}

Loading related content...

Figure