Abstract
Private itemset support counting (PISC) is a basic building block of various privacy-preserving data mining algorithms. Briefly, in PISC, Client wants to know the support of her itemset in Server’s database with the usual privacy guarantees. First, we show that if the number of attributes is small, then a communication-efficient PISC protocol can be constructed from a communication-efficient oblivious transfer protocol. The converse is also true: any communication-efficient PISC protocol gives rise to a communication-efficient oblivious transfer protocol. Second, for the general case, we propose a computationally efficient PISC protocol with linear communication in the size of the database. Third, we show how to further reduce the communication by using various tradeoffs and random sampling techniques.
Chapter PDF
Similar content being viewed by others
Keywords
References
Aiello, W., Ishai, Y., Reingold, O.: Priced Oblivious Transfer: How to Sell Digital Goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135. Springer, Heidelberg (2001)
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.I.: Fast Discovery of Association Rules. In: Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.) Advances in Knowledge Discovery and Data Mining, pp. 307–328. AAAI/MIT Press (1996)
Bayardo Jr., R.J., Goethals, B., Zaki, M.J. (eds.): FIMI 2004, Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations, Brighton, UK. CEUR Workshop Proceedings, vol. 126, November 1 (2004)
Chor, B., Gilboa, N., Naor, M.: Private information retrieval by keywords. Technical Report TR CS0917, Department of Computer Science, Technion (1997)
Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword Search and Oblivious Pseudorandom Functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303–324. Springer, Heidelberg (2005)
Freedman, M.J., Nissim, K., Pinkas, B.: Efficient Private Matching and Set Intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004)
Gunopulos, D., Khardon, R., Mannila, H., Saluja, S., Toivonen, H., Sharma, R.S.: Discovering All Most Specific Sentences. ACM Transactions on Database Systems 28(2), 140–174 (2003)
Gentry, C., Ramzan, Z.: Single-Database Private Information Retrieval with Constant Communication Rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005)
Lipmaa, H.: Verifiable Homomorphic Oblivious Transfer and Private Equality Test. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 416–433. Springer, Heidelberg (2003)
Lipmaa, H.: An Oblivious Transfer Protocol with Log-Squared Communication. In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314–328. Springer, Heidelberg (2005)
Mielikäinen, T.: On Inverse Frequent Set Mining. In: 2nd Workshop on Privacy Preserving Data Mining (PPDM), Melbourne, Florida, USA, November 19, pp. 18–23. IEEE Computer Society Press, Los Alamitos (2003)
Mielikäinen, T.: Separating Structure from Interestingness. In: Dai, H., Srikant, R., Zhang, C. (eds.) PAKDD 2004. LNCS (LNAI), vol. 3056, pp. 476–485. Springer, Heidelberg (2004)
Mannila, H., Toivonen, H.: Levelwise Search and Borders of Theories in Knowledge Discovery. Data Mining and Knowledge Discovery 1(3), 241–258 (1997)
Ogata, W., Kurosawa, K.: Oblivious Keyword Search. Journal of Complexity 20(2–3), 356–371 (2004)
Toivonen, H.: Sampling Large Databases for Association Rules. In: Vijayaraman, T.M., Buchmann, A.P., Mohan, C., Sarda, N.L. (eds.) VLDB 1996, Proceedings of 22th International Conference on Very Large Data Bases, September 3–6, pp. 134–145. Morgan Kaufmann, San Francisco (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Laur, S., Lipmaa, H., Mielikäinen, T. (2005). Private Itemset Support Counting. In: Qing, S., Mao, W., López, J., Wang, G. (eds) Information and Communications Security. ICICS 2005. Lecture Notes in Computer Science, vol 3783. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602897_9
Download citation
DOI: https://doi.org/10.1007/11602897_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30934-5
Online ISBN: 978-3-540-32099-9
eBook Packages: Computer ScienceComputer Science (R0)