2006 · 69 citations · 15 references
ComputingComputer ScienceComputer SecurityCryptographyData MiningData AnonymizationData ConfidentialityData ProtectionData SecurityPrivacy-preserving ProtocolsZero-knowledge ProofsAnonymity GuaranteesAnonymity ProtocolsAnonymizationAnonymized Data CollectionCollusion ResistanceCollusion-resistant MechanismsSensitive Data AnonymizationZero-knowledge Proof Protocols
The output of a data mining algorithm is only as good as its inputs, and individuals are often unwilling to provide accurate data about sensitive topics such as medical history and personal finance. Individuals maybe willing to share their data, but only if they are assured that it will be used in an aggregate study and that it cannot be linked back to them. Protocols for anonymity-preserving data collection provide this assurance, in the absence of trusted parties, by allowing a set of mutually distrustful respondents to anonymously contribute data to an untrusted data miner.To effectively provide anonymity, a data collection protocol must be collusion resistant, which means that even if all dishonest respondents collude with a dishonest data miner in an attempt to learn the associations between honest respondents and their responses, they will be unable to do so. To achieve collusion resistance, previously proposed protocols for anonymity-preserving data collection have quadratically many communication rounds in the number of respondents, and employ (sometimes incorrectly) complicated cryptographic techniques such as zero-knowledge proofs.We describe a new protocol for anonymity-preserving, collusion resistant data collection. Our protocol has linearly many communication rounds, and achieves collusion resistance without relying on zero-knowledge proofs. This makes it especially suitable for data mining scenarios with a large number of respondents.
15
How to generate and exchange secrets
Andrew Chi-Chih Yao · 1986 · 3.7K citations
Oded Goldreich, Silvio Micali, Avi Wigderson · 1987 · 3.5K citations
Privacy-preserving data mining
Rakesh Agrawal, Ramakrishnan Srikant · ACM SIGMOD Record · 2000 · 3K citations