Practical protocol for Yao’s millionaires problem enables secure multi-party computation of metrics and efficient privacy-preserving k-NN for large data sets

Amirbekyan, Artak and Estivill-Castro, Vladimir (2009) Practical protocol for Yao’s millionaires problem enables secure multi-party computation of metrics and efficient privacy-preserving k-NN for large data sets. Knowledge and Information Systems, 21 3: 327-363. doi:10.1007/s10115-009-0233-z


Author Amirbekyan, Artak
Estivill-Castro, Vladimir
Title Practical protocol for Yao’s millionaires problem enables secure multi-party computation of metrics and efficient privacy-preserving k-NN for large data sets
Formatted title
Practical protocol for Yao’s millionaires problem enables secure multi-party computation of metrics and efficient privacy-preserving k-NN for large data sets
Journal name Knowledge and Information Systems   Check publisher's open access policy
ISSN 0219-1377
0219-3116
Publication date 2009-07-18
Sub-type Article (original research)
DOI 10.1007/s10115-009-0233-z
Volume 21
Issue 3
Start page 327
End page 363
Total pages 37
Place of publication Surrey, United Kingdom
Publisher Springer U K
Language eng
Subject 280505 Data Security
280501 Data Structures
280504 Data Encryption
Formatted abstract
Finding the nearest k objects to a query object is a fundamental operation for many data mining algorithms. With the recent interest in privacy, it is not surprising that there is strong interest in k-NN queries to enable clustering, classification and outlier-detection tasks. However, previous approaches to privacy-preserving k-NN have been costly and can only be realistically applied to small data sets. In this paper, we provide efficient solutions for k-NN queries for vertically partitioned data. We provide the first solution for the L (or Chessboard) metric as well as detailed privacy-preserving computation of all other Minkowski metrics. We enable privacy-preserving L by providing a practical approach to the Yao’s millionaires problem with more than two parties. This is based on a pragmatic and implementable solution to Yao’s millionaires problem with shares. We also provide privacy-preserving algorithms for combinations of local metrics into a global metric that handles the large dimensionality and diversity of attributes common in vertically partitioned data. To manage very large data sets, we provide a privacy-preserving SASH (a very successful data structure for associative queries in high dimensions). Besides providing a theoretical analysis, we illustrate the efficiency of our approach with an empirical evaluation.
Keyword Privacy-preserving data mining
Secure multi-party computation
Nearest-neighbour classification
Yao’s millionaires problem
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 6 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 8 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 02 Sep 2009, 00:57:58 EST by Dr Artak Amirbekyan on behalf of Earth Systems Science Computational Centre