Patent ID: 7685115

Claim:
A computer implemented method for classifying securely a private query sample using exact k-nn classification, wherein nn means nearest neighbor, and k is a number of the nearest neighbors, comprising: using an apparatus to perform the method comprising the steps of: applying a secure dot product protocol to the private query sample and a plurality of private labeled samples to determine securely distances between the private query sample and the plurality of private labeled samples; applying a secure k-rank protocol to the distances to determine a nearest distance of a k th nearest labeled sample having a particular label; and applying a secure Parzen window protocol using the nearest distance to label the private query sample according to the particular label to label the private query sample according to the particular label to classify the private query sample, and wherein all of the applying steps are performed in part on a client computer and in part on server computer to provide secure multi-party computing for the classifying.