TY - GEN
T1 - Private comparison protocol and its application to range queries
AU - Saha, Tushar Kanti
AU - Mayank,
AU - Deevashwer,
AU - Koshiba, Takeshi
N1 - Funding Information:
Acknowledgments. This work is supported in part by JSPS Grant-in-Aids for Scientific Research (A) JP16H01705 and for Scientific Research (B) JP17H01695.
Publisher Copyright:
© Springer Nature Switzerland AG 2018.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
KW - Batch technique
KW - Comparison protocol
KW - Range query
KW - Somewhat homomorphic encryption
UR - http://www.scopus.com/inward/record.url?scp=85051129984&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85051129984&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-97795-9_12
DO - 10.1007/978-3-319-97795-9_12
M3 - Conference contribution
AN - SCOPUS:85051129984
SN - 9783319977942
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 128
EP - 141
BT - Internet and Distributed Computing Systems - 10th International Conference, IDCS 2017, Proceedings
A2 - Di Fatta, Giuseppe
A2 - Guerrieri, Antonio
A2 - Pathan, Mukaddim
A2 - Fortino, Giancarlo
A2 - Ali, A. B.
PB - Springer Verlag
T2 - 10th International Conference on Internet and Distributed Computing Systems, IDCS 2017
Y2 - 11 December 2017 through 13 December 2017
ER -