Privacy preserving OLAP

ABSTRACT

We present techniques for privacy-preserving computation of multidimensional aggregates on data partitioned across multiple clients. Data from different clients is perturbed (randomized) in order to preserve privacy before it is integrated at the server. We develop formal notions of privacy obtained from data perturbation and show that our perturbation provides guarantees against privacy breaches. We develop and analyze algorithms for reconstructing counts of subcubes over perturbed data. We also evaluate the tradeoff between privacy guarantees and reconstruction accuracy and show the practicality of our approach.

REFERENCES

• 1: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 2: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 3: Rakesh Agrawal , Alexandre Evfimievski , Ramakrishnan Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872771]
• 4: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 5: C. Blake and C. Merz. UCI repository of machine learning databases, 1998.
• 6: S. Chawla, C. Dwork, F. McSherry, H. Wee, and A. Smith. Towards privacy in public databases. In Theory of Cryptography Conference, 2005.
• 7: H. Chernoff. Asymptotic efficiency for tests based on the sums of observations. In Annals of Mathematical Statistics, 1952.
• 8: Chris Clifton , Murat Kantarcioglu , Jaideep Vaidya , Xiaodong Lin , Michael Y. Zhu, Tools for privacy preserving distributed data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.28-34, December 2002 [doi>10.1145/772862.772867]
• 9: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 10: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775080]
• 11: Josep Domingo-Ferrer , Vicenç Torra, Disclosure risk assessment in statistical microdata protection via advanced record linkage, Statistics and Computing, v.13 n.4, p.343-354, October 2003 [doi>10.1023/A:1025666923033]
• 12: M. J. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In Proc. Advances in Cryptology - EUROCRYPT 2004, 2004.
• 13: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 14: G. Golub and C. V. Loan. Matrix computations. John Hopkins Series in the Mathematical Sciences, 1996.
• 15: K. Hoffman and R. Kunze. Linear algebra. Prentice-Hall Inc. 1971.
• 16: Bernardo A. Huberman , Matt Franklin , Tad Hogg, Enhancing privacy and trust in electronic communities, Proceedings of the 1st ACM conference on Electronic commerce, p.78-86, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337012]
• 17: C. A. J. Hurkens and S. R. Tiourine. Model and methods for the microdata protection problem. In Journal of Official Statistics, 1998.
• 18: Chong K. Liew , Uinam J. Choi , Chung J. Liew, A data distortion by probability distribution, ACM Transactions on Database Systems (TODS), v.10 n.3, p.395-411, Sept. 1985 [doi>10.1145/3979.4017]
• 19: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 20: R. A. J. Moore. Controlled data-swapping techniques for masking public use microdata sets. In SRD Report RR 96-04, US Bereau of Census, 1996.
• 21: S. Rizvi and J. R. Haritsa. Maintaining data privacy in association rule mining. In Proc. of the 2002 Intl. Conf. on Very Large Data Bases.
• 22: L. Wang, S. Jajodia, and D. Wijesekera. Securing OLAP data cubes against privacy breaches. In In Proc. of the 2004 IEEE Symposium on Security and Privacy.
• 23: Lingyu Wang , Duminda Wijesekera , Sushil Jajodia, Cardinality-based inference control in data cubes, Journal of Computer Security, v.12 n.5, p.655-692, September 2004
• 24: S. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Assoc., 60(309).
• 25: A. Yao. How to generate and exchange secrets. In Proc. of the 1986 Annual IEEE Symp. on Foundations of Computer Science.