Search Condition-Hiding Query Evaluation on Encrypted Databases

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...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:2169-3536
2169-3536
DOI:10.1109/ACCESS.2019.2951695