Efficient encrypted data management system and method

• US 10,469,246 B2
• Filed: 02/28/2017
• Issued: 11/05/2019
• Est. Priority Date: 02/29/2016
• Status: Active Grant

• Current Assignee: Craxel, Inc.
• Original Assignee: Craxel, Inc.
• Inventors: Enga, David
• Primary Examiner(s): Song, Hee K
• Application Number:
  US15/445,104
• Publication Number:
  US 20170250798A1
• Time in Patent Office: 980 Days
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0819 Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) network architectures or network communication protocols for key distribution in a packet data network H04L63/062
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• 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

Abstract

A method for performing an encrypted data operation may include generating an encrypted hierarchical path identifier corresponding to a hierarchical data space for at least one plaintext data operation that preserves the hierarchy of the hierarchical data space. The at least one plaintext data operation may correspond to at least one subdivision of the hierarchical data space. The method may further include encrypting the at least one plaintext data operation, and sending a request to perform an encrypted data operation to a server. The request may include the encrypted data operation and the encrypted hierarchical path identifier.

Claims

1. A system for implementing an encrypted data operation, the system comprising:

a memory that stores instructions; and

a processor that executes the instructions to perform operations, the operations comprising;

generating an encrypted hierarchical path identifier corresponding to a hierarchical data space for at least one plaintext data operation that preserves a hierarchy of the hierarchical data space, wherein the at least one plaintext data operation corresponds to at least one subdivision of the hierarchical data space;

encrypting the at least one plaintext data operation; and

sending a request to perform an encrypted data operation to a server, wherein the request comprises the encrypted data operation and the encrypted hierarchical path identifier, wherein the operation of generating the encrypted hierarchical path identifier comprises;

determining the at least one subdivision to which the at least one plaintext data operation corresponds;

calculatinq a secret permutation for each of the at least one subdivision;

and generating an encrypted label for each of the at least one subdivision using the corresponding secret permutation.

2. The system of claim 1, wherein the operations further comprise generating the hierarchical data space comprising recursively subdividing a data space that corresponds to the at least one plaintext operation into at least two levels of subdivision.

3. The system of claim 2, wherein at least an initial subdivision of the data space is based on parameters generated using a secret key.

4. The system of claim 2, wherein the encrypted path identifier comprises the encrypted label generated for the at least one subdivision.

5. The system of claim 1, wherein the operation of generating the encrypted hierarchical path identifier comprises obscuring ordering within the hierarchical data space with respect to the encrypted hierarchical path identifier.

6. The system of claim 1, wherein the operations further comprise:

generating at least one additional encrypted hierarchical path identifier corresponding to a different hierarchical data space for the at least one plaintext data operation that preserves the hierarchy of the different hierarchical data space, wherein the at least one plaintext data

operation corresponds to at least one subdivision of the different hierarchical data space;

and sending the at least one additional encrypted hierarchical path identifier with the

request to perform the encrypted data operation to the server.

7. The system of claim 1, wherein the operations further comprise:

determining at least one partition of an encrypted hierarchical data space containing the encrypted hierarchical path identifier; and

selecting at least one server associated with the at least one partition containing the encrypted hierarchical path identifier, and wherein the operation of sending the request to perform the encrypted data operation to the server comprises sending the request to the selected at least one server.

8. A method for implementing an encrypted data operation, the method comprising:

generating, by utilizing instructions from a memory that are executed by a processor, an encrypted hierarchical path identifier corresponding to a hierarchical data space for at least one plaintext data operation that preserves the hierarchy of the hierarchical data space, wherein the at least one plaintext data operation corresponds to at least one subdivision of the hierarchical data space;

encrypting the at least one plaintext data operation; and

sending a request to perform an encrypted data operation to a server, wherein the request comprises the encrypted data operation and the encrypted hierarchical path identifier, wherein generating the encrypted hierarchical path identifier comprises;

determining the at least one subdivision to which the at least one plaintext data operation corresponds;

calculating a secret permutation for each of the at least one subdivision; and

qeneratinq an encrypted label for each of the at least one subdivision using the corresponding secret permutation.

9. The method of claim 8, further comprising generating the hierarchical data space comprising recursively subdividing a data space that corresponds to the at least one plaintext operation into at least two levels of subdivision.

10. The method of claim 9, wherein at least an initial subdivision of the data space is based on parameters generated using a secret key.

11. The method of claim 9, wherein the encrypted path identifier comprises the encrypted label generated for the at least one subdivision.

12. The method of claim 8, wherein generating the encrypted hierarchical path identifier comprises obscuring ordering within the hierarchical data space with respect to the encrypted hierarchical path identifier.

13. The method of claim 8, further comprising:

generating at least one additional encrypted hierarchical path identifier corresponding to a different hierarchical data space for the at least one plaintext data operation that preserves the hierarchy of the different hierarchical data space, wherein the at least one plaintext data operation corresponds to at least one subdivision of the different hierarchical data space; and

sending the at least one additional encrypted hierarchical path identifier with the request to perform the encrypted data operation to the server.

14. The method of claim 8, further comprising:

determining at least one partition of an encrypted hierarchical data space containing the encrypted hierarchical path identifier; and

selecting at least one server associated with the at least one partition containing the encrypted hierarchical path identifier, and wherein sending the request to perform the encrypted data operation to the server comprises sending the request to the selected at least one server.

15. A non-transitory computer readable device, which when loaded and executed by a processor, causes the processor to perform operations comprising:

generating an encrypted hierarchical path identifier corresponding to a hierarchical data space for at least one plaintext data operation that preserves a hierarchy of the hierarchical data space, wherein the at least one plaintext data operation corresponds to at least one subdivision of the hierarchical data space;

