M. Kim, H. T. Lee, S. Ling, S. Q. Ren, B. H. M. Tan and H. Wang, "Search Condition-Hiding Query Evaluation on Encrypted Databases," in IEEE Access. doi: 10.1109/ACCESS.2019.2951695
Abstract:
In this paper, we provide two fully homomorphic encryption (FHE)-based PDQ protocols that hide type of queries as well as the constants of a query statement. Particularly, our constructions focus on conjunctive, disjunctive, and threshold conjunctive queries. To this end, we first build a single compact logical expression to cover both conjunctive and disjunctive queries. On top of the logical expression, we design a PDQ protocol that enables to evaluate conjunctive and disjunctive queries without revealing any information on a given query. The second PDQ protocol comes from our observation that if a threshold conjunctive query has a particular threshold value, it results in either a conjunctive query or a disjunctive query. Because the PDQ protocol writes the three types of queries into a single polynomial expression, the resulting protocol can evaluate the three types of query statements without revealing any information on queries. To demonstrate their efficiency, we provide proof-of-concept implementation results of our proposed PDQ protocols. According to our rudimentary experiments, it takes 37.57 seconds to perform a query on 316 elements consisting of 16 attributes of 64 bits using Brakerski-Gentry-Vaikuntanathan's leveled FHE with SIMD techniques for 149-bit security, yielding an amortized rate of just 0.119~seconds per element.
License type:
http://creativecommons.org/licenses/by/4.0/
Funding Info:
National Research Foundation of Korea (NRF) funded by the Ministry of Education (No. NRF-2017R1D1A1B04035209), National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (No. NRF-2018R1C1B6008476), Singapore Ministry of Education under Research Grant MOE2016-T2-2-014(S)