An efficient privacy-preserving comparison protocol

Tushar Kanti Saha*, Takeshi Koshiba

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

6 Citations (Scopus)


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, Damgård, Geisler, and Krøigård (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.

Original languageEnglish
Title of host publicationLecture Notes on Data Engineering and Communications Technologies
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages13
Publication statusPublished - 2018

Publication series

NameLecture Notes on Data Engineering and Communications Technologies
ISSN (Print)2367-4512
ISSN (Electronic)2367-4520

ASJC Scopus subject areas

  • Media Technology
  • Electrical and Electronic Engineering
  • Computer Science Applications
  • Computer Networks and Communications
  • Information Systems


Dive into the research topics of 'An efficient privacy-preserving comparison protocol'. Together they form a unique fingerprint.

Cite this