Search Condition-Hiding Query Evaluation on Encrypted Databases

• Published in: IEEE access 2019, Vol.7, p.161283-161295
• Main Authors: Kim, Myungsun, Lee, Hyung Tae, Ling, San, Ren, Shu Qin, Tan, Benjamin Hong Meng, WANG, Huaxiong
• Format: Article
• Language: English
• Subjects: Cloud computing; Encrypted database; Encryption; homomorphic encryption; Polynomials; Privacy; private queries; Protocol; Protocols; Queries; Query processing; Searching; Servers
• ISSN: 2169-3536; 2169-3536
• DOI: 10.1109/ACCESS.2019.2951695

Private database query (PDQ) is a protocol between a client and a database server, designed for processing queries to encrypted databases. Specifically, PDQ enables a client to submit a search query and to learn a resulting set satisfying its search condition, without revealing sensitive information about a query statement. The whole query can be protected from the server, but for efficiency reasons known PDQ solutions generally consider to hide the constants only in a query statement. 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