Cryptology ePrint Archive: Report 2016/470

Better Security for Queries on Encrypted Databases

Myungsun Kim and Hyung Tae Lee and San Ling and Shu Qin Ren and Benjamin Hong Meng Tan and Huaxiong Wang

Abstract: Private database query (PDQ) processing has received much attention from the fields of both cryptography and databases. While previous approaches to design PDQ protocols exploit several cryptographic tools concurrently, recently the appearance of fully homomorphic encryption (FHE) schemes enables us to design PDQ protocols without the aid of additional tools. However, to the best of our knowledge, all currently existing FHE-based PDQ protocols focus on protecting only constants in query statements, together with the client's data stored in the database server.

In this paper, we provide a FHE-based PDQ protocol achieving better security, protecting query types as well as constants in query statements for conjunctive, disjunctive, and threshold queries with equality comparison. Our contributions are three-fold: First, we present a new security definition that reflects our enhanced security model which additionally protects query types in query statements. Second, we provide a new design for PDQ protocols using FHE schemes. To do this, we come up with a method to homomorphically evaluate our encrypted target queries on the encrypted database. Thereafter, we apply it to construct a protocol and show its security under our enhanced security definition in the semi-honest model. Finally, we provide proof-of-concept implementation results of our PDQ protocol. According to our rudimentary experiments, it takes 40 seconds to perform a query on 2352 elements consisting of 11 attributes of 40-bit using Brakerski-Gentry-Vaikuntanathan's leveled FHE with SIMD techniques for 80-bit security, yielding an amortized rate of just 0.12 seconds per element.

Category / Keywords: applications / private queries, encrypted database, homomorphic encryption

Date: received 16 May 2016, last revised 16 May 2016

Contact author: hyungtaelee at ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20160517:151618 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]