Accelerated encrypted database operations

Patent metadata

Field	Value
Publication number	US-9275249-B1
Application number	US-201313788749-A
Country	US
Kind code	B1
Filing date	Mar 7, 2013
Priority date	Mar 7, 2013
Publication date	Mar 1, 2016
Grant date	Mar 1, 2016

Abstract

Accelerated encrypted database operations may include a database receiving a modified database query and one or more decryption keys that correspond to the modified database query. Based, at least in part, on the modified database query and the one or more decryption keys, the database may generate partially decrypted query results. The database may submit the partially decrypted query results to an encryption manager for further decryption by an offload processor to generate further decrypted query results.

First claim

What is claimed is:

1. A system, comprising:
an encryption manager configured to:
receive a query for an encrypted database,
generate a query plan from the received query that indicates one or more storage representations of the encrypted database from which to retrieve data, and
submit, to the encrypted database, the query plan and a token that includes one or more decryption keys corresponding to the one or more storage representations; and

the encrypted database that includes the one more storage representations, wherein the encrypted database is configured to:
use the one or more decryption keys to generate partially decrypted data from the indicated one or more storage representations, wherein to use the one or more decryption keys to generate partially decrypted data, the encrypted database is further configured to decrypt a respective outer encryption layer of the indicated one or more storage representations with the one or more decryption keys into corresponding one or more working representations, wherein the one or more working representations include a respective mapping of field values in an property preserving manner without revealing underlying field values, and
provide the partially decrypted data to the encryption manager for further decryption operations by a query offload processor.

2. The system of claim 1 , wherein the encrypted database is further configured to create a work token from the token for each of the one or more working representations, wherein each work token is configured to enforce an authorization constraint on the corresponding working representation.

3. The system of claim 1 , wherein each of the one or more storage representations is associated with a different respective set of one or more types of query operations.

4. A method, comprising:
performing, by one or more computers:
a database receiving a modified database query and one or more decryption keys that correspond to the modified database query;
based, at least in part, on the modified database query and the one or more decryption keys, the database generating partially decrypted query results, wherein said generating partially decrypted query results is performed using one or more storage representations of the database that are selected, based, at least in part, on the modified database query and comprises:
decrypting a respective outer encryption layer of the one or more storage representations with the received one or more decryption keys into corresponding one or more working representations, wherein the one or more working representations include a respective mapping of field values in an property preserving manner without revealing underlying field values; and

the database submitting the partially decrypted query results to an encryption manager for further decryption by an offload processor to generate further decrypted query results.

5. The method of claim 4 , wherein the database includes a plurality of storage representations of data, wherein the storage representations preserve at least one property of the data and obscure at least one other property, wherein the storage representations differ from one another by which property is preserved, and wherein the storage representations include a respective outer layer of encryption corresponding to a respective one of the one of more decryption keys.

6. The method of claim 5 , wherein said generating partially decrypted query results includes, for at least one of the storage representations, decrypting the respective outer layer of encryption with the corresponding decryption key.

7. The method of claim 4 , wherein the received one or more decryption keys are received as part of a variadic authentication token that is a modified version of a client authentication token from a client, further comprising:
the database generating a respective work token corresponding to each working representation, wherein the work tokens are based, at least in part, on the variadic authentication token, and wherein the work tokens indicate one or more authorization constraints on the working representations.

8. The method of claim 4 , wherein the working representations are time constrained temporary storage locations.

9. The method of claim 4 , wherein each of the one or more storage representations is associated with a different respective set of one or more types of query operations.

10. The method of claim 4 , further comprising:
determining that a type of query indicated in an original query, from which the modified database query is derived, is not supported by the one or more storage representations; and
providing a portion of the original query corresponding to the type of query to the offload processor that is separate from the database for processing by the offload processor.

11. The method of claim 4 , further comprising providing the further decrypted query results to a client that provided an original query from which the modified database query was derived.

12. The method of claim 4 , wherein the modified database query is based, at least in part, on a projected pattern of field accesses determined from an original query.

13. The method of claim 4 , wherein the received one or more keys are selected based, at least in part, on the modified database query.

14. The method of claim 4 , wherein the modified database query is determined based, at least in part, on security and performance factors.

15. The method of claim 4 , wherein one of the one or more decryption keys is replaced based on a tracked amount of data partially decrypted by the one of the one or more decryption keys meeting a threshold value.

16. A non-transitory computer-readable storage medium storing program instructions, wherein the program instructions are computer-executable to implement:
receiving a query plan and one or more decryption keys corresponding to one or more storage representations;
partially decrypting, based at least in part on the one or more decryption keys, data from one or more storage representations that are associated with the received query plan into a respective working representation for each of the one or more storage representations, wherein partially decrypting comprises decrypting a respective outer encryption layer of the one or more storage representations with the one or more decryption keys into the respective working representation for each of the one or more storage representations, wherein the respective working representations include a respective mapping of field values in an property preserving manner without revealing underlying field values; and
providing the partially decrypted data from the one or more working representations for further decryption operations.

17. The non-transitory computer-readable storage medium of claim 16 , wherein the one or more storage representations are different representations of the same data, and wherein the one or more storage representations each include a respective first level of encryption that retains less than all properties of the data and a respective second level of encryption.

18. The non-transitory computer-readable storage medium of claim 16 , wherein said partially decrypting data includes applying the respective decryption keys to the corresponding one or more storage representations.

Assignees

• Amazon Tech Inc

Inventors

• Allen Nicholas Alexander

Classifications

• G06F21/6218 Primary

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

• G06F2221/2107

  File encryption · CPC title

• G06F21/6227 Primary

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