Enabling distance-based operations on data encrypted using a homomorphic encryption scheme with inefficient decryption
Methods, systems, and computer program products for enabling distance-based algorithms on data encrypted using a 2DNF homomorphic encryption scheme with inefficient decryption are provided herein. A computer-implemented method includes generating multiple versions of a data point, wherein each of the multiple versions of the data point comprises a distinct value corresponding to a distinct Euclidean space; encrypting each of the multiple versions of the data point; storing the multiple encrypted versions of the data point across multiple databases; and executing one or more distance-based algorithms on the multiple encrypted versions of the data point by using a finite decryption table across the multiple databases, wherein the finite decryption table stores a set of plaintext-ciphertext mappings between (i) multiple plaintext values and (ii) multiple encrypted ciphertext values corresponding to the multiple plaintext values.
1. A computer-implemented method, the method comprising steps of:
generating multiple versions of a data point, wherein each of the multiple versions of the data point comprises a distinct value corresponding to a distinct Euclidean space;
encrypting each of the multiple versions of the data point;
storing the multiple encrypted versions of the data point across multiple databases; and
executing one or more distance-based algorithms on the multiple encrypted versions of the data point by using a finite decryption table across the multiple databases, wherein the finite decryption table stores a set of plaintext-ciphertext mappings between (i) multiple plaintext values and (ii) multiple encrypted ciphertext values corresponding to the multiple plaintext values;
wherein the steps are carried out by at least one computing device.
2. The computer-implemented method of claim 1 , wherein the multiple encrypted ciphertext values comprise multiple 2DNF-encrypted ciphertext values.
3. The computer-implemented method of claim 1 , wherein the multiple plaintext values are selected by a storage manager.
4. The computer-implemented method of claim 1 , wherein each of the multiple versions of the data point comprises a distinct value corresponding to a distinct Euclidean space that is a coarser-grained Euclidean space than a preceding version of the data point.
5. The computer-implemented method of claim 1 , wherein said generating the multiple versions of the data point comprises dividing, repeatedly over one or more iterations, the value of a given version of the data point by a pre-determined number.
6. The computer-implemented method of claim 1 , wherein said encrypting comprises encrypting each of the multiple versions of the data point using a disjunctive normal form homomorphic semantically secure encryption (2DNF-sHE) scheme.
7. The computer-implemented method of claim 1 , wherein the multiple databases are stored on a cloud platform.
8. The computer-implemented method of claim 1 , wherein said executing the one or more distance-based algorithms on the multiple encrypted versions of the data point comprises executing the one or more distance-based algorithms on the multiple encrypted versions of the data point using a disjunctive normal form homomorphic semantically secure encryption (2DNF-sHE) scheme.
9. The computer-implemented method of claim 1 , wherein the one or more distance-based algorithms comprises a k-nearest neighbors algorithm.
10. The computer-implemented method of claim 1 , wherein the one or more distance-based algorithms comprises a k-means clustering algorithm.
11. The computer-implemented method of claim 1 , wherein the finite decryption table is stored on a cloud platform.
12. A computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computing device to cause the computing device to:
generate multiple versions of a data point, wherein each of the multiple versions of the data point comprises a distinct value corresponding to a distinct Euclidean space;
encrypt each of the multiple versions of the data point;
storing the multiple encrypted versions of the data point across multiple databases;
and execute one or more distance-based algorithms on the multiple encrypted versions of the data point by using a finite decryption table across the multiple databases, wherein the finite decryption table stores a set of plaintext-ciphertext mappings between (i) multiple plaintext values and (ii) multiple encrypted ciphertext values corresponding to the multiple plaintext values.
13. The computer program product of claim 12 , wherein said generating the multiple versions of the data point comprises dividing, repeatedly over one or more iterations, the value of a given version of the data point by a pre-determined number.
14. The computer program product of claim 12 , wherein said encrypting comprises encrypting each of the multiple versions of the data point using a disjunctive normal form homomorphic semantically secure encryption (2DNF-sHE) scheme.
15. The computer program product of claim 12 , wherein said executing the one or more distance-based algorithms on the multiple encrypted versions of the data point comprises executing the one or more distance-based algorithms on the multiple encrypted versions of the data point using a disjunctive normal form homomorphic semantically secure encryption (2DNF-sHE) scheme.
16. The computer program product of claim 12 , wherein the one or more distance-based algorithms comprises a k-nearest neighbors algorithm.
17. The computer program product of claim 12 , wherein the one or more distance-based algorithms comprises a k-means clustering algorithm.
18. The computer program product of claim 12 , wherein the multiple encrypted ciphertext values comprise multiple 2DNF-encrypted ciphertext values.
19. A system comprising:
a memory; and
at least one processor operably coupled to the memory and configured for:
generating multiple versions of a data point, wherein each of the multiple versions of the data point comprises a distinct value corresponding to a distinct Euclidean space;
encrypting each of the multiple versions of the data point;
storing the multiple encrypted versions of the data point across multiple databases; and
executing one or more distance-based algorithms on the multiple encrypted versions of the data point by using a finite decryption table across the multiple databases, wherein the finite decryption table stores a set of plaintext-ciphertext mappings between (i) multiple plaintext values and (ii) multiple encrypted ciphertext values corresponding to the multiple plaintext values.
20. A computer-implemented method, the method comprising steps of:
generating multiple versions of a data point in a sequential order, wherein each of the multiple versions of the data point comprises a distinct value corresponding to a distinct Euclidean space that is decreasingly granular in comparison to the distinct Euclidean space corresponding to the preceding version of the data point in the sequential order;
encrypting each of the multiple versions of the data point;
generating a storage mechanism comprising multiple databases, wherein the storage mechanism is compatible with disjunctive normal form homomorphic semantically secure encryption (2DNF-sHE) schemes;
storing the multiple encrypted versions of the data point across the multiple databases; and
executing one or more distance-based algorithms on the multiple encrypted versions of the data point by using a decryption table across the multiple databases, wherein the decryption table comprises a decryption table limited to a finite set of values, and wherein the decryption table stores a set of plaintext-ciphertext mappings between (i) multiple plaintext values and (ii) multiple encrypted ciphertext values corresponding to the multiple plaintext values;
wherein the steps are carried out by at least one computing device.