.png){kind=icon}
.png){kind=icon}
Return
Efficient Private Comparison Queries Over Encrypted Databases Using Fully Homomorphic Encryption With Finite Fields
.png){kind=icon}
OA
AI
DOI：10.1109/TDSC.2020.2967740.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 not equal 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 article, 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.
Keywords:
Private database queries
fully homomorphic encryption
secure comparison
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.5
Papers:
2.4K
Citations:
9.6K
View more organizations