Helger Lipmaa's publications

Private Itemset Support Counting

Sven Laur, Helger Lipmaa and Taneli Mielikäinen. Private Itemset Support Counting. In Sihan Qing, Wenbo Mao, Javier Lopez and Guilin Wang, editors, Information and Communications Security: 7th International Conference, ICICS 2005, volume 3783 of Lecture Notes in Computer Science, pages 97--111, Beijing, China, December 10--13, 2005. Springer, Heidelberg.

File: [.ps.bz2 (105 KB), .pdf (175 KB)] ps recommended.


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..

Keywords: privacy-preserving data mining, private frequent itemset mining, private itemset support counting, private subset inclusion test.

More information: Publisher Webpage.

DOI: 10.1007/11602897_9


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.