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: ia.cr/2016/470