Sharing in a Trustless World: Privacy-Preserving Data Analytics with Potentially Cheating Participants

Tham Nguyen, Hassan Jameel Asghar, Raghav Bhaskar, Dali Kaafar, Farhad Farokhi

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 system architecture involves multiple participants (P) and two non-colluding servers (S) to facilitate secure queries.

The DataRing Methodology

DataRing addresses these challenges through a multi-phase approach designed to detect and deter cheating without compromising privacy.

The DataRing workflow consists of three primary phases: Setup, Partial View, and Query Evaluation.

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

Abstract

Lack of trust between organisations and privacy concerns about their data are impediments to an otherwise potentially symbiotic joint data analysis. We propose DataRing, a data sharing system that allows mutually mistrusting participants to query each others' datasets in a privacy-preserving manner while ensuring the correctness of input datasets and query answers even in the presence of (cheating) participants deviating from their true datasets. By relying on the assumption that if only a small subset of rows of the true dataset are known, participants cannot submit answers to queries deviating significantly from their true datasets. We employ differential privacy and a suite of cryptographic tools to ensure individual privacy for each participant's dataset and data confidentiality from the system. Our results show that the evaluation of 10 queries on a dataset with 10 attributes and 500,000 records is achieved in 90.63 seconds. DataRing could detect cheating participant that deviates from its true dataset in few queries with high accuracy.
BibTeX
@misc{nguyen2021sharing,
  author = {Tham Nguyen and Hassan Jameel Asghar and Raghav Bhaskar and Dali Kaafar and Farhad Farokhi},
  title = {{Sharing in a Trustless World: Privacy-Preserving Data Analytics with Potentially Cheating Participants}},
  year = {2021},
  eprint = {2106.09904},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.09904},
}
Figure