Efficient Privacy-Preserving k-Nearest Neighbor Search
- 1 June 2008
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 311-319
- https://doi.org/10.1109/icdcs.2008.79
Abstract
We give efficient protocols for secure and private k-nearest neighbor (k-NN) search, when the data is distributed between two parties who want to cooperatively compute the answers without revealing to each other their private data. Our protocol for the single-step k-NN search is provably secure and has linear computation and communication complexity. Previous work on this problem had a quadratic complexity, and also leaked information about the parties' inputs. We adapt our techniquesto also solve the general multi-step k-NN search, and describe a specific embodiment of it for the case of sequence data. The protocols and correctness proofs can be extended to suit other privacy-preserving data mining tasks, such as classification and outlier detection.Keywords
This publication has 24 references indexed in Scilit:
- A Hybrid Multi-group Privacy-Preserving Approach for Building Decision TreesPublished by Springer Science and Business Media LLC ,2007
- Privacy-preserving distributed mining of association rules on horizontally partitioned dataIEEE Transactions on Knowledge and Data Engineering, 2004
- Privately Computing a Distributed k-nn ClassifierLecture Notes in Computer Science, 2004
- Efficient algorithms for mining outliers from large data setsPublished by Association for Computing Machinery (ACM) ,2000
- Public-Key Cryptosystems Based on Composite Degree Residuosity ClassesPublished by Springer Science and Business Media LLC ,1999
- Optimal multi-step k-nearest neighbor searchPublished by Association for Computing Machinery (ACM) ,1998
- Two algorithms for nearest-neighbor search in high dimensionsPublished by Association for Computing Machinery (ACM) ,1997
- Software protection and simulation on oblivious RAMsJournal of the ACM, 1996
- Nearest neighbor queriesPublished by Association for Computing Machinery (ACM) ,1995
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970