Enabling distance-based operations on data encrypted using a homomorphic encryption scheme with inefficient decryption

Patent metadata

Field	Value
Publication number	US-10693628-B2
Application number	US-201815971230-A
Country	US
Kind code	B2
Filing date	May 4, 2018
Priority date	May 4, 2018
Publication date	Jun 23, 2020
Grant date	Jun 23, 2020

Abstract

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.

First claim

What is claimed is:

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.

Assignees

• IBM

Inventors

• Singh Gagandeep
• Kaul Akshar
• Kesarwani Manish
• Mehta Sameep

Classifications

• G06F21/6227 Primary

  where protection concerns the structure of data, e.g. records, types, queries · CPC title

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• G06F18/21355

  nonlinear criteria, e.g. embedding a manifold in a Euclidean space · CPC title

• G06F21/6218

  to a system of files or objects, e.g. local or distributed file system or database · CPC title

• H04L9/0618

  Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation · CPC title