Homomorphic encryption for database querying
View Patent ↗This disclosure concerns homomorphic encryption for database querying. Numerical values are encrypted using keys and random numbers to produce a ciphertext. The ciphertext is homomorphic and is comprised of two or more sub-ciphertexts. Queries based on addition, average and multiplication operations can be performed without decrypting the numerical values relevant to the query. Each sub-ciphertext is stored in a single record and in separate attributes. There is disclosed methods of encrypting and decrypting, creating a suitable table, querying such a database and updating such a database.
1. A computer implemented method for performing a query on a database, wherein a numerical value subject of the query is represented as a ciphertext determined using additive homomorphic encryption, and the ciphertext is comprised of multiple parts including at least a first sub-ciphertext and a second sub-ciphertext, the method comprising:
storing the first sub-ciphertext and the second sub-ciphertext in the database, wherein the first sub-ciphertext and the second sub-ciphertext are part components of the ciphertext such that decryption of the ciphertext requires at least the first sub-ciphertext and the second sub-ciphertext, the first sub-ciphertext and the second sub-ciphertext are stored in separate attributes in the database, and are each determined based on whole of the numerical value, wherein the second sub-ciphertext is determined independently of the determination of the first sub-ciphertext;
generating a query involving a computation to be performed on the first sub-ciphertext and the second sub-ciphertext stored in the database; and
performing the computation on the first sub-ciphertext and the second sub-ciphertext to determine an encrypted answer to the query without requiring decryption of the first sub-ciphertext and the second sub-ciphertext.
2. The computer implemented method of claim 1 , wherein the additive homomorphic encryption is also multiplicative homomorphic.
3. The computer implemented method of claim 1 , wherein the method further comprises a step of:
determining the ciphertext based on a key that is comprised of a set of key components, wherein the number of key components in the set of key components is equal to the number of sub-ciphertexts.
4. The computer implemented method of claim 3 , wherein the method further comprises:
determining the set of key components based on the number of sub-ciphertexts.
5. The computer implemented method of claim 3 , wherein the key satisfies the following equation:
Σ i=1 n ƒ i ( K ( n ))*Value i ( K ( n ), V )= V
where
V is the numeric value,
n is the number of sub-ciphertexts,
K(n) is the key,
ƒ i is a i th function over the key, and
Value i is a i th function over K(n) and V.
6. The computer implemented method of claim 3 , wherein determining the ciphertext comprises determining sub-ciphertexts that satisfy the following equation:
Σ i=1 n ƒ i ( K ( n ))* V i =V
where
V is the numeric value,
n is the number of sub-ciphertexts,
K(n) is the key,
ƒ i is a i th function over the key, and
V i is a i th sub-ciphertext.
7. The computer implemented method of claim 3 , wherein determining the ciphertext comprises determining sub-ciphertexts satisfy the following equation:
V i =Value i ( K ( n ), V )+Noise i ( K ( n ), R )
where
V is the numeric value,
n is the number of sub-ciphertexts,
K(n) is the key,
R is a set of random numbers,
V i is the i th sub-ciphertext,
Value i is a i th function over K(n) and V, and
Noise i is a i th function over K(n) and R.
8. The computer implemented method of claim 1 , wherein the method comprises the step of:
determining the ciphertext by adding for each sub-ciphertext a first result and a second result, where the first result is the value of a function based on a key associated with that sub-ciphertext and the numerical value, and the second result is the value of a function based on the key associated with that sub-ciphertext and one or more random numbers.
9. The computer implemented method of claim 1 , wherein the method comprises the step of:
determining the ciphertext that does not comprise the use of a modulo or floor arithmetic operation.
10. The computer implemented method of claim 1 , wherein the method further comprises the steps of:
determining a set of random number components; and
determining the ciphertext based on the set of random number components.
11. The computer implemented method according to claim 10 , wherein determining the ciphertext is based on a key that is comprised of a set of key components, wherein the number of key components in the set of key components is equal to the number of sub-ciphertexts, and determining the set of random number components comprises determining a set of random numbers that satisfies the following equation:
Σ i=1 n ƒ i ( K ( n ))*Noise i ( K ( n ), R )=0
where
n is the number of sub-ciphertexts,
K(n) is the key,
ƒ i is a i th function over the key,
R is a set of random number components; and
Noise i is a i th function over K(n) and R.
12. The computer implemented method of claim 11 , wherein the equation is composable and the method further comprising:
fusing multiple instances of the key to create a new key instance.
13. A non-transitory computer readable medium comprising computer-executable instructions stored thereon that when executed cause the computer to perform a query on a database, wherein a numerical value subject of the query is represented as a ciphertext determined using additive homomorphic encryption, and the ciphertext is comprised of multiple parts including at least a first sub-ciphertext and a second sub-ciphertext, the method comprising:
storing the first sub-ciphertext and the second sub-ciphertext in the database, wherein the first sub-ciphertext and the second sub-ciphertext are part components of the ciphertext such that decryption of the ciphertext requires at least the first sub-ciphertext and the second sub-ciphertext, the first sub-ciphertext and the second sub-ciphertext are stored in separate attributes in the database, and are each determined based on whole of the numerical value, and wherein the second sub-ciphertext is determined independently of the determination of the first sub-ciphertext;
generating a query that involves a computation to be performed on the first sub-ciphertext and the second sub-ciphertext stored in the database; and
performing the computation on the first sub-ciphertext and the second sub-ciphertext to determine an encrypted answer to the query without requiring decryption of the first sub-ciphertext and the second sub-ciphertext.
14. A computer system for encryption of a numerical value to be stored in a database comprising:
a processor; and
a non-transitory computer readable medium storing code, which when executed by the processor, causes the processor to:
determine ciphertext for the numerical value using additive homomorphic encryption, wherein the ciphertext is comprised of multiple parts including at least a first sub-ciphertext and a second sub-ciphertext that are part components of the ciphertext such that decryption of the ciphertext requires at least the first sub-ciphertext and the second sub-ciphertext, and the first sub-ciphertext and the second sub-ciphertext are determined based on whole of the numerical value, and the second sub-ciphertext is determined independently of the determination of the first sub-ciphertext; and
cause the first sub-ciphertext and the second sub-ciphertext to be stored in separate attributes in the database, such that, in use, an encrypted result to a query involving a computation on the first sub-ciphertext and the second sub-ciphertext is determined by performing the computation without decryption of the first sub-ciphertext and the second sub-ciphertext, wherein the encrypted result is a ciphertext for a result of the computation performed on the numerical value.
15. A computer implemented method for accessing protected data stored in a database, the method comprising:
receiving or accessing ciphertext representing a numeric value subject of a query, the ciphertext determined using an additive homomorphic encryption, wherein the ciphertext is comprised of multiple parts including at least a first sub-ciphertext and a second sub-ciphertext that are part components of the ciphertext such that decryption of the ciphertext requires at least the first sub-ciphertext and the second sub-ciphertext, the first sub-ciphertext and the second sub-ciphertext are determined based on whole of the numerical value and stored in separate attributes, and the second sub-ciphertext is determined independently of the determination of the first sub-ciphertext; and
decrypting the ciphertext to determine a result of the query based on the first sub-ciphertext and the second sub-ciphertext and using an encryption key comprised of a set of key components, wherein the number of key components is the same as the number of sub-ciphertexts.
16. The computer implemented method of claim 1 , wherein the method further comprises:
decrypting the encrypted answer to the query based on keys used to encrypt the numerical value.
17. The computer implemented method of claim 1 , wherein the computation is a multiplication based query on the database, the computation comprising:
for each pair of numerical values subject of the query, performing an outer product of the sub-ciphertexts for that pair of numerical values to determine an encrypted multiplied value.
18. The computer implemented method of claim 1 , wherein the storing the first sub-ciphertext and the second sub-ciphertext is performed by creating a table having a first attribute to store the first sub-ciphertext and a second attribute to store the second sub-ciphertext.
19. The computer implemented method of claim 1 , wherein the method comprises storing the first sub-ciphertext and the second sub-ciphertext by inserting a record into the database having the separate attributes.