Filtering encrypted data using indexes

• US 10,594,490 B2
• Filed: 04/24/2017
• Issued: 03/17/2020
• Est. Priority Date: 04/24/2017
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Hersans, Alexandre
• Primary Examiner(s): Abyaneh, Ali S
• Application Number:
  US15/495,685
• Publication Number:
  US 20180307763A1
• Time in Patent Office: 1,058 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

During an encryption process, a database system may generate an index value based on the plaintext to be encrypted, an encryption key, a data field-specific salt, or a combination thereof. The database may store the index value in an index associated with the ciphertext output of the encryption process. In some cases, the database may receive a query specifying a plaintext value for filtering on a data field, where the database may return data objects with the specified plaintext value in the given data field. The database may compute a set of index values associated with the specified plaintext, and may identify indexes with index values included in the set of index values and associated with the given data field. The database may decrypt the ciphertexts associated with the identified indexes to check if they match the specified plaintext.

Claims

1. A method for storing encrypted data, comprising:

storing a first ciphertext associated with a first plaintext in a data field of a database;

storing a second ciphertext associated with a second plaintext in the data field, wherein the first plaintext and the second plaintext are different;

generating a first index for the first plaintext and a second index for the second plaintext using an indexing function, wherein an index value of the first index and an index value of the second index are the same;

receiving a query request message including a request to filter on the first plaintext for the data field;

determining a set of index values associated with the first plaintext using the indexing function, wherein the set of index values comprises the index value of the first index and the second index, wherein determining the set of index values is based at least in part on the query request message and wherein the indexing function implements collisions to generate the same index value for the first index and the index value for the second index using the first plaintext and the second plaintext different from the first plaintext; and

identifying, for a set of ciphertexts stored in the data field, all indexes with index values included in the determined set of index values.

2. The method of claim 1, further comprising:

decrypting the first ciphertext and the second ciphertext based at least in part on identifying that the index value of the first index and the second index is included in the determined set of index values.

3. The method of claim 2, wherein the first ciphertext and the second ciphertext are decrypted within the database.

4. The method of claim 1, further comprising:

adjusting a selectivity of the indexing function, wherein the selectivity comprises a ratio between a quantity of the identified indexes and a total quantity of the set of ciphertexts stored in the data field.

5. The method of claim 1, further comprising:

storing a third ciphertext associated with a third plaintext in the data field, wherein the first plaintext and the third plaintext are the same; and

generating a third index for the third plaintext using the indexing function, wherein an index value of the third index is different than the index value of the first index.

6. The method of claim 5, wherein the indexing function is based at least in part on a set of encryption keys, wherein the first index is generated based at least in part on a first encryption key of the set of encryption keys and the third index is generated based at least in part on a second encryption key of the set of encryption keys.

7. The method of claim 1, further comprising:

storing a fourth ciphertext associated with a fourth plaintext in a second data field of the database; and

generating a fourth index for the fourth plaintext using a different indexing function than the indexing function used to generate the first index and second index.

8. The method of claim 7, wherein the data field has an associated first salt value and the second data field has an associated second salt value, wherein the indexing function used to generate the first index and second index is based at least in part on the first salt value and the different indexing function used to generate the fourth index is based at least in part on the second salt value.

9. The method of claim 1, wherein the indexing function is a secure hash function.

10. The method of claim 1, wherein generating the first index for the first plaintext is based at least in part on a first message authentication code (MAC) associated with the first plaintext, and wherein generating the second index for the second plaintext is based at least in part on a second MAC associated with the second plaintext.

11. The method of claim 1, wherein the index value is a numeric value.

12. An apparatus for storing encrypted data, in a system comprising:

a processor;

memory in electronic communication with the processor; and

instructions stored in the memory and operable, when executed by the processor, to cause the apparatus to;

store a first ciphertext associated with a first plaintext in a data field of a database;

store a second ciphertext associated with a second plaintext in the data field, wherein the first plaintext and the second plaintext are different;

generate a first index for the first plaintext and a second index for the second plaintext using an indexing function, wherein an index value of the first index and an index value of the second index are the same;

receive a query request message including a request to filter on the first plaintext for the data field;

determine a set of index values associated with the first plaintext using the indexing function, wherein the set of index values comprises the index value of the first index and the second index, wherein determining the set of index values is based at least in part on the query request message and wherein the indexing function implements collisions to generate the same index value for the first index and the index value for the second index using the first plaintext and the second plaintext different from the first plaintext; and

identify, for a set of ciphertexts stored in the data field, all indexes with index values included in the determined set of index values.

13. The apparatus of claim 12, wherein the instructions are further executable by the processor to:

decrypt the first ciphertext and the second ciphertext based at least in part on identifying that the index value of the first index and the second index is included in the determined set of index values.

14. The apparatus of claim 12, wherein the instructions are further executable by the processor to:

adjust a selectivity of the indexing function, wherein the selectivity comprises a ratio between a quantity of the identified indexes and a total quantity of the set of ciphertexts stored in the data field.

15. A non-transitory computer readable medium storing code for storing encrypted data, the code comprising instructions executable by a processor to:

store a first ciphertext associated with a first plaintext in a data field of a database;

store a second ciphertext associated with a second plaintext in the data field, wherein the first plaintext and the second plaintext are different;

generate a first index for the first plaintext and a second index for the second plaintext using an indexing function, wherein an index value of the first index and an index value of the second index are the same;

receive a query request message including a request to filter on the first plaintext for the data field;

determine a set of index values associated with the first plaintext using the indexing function, wherein the set of index values comprises the index value of the first index and the second index, wherein determining the set of index values is based at least in part on the query request message and wherein the indexing function implements collisions to generate the same index value for the first index and the index value for the second index using the first plaintext and the second plaintext different from the first plaintext; and

identify, for a set of ciphertexts stored in the data field, all indexes with index values included in the determined set of index values.

16. The non-transitory computer-readable medium of claim 15, wherein the instructions are further executable by the processor to:

decrypt the first ciphertext and the second ciphertext based at least in part on identifying that the index value of the first index and the second index is included in the determined set of index values.

17. The non-transitory computer-readable medium of claim 15, wherein the instructions are further executable by the processor to:

adjust a selectivity of the indexing function, wherein the selectivity comprises a ratio between a quantity of the identified indexes and a total quantity of the set of ciphertexts stored in the data field.