Efficient anonymity-preserving data collection

Justin Brickell, Vitaly ShmatikovKDD 2006 · DOI

TL;DR

This paper introduces a novel protocol for collecting sensitive data from a large number of respondents anonymously and securely, even when participants and the data collector are mutually distrustful. The key innovation is achieving collusion-resistant anonymity with linear communication rounds and without relying on complex zero-knowledge proofs, making it practical for large-scale data mining.

What Problem Does This Paper Address?

In data mining, especially for sensitive topics like health or finance, individuals are often hesitant to share accurate data due to privacy concerns. They might be willing to contribute if assured their data will be used only in aggregate and cannot be linked back to them. Existing protocols for anonymity-preserving data collection often struggle with efficiency, requiring many communication rounds or complex cryptographic techniques like zero-knowledge proofs, which can be computationally expensive and difficult to compose. Furthermore, these protocols need to be "collusion resistant," meaning that even if all dishonest respondents and the data miner conspire, they shouldn't be able to link specific responses to honest individuals. This paper aims to bridge this gap by providing a protocol that is both efficient and robustly secure.

Methods

The proposed protocol has two main parts:

  1. Encryption and Shuffling: Respondents encrypt their responses using a layered approach. First, they encrypt with the data miner's public key, then with secondary public keys of all respondents, and finally with the primary public keys of all respondents. This layered encryption ensures that no single entity can decrypt the data without the cooperation of others. The responses are then shuffled under encryption.
  2. Verification and Decryption: The protocol includes a crucial verification phase. Respondents use their knowledge of their own responses and secondary private keys to verify the integrity of the shuffling process without revealing their private keys prematurely. This verification step is designed to detect malicious behavior or incorrect shuffles. Only after successful verification do respondents reveal their secondary private keys, allowing the data miner to decrypt the responses.

A key aspect of their method is avoiding zero-knowledge proofs for shuffle verification. Instead, they leverage the fact that each respondent knows their own response and can verify if their encrypted response was correctly handled during the shuffling process. This significantly reduces communication overhead.

Datasets

Not discussed in the paper. The paper focuses on a theoretical protocol and its security properties, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Collusion Resistance Without Zero-Knowledge Proofs: The most significant insight is demonstrating that robust anonymity and collusion resistance can be achieved without the computationally intensive zero-knowledge proofs typically used for verifiable shuffles.
  • Respondents as "Mix-Servers": The protocol cleverly uses the respondents themselves as decentralized mix-servers. Each respondent contributes to shuffling and rerandomizing the encrypted data, creating a layered anonymity.
  • Verification Through Self-Knowledge: The protocol's security hinges on respondents being able to verify the integrity of the shuffling process using their own data and secondary keys, rather than relying on complex proofs of knowledge. This is a novel approach to ensuring shuffle correctness in a distributed, distrustful environment.
  • Efficiency Gains: By avoiding zero-knowledge proofs and optimizing communication rounds, the protocol becomes practical for scenarios with a large number of respondents, a common challenge in real-world data collection.

Key Results

  • Linear Communication Rounds: The protocol achieves O(N) communication rounds, where N is the number of respondents, a significant improvement over previous quadratic protocols.
  • Collusion Resistance: The protocol is proven to be collusion resistant, meaning that even if all dishonest respondents collude with a dishonest data miner, they cannot link specific responses to honest individuals.
  • IND-CCA2 Security: The protocol relies on an underlying public-key encryption scheme that is Indistinguishable Under Adaptive Chosen Ciphertext Attack (IND-CCA2), a strong security guarantee.
  • Practicality: The reduced communication complexity and avoidance of zero-knowledge proofs make the protocol more suitable for large-scale data mining applications compared to prior work.

Limitations and Future Work

  • Trust in Certification Authority: The protocol assumes the existence of a trusted certification authority for initial key distribution. While standard, this is a single point of trust.
  • Honest Data Miner Assumption for Integrity: While the protocol aims for integrity, it notes that a dishonest data miner can corrupt responses. The security arguments for integrity primarily assume an honest data miner who wants accurate data.
  • Computational Complexity: While communication is efficient, the overall computation is O(N^2), with individual respondents having O(N) complexity. This is still manageable, especially since respondents are often less computationally powerful than a central server.
  • Future Work: The paper implicitly suggests that further research could explore even more efficient protocols or investigate scenarios with different trust models. The authors highlight the impracticality of previous zero-knowledge proof-based approaches, reinforcing the value of their efficient, proof-free verification method.

Summary updated

BibTeX
@inproceedings{brickell2006efficient,
  author = {Justin Brickell and Vitaly Shmatikov},
  title = {{Efficient anonymity-preserving data collection}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2006},
  doi = {10.1145/1150402.1150415},
}
Figure