Scalable Privacy-Preserving t-Repetition Protocol with Distributed Medical Data

Ji Young CHUN  Dowon HONG  Dong Hoon LEE  Ik Rae JEONG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A   No.12   pp.2451-2460
Publication Date: 2012/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.2451
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
t-repetition,  rare cases,  set operation,  data mining,  privacy,  

Full Text: PDF(1MB)>>
Buy this Article

Finding rare cases with medical data is important when hospitals or research institutes want to identify rare diseases. To extract meaningful information from a large amount of sensitive medical data, privacy-preserving data mining techniques can be used. A privacy-preserving t-repetition protocol can be used to find rare cases with distributed medical data. A privacy-preserving t-repetition protocol is to find elements which exactly t parties out of n parties have in common in their datasets without revealing their private datasets. A privacy-preserving t-repetition protocol can be used to find not only common cases with a high t but also rare cases with a low t. In 2011, Chun et al. suggested the generic set operation protocol which can be used to find t-repeated elements. In the paper, we first show that the Chun et al.'s protocol becomes infeasible for calculating t-repeated elements if the number of users is getting bigger. That is, the computational and communicational complexities of the Chun et al.'s protocol in calculating t-repeated elements grow exponentially as the number of users grows. Then, we suggest a polynomial-time protocol with respect to the number of users, which calculates t-repeated elements between users.