A computer implemented method classifies securely a private query sample using exact k-nn classification. A secure dot product protocol is applied to determine securely distances between a private query sample and a plurality of private labeled samples. A secure k-rank protocol is applied to the distances to determine a nearest distance of a kth nearest labeled sample having a particular label. Then, a secure Parzen protocol is applied to the nearest distance to label the private query sample according to the particular label.