Data mining services require accurate input data for their results to be meaningful, but privacy concerns may influence users to provide spurious information. To preserve client privacy in the data mining process, a variety of techniques based on random perturbation of data records have been proposed recently. One known fact which is very important in data mining is discovering the association rules from database of transactions where each transaction consists of set of items. Two important terms support and confidence are associated with each of the association rule. Actually any rule is called as sensitive if its disclosure risk is above a certain privacy threshold. Sometimes we do not want to disclose a sensitive rule to the public because of confidentiality purposes. This paper is extension of work done in [1]. In [1] a reduction of 3-SAT problem from optimal sanitization in association rule hiding is presented. This paper proves that optimal sanitization in association rule hiding is NP-Complete. The proofs are based on reduction from 3-SAT.

1. Kshitij Pathak, Aruna Tiwari, Narendra S Chaudhari A Reduction of 3-SAT problem from optimal sanitization in association rule hiding In: Proc. Of IEEE Int’l conference ETNCC, 2011, 43-46
2. Atallah, M., Bertino, E., Elmagarmid, A., Ibrahim, M., and Verykios, V.S. Disclosure limitation of sensitive rules. In: Scheuermann P, ed. Proc. of the IEEE Knowledge and Data Exchange Workshop (KDEX'99). IEEE Computer society, 1999. 45-52.
3. Verykios, V.S., Elmagarmid, A., Bertino, E., Saygin, Y., and Dasseni, E. Association rule hiding. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(4):434-447.
4. Oliveira, S.R.M. and Zaïane, O.R. Privacy preserving frequent itemset mining. In: Proc. of the 2 nd IEEE ICDM Workshop on Privacy, Security and Data Mining. Australian Computer Society, 2002. 43-54.
5. Oliveira, S.R.M. and Zaïane, O.R. Protecting sensitive knowledge by data sanitization. In: Proc. of the 3Prd P IEEE Int’l Conf. on Data Mining (ICDM'03). IEEE Computer Society, USA, 2003. 613-616.
6. Oliveira, S.R.M. and Zaïane, O.R. A unified framework for protecting sensitive association rules in business collaboration. Int’l Journal of Business Intelligence and Data Mining, 2006, 1(3):247-287.
7. Shariq J. Rizvi Jayant R. Haritsa Maintaining Data Privacy in Association Rule Mining Proceedings of the 28th VLDB Conference,Hong Kong, China, 2002
8. Sun, X. and Yu, P.S. A border-based approach for hiding sensitive frequent itemsets. In: Proc. of the 5th IEEE Int’l Conf. on Data Mining (ICDM'05). IEEE Computer Society, 2005. 426-433.
9. Saygin, Y., Verykios, V.S., and Clifton, C. Using unknowns to prevent discovery of association rules. SIGMOD Record,2001, 30(4):45-54.
10. Chen, X., Orlowska, M., and Li, X. A new framework for privacy preserving data sharing. In: Proc. of the 4th IEEE ICDM Workshop: Privacy and Security Aspects of Data Mining. IEEE Computer Society, 2004. 47-56.
11. Natwichai, J., Li, X., and Orlowska, M. A reconstruction based algorithm for classification rules hiding. In: Dobbie G, Bailey J, eds. Proc. of the Seventeenth Australasian Database Conf. (ADC'06). Australian Computer Society,2006. 49-58.

3-SAT Association Rule NP-Complete Data mining Data Sanitization