학술논문
Efficient Private Comparison Queries Over Encrypted Databases Using Fully Homomorphic Encryption With Finite Fields
Document Type
Periodical
Author
Source
IEEE Transactions on Dependable and Secure Computing IEEE Trans. Dependable and Secure Comput. Dependable and Secure Computing, IEEE Transactions on. 18(6):2861-2874 Jan, 2021
Subject
Language
ISSN
1545-5971
1941-0018
2160-9209
1941-0018
2160-9209
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\ne y$x=y,x≠y”, have been widely studied with many proposals but there is much room for improvement for order comparisons, “$x < y,~x \leq y,~x > y \text{ and } x \geq y$xyandx≥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$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.