Private comparison protocol and its application to range queries

Abstract

We consider the problem of private comparison protocol and its application to private range queries for accessing a private database. Very recently, Saha and Koshiba (NBiS 2017) proposed an efficient privacy-preserving comparison protocol using ring-LWE based somewhat homomorphic encryption (SwHE) in the semi-honest model. The protocol took 124 ms (resp., 125 ms) for comparing two 16-bit (resp., 32-bit) integers. But this protocol is not efficient enough to process range queries to a large database where several thousand comparisons are required. In this paper, we propose an efficient parity-based private comparison protocol and show its application to private range queries with a modified packing method. Here the security of the protocol is also ensured by ring-LWE based SwHE in the same semi-honest model. Our practical experiments show that our comparison protocol enables us to do a single comparison in 84 ms (resp., 85 ms) for 16-bit (resp., 32-bit) integers which is more efficient than Saha et al.’s protocol. Besides, it takes about 0.499 s (resp., 2.247 s) to process a 3-out-of-11 range query in a database of 100 records (resp., 1000 records) including 11 attributes, which outperform state of the art. © Springer Nature Switzerland AG 2018.