An efficient secure comparison protocol

We propose a new efficient cryptography-based secure comparison protocol for comparing secrets that are additively split between two parties. Our solution, based on homomorphic cryptosystems, needs 2N + 6 invocations of secure multiplications when the two secrets are numbers in the range [0; 2^N); previous solutions required 12N + O(1) secure multiplications. The protocol provides substantial performance improvement in privacy preserving data mining protocols that use comparison as a primitive operation. In particular, we experimentally evaluate the performance of our secure comparison protocol in the implementation of a secure k-means clustering protocol applied to several real datasets.