An Efficient Privacy-Preserving Comparison Protocol

We address an efficient privacy-preserving comparison protocol using somewhat homomorphic encryption based on ring learning with errors (ring-LWE) problem in the semi-honest model. Here we take two l-bit integers a and b as input and produce the output indicating a < b or a >= b. To accomplish this task, Damgard, Geisler, and Kroigard (DGK) [Int. J. of Appl. Cryptol., 1(1), 2008] proposed an efficient protocol using an additively homomorphic encryption scheme in the semi-honest model. Thereafter many attempts were made to improve the performance for the privacy-preserving integer comparison but the improvement is not remarkable. Until now, the DGK protocol is believed to be one of the efficient comparison protocols using homomorphic encryption. The DGK protocol executes an integer comparison within 969 ms (resp., 1977 ms) for 16-bit (resp., 32-bit) integers under the 112-bit security level (by using the 2048-bit RSA). In this paper, we propose a more efficient comparison protocol than the DGK protocol. For the efficiency, we propose two new packing methods to make the comparison computation faster for some packed ciphertexts. The first packing method helps the multiple Hamming distance computation and the second packing method helps to compute the bit differences of two l-bit integers. Finally, our experiments at the 140-bit security level show that our method is about 147 times faster for 16-bit integers comparison and 146 times faster for 32-bit integers comparison than that of the DGK protocol.