Efficient homomorphic evaluation of <i>k</i>-NN classifiers
Martin Zuber, Renaud Sirdey
Abstract
Abstract We design and implement an efficient, secure, homomorphic k-Nearest Neighbours determination algorithm, to be used for regression or classification over private data. Our algorithm runs in quadratic complexity with regard to the size of the database but is the only one in the literature to make the secure determination completely non-interactively. We show that our secure algorithm is both efficient and accurate when applied to classification problems requiring a small set of model vectors, and still scales to larger sets of model vectors with high accuracy yet at greater (sequential) computational costs.
Topics & Concepts
Homomorphic encryptionComputer scienceSet (abstract data type)Support vector machineQuadratic equationData miningAlgorithmArtificial intelligenceTheoretical computer scienceMathematicsEncryptionComputer securityGeometryProgramming languageCryptography and Data SecurityPrivacy-Preserving Technologies in DataInternet Traffic Analysis and Secure E-voting