Secure analytics using homomorphic encryption

• US 10,644,876 B2
• Filed: 01/19/2018
• Issued: 05/05/2020
• Est. Priority Date: 01/20/2017
• Status: Active Grant

• Current Assignee: Enveil, Inc.
• Original Assignee: Enveil, Inc.
• Inventors: Williams, Ellison Anne, Carr, Ryan
• Primary Examiner(s): Poltorak, Piotr
• Application Number:
  US15/876,024
• Publication Number:
  US 20180212754A1
• Time in Patent Office: 837 Days
• Field of Search: None
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 21/30 Authentication, i.e. establishing the identity or authorisation of security principals
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06N 3/04 Architecture, e.g. interconnection topology
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 7/08 using chaos models or non-linear system models
• CPC Class Codes: G09C 1/00 Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system cryptographic typewriters G09C3/00
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/14 : using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/30 : Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/302 : involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3242 : involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

Provided are methods and systems for performing a secure analytic over a data source. An example method includes acquiring, by a client, an analytic, at least one analytic parameter associated with the analytic, and an encryption scheme. The encryption scheme can include a public key for encryption and a private key for decryption. The method further includes generating, using the encryption scheme, at least one analytical vector based on the analytic and analytic parameter, and sending the analytical vector and the encryption scheme to at least one server. The method includes extracting, by the at least one server based on the encryption scheme, a set of terms from a data set, and evaluating the analytical vector over the set of terms to obtain an encrypted result. The method further includes sending, by the server, the encrypted result and the error to the client where the encrypted result is decrypted.

Claims

1. A method for performing a secure analysis using homomorphic encryption, the method comprising:

receiving, from a client, by at least one server, at least one analytic vector, the at least one analytic vector being encrypted using a homomorphic encryption scheme, a term generation function, and a keyed hash function, wherein the homomorphic encryption scheme includes a public key for encryption and a private key for decryption;

extracting, by the at least one server, a set of term components from a data set using the term generation function and the keyed hashed function;

evaluating, by the at least one server, the at least one analytic vector over the set of term components to obtain at least one encrypted result; and

sending, by the at least one server, the at least one encrypted result to the client, wherein the client is configured to decrypt the at least one encrypted result using the homomorphic encryption scheme,

wherein the at least one analytic vector is generated based on an analytic and at least one parameter associated with the analytic; and

wherein the generation of the at least one analytic vector includes;

extracting, using the term generation function, a set of term elements from the analytic and the at least one analytic parameter;

generating, using the keyed hash function, a set of hashes from the set of the term elements;

determining whether an index of at least one element of the at least one analytical vector is present in the set of hashes;

if the index is present in the set of hashes, assigning the at least one element to a non-zero value; and

if the index is not present in the set of hashes, assigning the at least one element a zero value.

2. The method of claim 1, wherein the homomorphic encryption scheme includes a partially homomorphic encryption scheme.

3. The method of claim 2, wherein the partially homomorphic encryption scheme includes at least one of a Rivest, Shamir and Adleman cryptosystem, an Elgamal cryptosystem, a Benaloh cryptosystem, a Goldwasser-Micali cryptosystem, and a Pallier cryptosystem.

4. The method of claim 1, wherein the homomorphic encryption scheme includes a fully homomorphic encryption scheme.

5. The method of claim 1, wherein a dimension of the at least one analytic vector is greater than the number of elements in the set of term elements.

6. The method of claim 1, wherein the non-zero value is an encrypted value of a non-zero bitmask of a term element of the set of term elements, the hash of the term element being equal to the index, the encrypted value being obtained using the homomorphic encryption scheme.

7. The method of claim 1, wherein the data set is in a plaintext form.

8. The method of claim 1, wherein the data set is deterministically encrypted or semantically encrypted.

9. A system for performing a secure analysis using homomorphic encryption, the system comprising:

at least one processor; and

a memory communicatively coupled with the at least one processor, the memory storing instructions, which when executed by the at least one processor perform a method comprising;

receiving, from a client, at least one analytic vector, the at least one analytic vector being encrypted using a homomorphic encryption scheme, a term generation function, and a keyed hash function, wherein the homomorphic encryption scheme includes a public key for encryption and a private key for decryption;

extracting, by at least one server, a set of term components from a data set using the term generation function and the keyed hashed function;

evaluating the at least one analytic vector over the set of term components to obtain at least one encrypted result; and

sending the at least one encrypted result to the client, wherein the client is configured to decrypt the at least one encrypted result using the homomorphic encryption scheme,

wherein the client is configured to generate the at least one analytic vector based on an analytic and at least one parameter associated with the analytic; and

wherein the generation of the at least one analytic vector includes;

extracting, using the term generation function, a set of term elements from the analytic and the at least one analytic parameter;

generating, using the keyed hash function, a set of hashes from the set of the term elements;

determining whether an index of at least one element of the at least one analytical vector is present in the set of hashes;

if the index is present in the set of hashes, assigning the at least one element a non-zero value; and

if the index is not present in the set of hashes, assigning the at least one element a zero value.

10. The system of claim 9, wherein the homomorphic encryption scheme includes a partially homomorphic encryption scheme.

11. The system of claim 9, wherein the homomorphic encryption scheme includes at least one of a Rivest, Shamir and Adleman cryptosystem, an Elgamal cryptosystem, a Benaloh cryptosystem, a Goldwasser-Micali cryptosystem, and a Pallier cryptosystem.

12. The system of claim 9, wherein the homomorphic encryption scheme includes a fully homomorphic encryption scheme.

13. The system of claim 9, wherein a dimension of the at least one analytic vector is greater than the number of elements in the set of term elements.

14. The system of claim 9, wherein the non-zero value is an encrypted value of a non-zero bitmask of a term element of the set of term elements, the hash of the term element being equal to the index, the encrypted value being obtained using the homomorphic encryption scheme.

15. The system of claim 9, wherein the data set is in one of the following forms:

a plaintext, deterministically encrypted, and semantically encrypted.

16. A non-transitory computer-readable storage medium having embodied thereon instructions, which when executed by at least one processor, perform steps of a method, the method comprising:

receiving, by at least one server from a client,

at least one analytic vector, the at least one analytic vector being encrypted using a homomorphic encryption scheme, a term generation function, and a keyed hash function, wherein the homomorphic encryption scheme including a public key for encryption and a private key for decryption;

extracting, by the at least one server, a set of term components from a data set using the term generation function and the keyed hashed function;

evaluating, by the at least one server, the at least one analytic vector over the set of term components to obtain at least one encrypted result; and

sending, by the at least one server, the at least one encrypted result to the client, wherein the client is configured to decrypt the at least one encrypted result using the homomorphic encryption scheme,

wherein the at least one analytic vector is generated based on an analytic and at least one parameter associated with the analytic; and

wherein the generation of the at least one analytic vector includes;

extracting, using the term generation function, a set of term elements from the analytic and the at least one analytic parameter;

generating, using the keyed hash function, a set of hashes from the set of the term elements;

determining whether an index of at least one element of the at least one analytical vector is present in the set of hashes;

if the index is present in the set of hashes, assigning the at least one element to a non-zero value; and

if the index is not present in the set of hashes, assigning the at least one element a zero value.