TL;DR
This paper introduces Privacy-Preserving Sharing of Sensitive Information (PPSSI), a framework for securely querying databases without revealing sensitive information to either party. They propose two efficient instantiations that offer strong privacy guarantees with minimal performance overhead, making them practical for real-world applications.
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. Imagine scenarios like law enforcement needing data from various agencies without revealing their investigative interests, or healthcare providers needing patient information without exposing other patients' data. The core challenge is enabling controlled data sharing where parties only learn what they are explicitly entitled to, without leaking any additional private information, and doing so efficiently enough for practical use. Existing methods often fall short, either by being too computationally expensive or by not offering robust privacy guarantees for both parties.
Methods
The paper's core contribution is the development of Privacy-Preserving Sharing of Sensitive Information (PPSSI) and its concrete instantiations. The foundation of their approach lies in Private Set Intersection (PSI) techniques, specifically variants that support data transfer (PSI-DT) and authorized queries (APSI-DT).
They propose two main PPSSI approaches:
- First PPSSI Approach: This approach builds upon (A)PSI-DT protocols without pre-distribution. It introduces a novel database encryption technique that uses counters to handle duplicate values (addressing the "multi-set" challenge) and encrypted pointers to obscure the direct link between query tokens and records (addressing the "data pointer" challenge). This method prioritizes strong privacy guarantees, including Server Unlinkability and Forward Security.
- Second PPSSI Approach (for Very Large Databases): To tackle bandwidth and liability concerns with 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 pre-processes its data and encrypts it for the IB. The client then interacts with the server to generate query tokens and uses the IB to retrieve matching records. This approach leverages (A)PSI-DT protocols with pre-distribution, allowing the server to perform token computations offline.
Datasets
Not discussed in the paper. The paper focuses on a generic database querying scenario and uses simulated data for performance evaluation.
Key Insights and Ideas
- The "Multi-set" and "Data Pointer" Challenges: The paper clearly articulates two critical issues that arise when naively applying PSI to database querying: how to handle duplicate values in a database without revealing distribution patterns, and how to avoid linking query tokens to specific records when using encrypted data pointers.
- The "Isolated Box" for Scalability: Introducing a dedicated, untrusted third party (the Isolated Box) is a clever way to offload storage and retrieval of encrypted data, significantly improving performance and addressing liability concerns for large databases.
- Balancing Privacy and Efficiency: The authors demonstrate that it's possible to achieve strong privacy guarantees (like Server Unlinkability and Forward Security) while maintaining low computational and communication overhead, often comparable to or only slightly higher than standard database operations.
- PSI-DT as a Building Block: The paper effectively shows how PSI-DT and APSI-DT, with careful adaptation, can serve as robust building blocks for complex privacy-preserving data sharing scenarios beyond simple set intersection.
Key Results
- Low Overhead: The first PPSSI approach incurs about 10% higher overhead than standard MySQL for query processing.
- Scalability: All proposed operations (Token computation, encryption, lookup) have linear complexity with respect to database size and query size, indicating good scalability.
- Performance Comparison: The first PPSSI approach is shown to be significantly more efficient than existing single-database Private Information Retrieval (PIR) schemes like GR-PIR, especially when considering computation overhead.
- Practicality: Extensive experimental results attest to the practicality of the attained privacy features and their low overhead.
Limitations and Future Work
- Collusion: The paper acknowledges that collusion between parties (server and IB, or client and IB) can compromise privacy.
- Dynamic Databases: While the second approach can handle dynamic databases with modifications, it requires storing maximum counters, which can be substantial.
- Query Types: The current PPSSI approaches primarily support equality and disjunctive queries. Enabling conjunctive queries would lead to an exponential increase in client input size, which is a significant challenge.
- Selective Failure: The protocols do not currently consider selective failure, which is left as future work.
- Future Work: The authors suggest extending PPSSI to support versatile query predicates (e.g., conjunctive queries) and fuzzy queries over non-normalized data. They also mention the possibility of replacing the online server with a tamper-proof smartcard to further enhance security and allow the server to go offline.
Summary updated