Security in Association Rule Mining

This dissertation, "Security in Association Rule Mining" by Wai-kit, Wong, 王偉傑, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled "Security in Association Rule Mining" Submitted by Wong Wai Kit for the degree of Master of Philosophy at The University of Hong Kong in August 2007 Association rule mining discovers correlations between different itemsets in a transaction database. It provides important knowledge in business for decision makers. Different algorithms have been proposed to facilitate association rule mining in different situations. However, most previous studies involving two or more parties have not considered security with the result that some private and sensitive information is disclosed to other parties. New algorithms are required to address the security issue. Novel techniques have been proposed to protect private information in data mining, e.g., data perturbation, secure multiparty computation. Various cases of privacy preserving association rule mining, such as distributed horizontally partitioned databases and vertically partitioned databases, are studied. How- ever, association rule mining in many other situations is still left untouched. In our thesis, we proposed new solutions in two aspects: (i) maintenance of the discovered rules with privacy protection when new sites join the old sites, and (ii) outsourcing of association rule mining to a third party while protecting the database and the mined association rules. Whileresearchresultshavebeendevelopedon(i)incrementallymaintainingthe discovered association rules, and (ii) computing the distributed association ruleswhilepreservingprivacy, theincrementalmaintenanceofdistributedassoci- ation rule mining with privacy protection cannot be solved efficiently by existing secure protocols. We proposed an algorithm SIMDAR for this problem. Some techniqueswe developedcanevenfurtherreducethecostinanormalassociation ruleminingalgorithmwithprivacyprotection. Experimentalresultsshowedthat SIMDAR can significantly reduce the workload at the old sites by up to 80%. Outsourcing association rule mining to an outside service provider brings several benefits to the data owner. Nevertheless, private data and the mined result should be protected against third party access. We proposed substitution cipher techniques in the encryption of transactional data for outsourcing asso- ciation rule mining. A comprehensive cryptanalysis study is carried out. The results show that our technique is highly secure with a low data transformation cost. DOI: 10.5353/th_b3955890 Subjects: Data mining Computer security