Efficient Private Comparison Queries over Encrypted Databases using Fully Homomorphic Encryption with Finite Fields

Efficient Private Comparison Queries over Encrypted Databases using Fully Homomorphic Encryption with Finite Fields
Title:
Efficient Private Comparison Queries over Encrypted Databases using Fully Homomorphic Encryption with Finite Fields
Other Titles:
IEEE Transactions for Dependable and Secure Computing
DOI:
Publication URL:
Publication Date:
01 January 2020
Citation:
Abstract:
To achieve security and privacy for data stored on the cloud, we need the ability to secure data in compute. Equality comparisons, “x = y, x 6= y”, have been widely studied with many proposals but there is much room for improvement for order comparisons, “x < y, x ≤ y, x > y and x ≥ y”. Most protocols for order comparisons have some limitation, either leaking some information about the data or requiring several rounds of communication between client and server. In addition, little work has been done on retrieving with compound conditions, mixing several equality and order comparisons. Fully homomorphic encryption (FHE) promises the ability to compute arbitrary functions on encrypted data without sacrificing privacy and without communication, but its potential has yet to be fulfilled. Particularly, private comparisons for database queries using FHE are expensive to compute. In this work, we design an efficient private database query (PDQ) protocol which supports compound conditions with equality and order comparisons. To this end, we first present a private comparison algorithm on encrypted integers using FHE, which scales efficiently for the length of input integers, by applying techniques from finite field theory. Then, we consider a scenario for PDQ protocols, querying for values based on a conjunction of one order and four equality conditions on key columns. The proposed algorithm and protocol are implemented and tested to determine their performance in practice. The proposed comparison algorithm takes about 25.259 seconds to compare 697 pairs of 64-bit integers using Brakerski-Gentry-Vaikuntanathan’s leveled FHE scheme with single instruction multiple data (SIMD) techniques at more than 138 bits of security. This yields an amortized rate of just 36 milliseconds per comparison. On top of that, we show that our techniques achieve an efficient PDQ protocol for one order and four equality comparisons, achieving an amortized time and communication cost of 57 milliseconds and 448 bytes per database element.
License type:
PublisherCopyrights
Funding Info:
Basic Science Research Program, South Korean National Research Foundation of Korea (NRF), Ministry of Science and ICT (No. NRF-2018R1C1B6008476), Strategic Capability Research Centres Funding Initiative,Singapore Ministry of Education Research Grant MOE2016-T2-2-014(S)
Description:
© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
ISBN:

Files uploaded:
File Size Format Action
There are no attached files.