Toward Understanding Efficient Privacy-Preserving Homomorphic Comparison

The security issues that arise in public cloud environments raise several concerns about privacy-preserving. Conventional security practices successfully protect stored and transmitted data by encryption, but not during data processing where the data value extraction requires decryption. It creates critical exposure points for sensitive sectors like healthcare, pharmaceutical, genomics, government, and financial, among many others that cause hesitation to use these third-party services and prevent widespread practical adoption of cloud solutions. Homomorphic Encryption (HE) emerges as a mechanism for expanding the scope of public cloud services for sensitive data processing. However, high-demand solutions such as artificial intelligence and machine learning require efficient operations beyond HE additions and multiplications. In this paper, we analyze the current homomorphic comparison methods across their strengths and weaknesses and present theoretical concepts, state-of-the-art techniques, challenges, opportunities, and open problems. We theoretically prove the limits of the representability of sign and comparison functions in polynomial forms for HE schemes. We show that both functions can be represented as polynomials over the Galois field and cannot be represented over a residue ring with zero divisors. We compare the efficiency, accuracy, and computational complexity of different homomorphic comparison approaches. The experimental results demonstrate that Newton-Raphson is the fastest method for generating polynomial approximations and evaluating comparisons, and the Fourier method is the most accurate considering the L1, L2, L∞ norms and R2 measure. The bi-objective analysis presents the performance compromise between complexity and accuracy.