encrypting the at least one plaintext data operation; and

sending a request to perform an encrypted data operation to a server, wherein the request comprises the encrypted data operation and the encrypted hierarchical path identifier, wherein the operation of qeneratinq the encrypted hierarchical path identifier comprises;

determining the at least one subdivision to which the at least one plaintext data operation corresponds;

calculatinq a secret permutation for each of the at least one subdivision; and

qeneratinq an encrypted label for each of the at least one subdivision using the corresponding secret permutation.

16. The non-transitory computer readable device of claim 15, wherein the operations further comprise generating the hierarchical data space comprising recursively subdividing a data space that corresponds to the at least one plaintext operation into at least two levels of subdivision.

17. The non-transitory computer readable device of claim 16, wherein at least an initial subdivision of the data space is based on parameters generated using a secret key.

18. The non-transitory computer readable device of claim 16, wherein the encrypted path identifier comprises the encrypted label generated for the at least one subdivision.

19. The non-transitory computer readable device of claim 15, wherein the operation of generating the encrypted hierarchical path identifier comprises obscuring ordering within the hierarchical data space with respect to the encrypted hierarchical path identifier.

20. The non-transitory computer readable device of claim 15, wherein the operations further comprise:

generating at least one additional encrypted hierarchical path identifier corresponding to a different hierarchical data space for the at least one plaintext data operation that preserves the hierarchy of the different hierarchical data space, wherein the at least one plaintext data operation corresponds to at least one subdivision of the different hierarchical data space; and

sending the at least one additional encrypted hierarchical path identifier with the request to perform the encrypted data operation to the server.

21. The non-transitory computer readable device of claim 15, wherein the operations further comprise:

determining at least one partition of an encrypted hierarchical data space containing the encrypted hierarchical path identifier; and

selecting at least one server associated with the at least one partition containing the encrypted hierarchical path identifier, and wherein the operation of sending the request to perform the encrypted data operation to the server comprises sending the request to the selected at least one server.

22. A system for performing an encrypted data operation, the system comprising:

a memory that stores instructions; and

a processor that executes the instructions to perform operations, the operations comprising;

receiving an encrypted data operation and a first encrypted hierarchical path identifier from a client;

finding at least one data index node of at least one data index using the first encrypted hierarchical path identifier; and

sending the encrypted results of the encrypted data operation to the client, wherein the client generating the first encrypted hierarchical path identifier by;

determining the at least one subdivision to which the at least one plaintext data operation corresponds;

calculating a secret permutation for each of the at least one subdivision; and

generating an encrypted label for each of the at least one subdivision using the corresponding secret permutation.

23. The system of claim 22, wherein the encrypted data operation is a mutation, and wherein the operations further comprise executing the encrypted data operation within the at least one data index node.

24. The system of claim 22, wherein the encrypted data operation is a query, and wherein the operations further comprise:

receiving a second different encrypted hierarchical path identifier associated with the encrypted data operation;

searching for encrypted data tuples that are associated with a first encrypted hierarchical path identifier matching the first encrypted hierarchical path identifier;

searching for encrypted data tuples that are associated with the second different encrypted hierarchical path identifier that matches the second different encrypted hierarchical path identifier; and

sending the encrypted data tuples identified in the search to the client.

25. A method for performing an encrypted data operation, the method comprising:

receiving an encrypted data operation and a first encrypted hierarchical path identifier from a client;

finding, by utilizing instructions from a memory that are executed by a processor, at least one data index node of at least one data index using the first encrypted hierarchical path identifier; and

sending the encrypted results of the encrypted data operation to the client, wherein the client generating the first encrypted hierarchical path identifier by;

determining the at least one subdivision to which the at least one plaintext data operation corresponds;

calculating a secret permutation for each of the at least one subdivision; and

generating an encrypted label for each of the at least one subdivision using the corresponding secret permutation.

26. The method of claim 25, wherein the encrypted data operation is a mutation, and wherein the method further comprises executing the encrypted data operation within the at least one data index node.

27. The method of claim 25, wherein the encrypted data operation is a query, and wherein the method further comprises:

receiving a second different encrypted hierarchical path identifier associated with the encrypted data operation;

searching for encrypted data tuples that are associated with a first encrypted hierarchical path identifier matching the first encrypted hierarchical path identifier;

searching for encrypted data tuples that are associated with the second different encrypted hierarchical path identifier that matches the second different encrypted hierarchical path identifier; and

sending the encrypted data tuples identified in the search to the client.

28. A non-transitory computer readable device, which when loaded and executed by a processor, causes the processor to perform operations comprising:

receiving an encrypted data operation and a first encrypted hierarchical path identifier from a client;

finding at least one data index node of at least one data index using the first encrypted hierarchical path identifier; and

sending the encrypted results of the encrypted data operation to the client, wherein the client generating the first encrypted hierarchical path identifier by;

determining the at least one subdivision to which the at least one plaintext data operation corresponds;

calculating a secret permutation for each of the at least one subdivision; and

generating an encrypted label for each of the at least one subdivision using the corresponding secret permutation.

29. The non-transitory computer readable device of claim 28, wherein the encrypted data operation is a mutation, and wherein the operations further comprise executing the encrypted data operation within the at least one data index node.

30. The non-transitory computer readable device of claim 28, wherein the encrypted data operation is a query, and wherein the operations further comprise:

receiving a second different encrypted hierarchical path identifier associated with the encrypted data operation;

searching for encrypted data tuples that are associated with a first encrypted hierarchical path identifier matching the first encrypted hierarchical path identifier;

searching for encrypted data tuples that are associated with the second different encrypted hierarchical path identifier that matches the second different encrypted hierarchical path identifier; and

sending the encrypted data tuples identified in the search to the client.