Abstract
Lack of trust between organizations and privacy concerns regarding their data are significant impediments to collaborative data analysis. We propose DataRing, a data-sharing system that enables mutually mistrusting participants to query each other's datasets in a privacy-preserving manner. Crucially, DataRing ensures the correctness of input datasets and query answers even when participants attempt to cheat by deviating from their true data. By leveraging differential privacy and a suite of cryptographic tools, DataRing maintains individual privacy and data confidentiality. Our evaluation demonstrates that the system can process 10 queries on a dataset with 500,000 records in approximately 90 seconds while detecting cheating with high accuracy.
Introduction: The Challenge of Trust and Privacy
In sectors such as healthcare and finance, joint data analytics can unlock transformative insights. However, two major hurdles persist: privacy (protecting individual records) and trust (ensuring participants provide truthful data). While many existing systems handle "honest-but-curious" actors, they often fail against "malicious" participants who might intentionally provide fake datasets to protect business interests while benefiting from others' data.
The DataRing Methodology
DataRing addresses these challenges through a multi-phase approach designed to detect and deter cheating without compromising privacy.
1. Setup Phase
Two non-colluding servers generate a collective public key using Elliptic Curve ElGamal (EC-ElGamal). This additive homomorphic encryption allows servers to perform computations on encrypted data without ever accessing the raw values.
2. Partial View Phase
To prevent participants from using entirely fabricated datasets, they must submit an encrypted random sample of their data, known as a "Partial View." The system verifies this sample against "Background Knowledge"—a small subset of true records already known to the server (e.g., from previous audits or interactions).
3. Query Evaluation Phase
When a participant queries another's data, the owner applies Differential Privacy (DP) noise to the result. To ensure the owner isn't lying about the noisy result, the server injects hidden test queries. If the owner's responses to these tests deviate significantly from the expectations set by the Partial View, they are flagged as a cheater.
Experimental Evaluation
The researchers evaluated DataRing using a real-world dataset from Lending Club, comprising 2.26 million loan records. For the primary performance benchmarks, a subset of 500,000 records with 10 attributes was used. A key finding was that 97% of records in this high-dimensional space are unique, which significantly enhances the effectiveness of the Partial View verification.
Key Results
- Performance: Evaluating 10 queries on the 500,000-record dataset took 90.63 seconds. While cheating detection adds roughly 27% overhead, it provides essential integrity guarantees.
- Detection Accuracy: To maintain a 95% chance of passing initial verification, a participant must use at least 97.15% of their true dataset.
- Cheater Detection: The system can detect incorrect answers to even a single query with ~20% probability, which scales toward 100% if cheating persists across multiple queries.
- Comparative Efficiency: DataRing outperformed existing systems like Drynx in mean query evaluation time (1.0s vs 2.6s), despite its more rigorous verification checks.
Discussion and Insights
DataRing exploits the power of uniqueness in high-dimensional data. If a server knows just a few specific records, it becomes mathematically difficult for a cheater to construct a fake dataset that includes those records in correct proportions. This creates a probabilistic deterrence, making cheating "not worth the risk" for organizations.
The system also balances the inherent tension between Differential Privacy (which introduces noise) and cheating detection (which requires precision) by defining an "acceptance range" for query answers based on the noise scale.
Limitations and Future Directions
Currently, DataRing is optimized for static datasets. Future work will explore adapting the system for "evolving" or streaming data. Additionally, while the requirement for "Background Knowledge" is justified by legal and technical precedents, it remains a prerequisite for the system's verification capabilities.
Summary updated