2005 · 40 citations · 20 references
ComputingComputer ScienceComputer SecurityData MiningPrivacy EngineeringData AnonymizationData BreachesData ProtectionData SecurityPrivacy-preserving AnalyticsAnonymization RiskBelief FunctionsBenchmark DatasetsFrequent Itemset MiningKnowledge Discovery ProcessesPrivacy-preserving Data MiningSensitive Information LeakageSensitive Information Protection
Decision makers of companies often face the dilemma of whether to release data for knowledge discovery, vis a vis the risk of disclosing proprietary or sensitive information. While there are various "sanitization" methods, in this paper we focus on anonymization, given its widespread use in practice. We give due diligence to the question of "just how safe the anonymized data is", in terms of protecting the true identities of the data objects. We consider both the scenarios when the hacker has no information, and more realistically, when the hacker may have partial information about items in the domain. We conduct our analyses in the context of frequent set mining. We propose to capture the prior knowledge of the hacker by means of a belief function, where an educated guess of the frequency of each item is assumed. For various classes of belief functions, which correspond to different degrees of prior knowledge, we derive formulas for computing the expected number of "cracks". While obtaining the exact values for the more general situations is computationally hard, we propose a heuristic called the O-estimate. It is easy to compute, and is shown to be accurate empirically with real benchmark datasets. Finally, based on the O-estimates, we propose a recipe for the decision makers to resolve their dilemma.
20
Mining association rules between sets of items in large databases
Rakesh Agrawal, Tomasz Imieliński, Arun Swami · 1993 · 14.8K citations · Full text
Privacy-preserving data mining
Rakesh Agrawal, Ramakrishnan Srikant · ACM SIGMOD Record · 2000 · 3K citations
The complexity of computing the permanent
Leslie G. Valiant · Theoretical Computer Science · 1979 · 2.8K citations
Privacy-preserving data mining
Rakesh Agrawal, Ramakrishnan Srikant · 2000 · 1.7K citations