zbMATH — the first resource for mathematics

Private itemset support counting. (English) Zbl 1122.68494
Qing, Sihan (ed.) et al., Information and communications security. 7th international conference, ICICS 2005, Beijing, China, December 10–13, 2005. Proceedings. Berlin: Springer (ISBN 3-540-30934-9/pbk). Lecture Notes in Computer Science 3783, 97-111 (2005).
Summary: 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.
For the entire collection see [Zbl 1098.68006].

68T05 Learning and adaptive systems in artificial intelligence
68T10 Pattern recognition, speech recognition
94A62 Authentication, digital signatures and secret sharing
Full Text: DOI