Systems and methods for end-to end-encryption with encrypted multi-maps

Abstract

According to some aspects, provided are systems and methods that implement end-to-end encryption, and provide implementation configured to secure information during execution of queries on an encrypted data source. Various embodiments include multiple encrypted multi-map data structures and associated encryption schemes configured to securely read, write, and delete information while supporting any one or more of the following features: snapshot security, multiple client support, efficient execution under concurrent operation, and resilience to client failures. In various embodiments, addressable multi-map data structures enable concurrent access, and allow correct operation under polynomial time constraints.

What is claimed is: 
     
         1 . A database system comprising:
 at least one processor operatively connected to a memory, the at least one processor when executing configured to:   manage a distributed database, the distributed database configured to:
 provide end-to-end encryption of plaintext data; 
 receive encrypted representations of the plaintext data and store encryptions of the plaintext data in at least one encrypted multi-map data structure comprising label and tuple pairs; 
 accept and process queries from a plurality of clients, such that the queries operate on and retrieve encrypted data from the at least one multi-map data structure using the labels to identify data in the at least one multi-map data structure; 
 enforce security against a snapshot adversary during execution of database functions so that correlation between edits on an encrypted dictionary are obscured; and 
 execute the database functions under stateless constraints using the encrypted dictionary. 
   
     
     
         2 . The system of  claim 1 , wherein the at least one processor is configured to retrieve and write the encrypted data using multi-dimension labels. 
     
     
         3 . The system of  claim 1 , wherein the at least one processor is configured to enable concurrent access to the encrypted data based at least in part on multi-dimension labels. 
     
     
         4 . The system of  claim 3 , wherein the at least one processor is configured to employ read tokens for data retrieval based on use of a first read token for a first component of a multi-dimension label and use of a second read token for a second component of the multi-dimension label. 
     
     
         5 . The system of  claim 1 , wherein the at least one processor is configured to execute initialization, write, read, and erase operations for the encrypted data under polynomial time constraints. 
     
     
         6 . The system of  claim 1 , wherein the at least one processor is configured to conceal correlations from a snapshot adversary based at least in part on executing edits under an immutable constraint. 
     
     
         7 . The system of  claim 6 , wherein the at least one processor is configured to manage an encrypted multi-map data structure and execute dictionary edit operations based at least in part on executing append operations to the multi-map data structure. 
     
     
         8 . The system of  claim 7 , wherein the at least one processor is configured to manage the encrypted multi-map data structure and operations under a completeness constraint. 
     
     
         9 . The system of  claim 2 , wherein the at least one processor is configured to generate an encrypted data structure for managing metadata about the encrypted data. 
     
     
         10 . The system of  claim 9 , wherein the at least one processor is configured to execute an encryption scheme configured to manage information on items deleted from the encrypted data. 
     
     
         11 . The system of  claim 10 , wherein the at least one processor is configured to execute an encryption scheme configured to manage auxiliary data structures. 
     
     
         12 . A computer implementation method for managing encrypted database data, the method comprising:
 managing, by at least one processor, a distributed database to provide end-to-end encryption of plaintext data;   storing, by the at least one processor, encrypted representations of the plaintext data in at least one encrypted multi-map data structure comprising label and tuple pairs;   operating, by the at least one processor, on the encrypted representation of the plaintext data, wherein operating on includes accepting and processing queries from a plurality of clients, such that execution of the queries operate on and retrieve encrypted data, from the at least one encrypted multi-map data structure using the labels to identify data in the at least one encrypted multi-map data structure and to communicate to the plurality of clients;   enforcing, by the at least one processor, security against a snapshot adversary during execution of database functions so that correlation between edits on an encrypted dictionary are obscured; and   executing, by the at least one processor, the database functions under stateless constraints using the encrypted dictionary.   
     
     
         13 . The method of  claim 12 , wherein the at least one processor is configured to retrieve and write the encrypted data using multi-dimension labels. 
     
     
         14 . The method of  claim 12 , wherein the method further comprises enabling concurrent access to the encrypted data based at least in part on multi-dimension labels. 
     
     
         15 . The method of  claim 14 , wherein the method comprises generating read tokens for data retrieval based on employing a first read token for a first component of a multi-dimension label and a second read token for a second component of the multi-dimension label. 
     
     
         16 . The method of  claim 12 , wherein the method comprises executing initialization, write, read, and erase operations for the encrypted data under polynomial time constraints. 
     
     
         17 . The method of  claim 12 , wherein the method comprises concealing correlations from a snapshot adversary based at least in part on executing edits under an immutable constraint. 
     
     
         18 . The method of  claim 17 , wherein the method comprises managing an encrypted multi-map data structure and executing dictionary edit operations based at least in part on executing append operations to the multi-map data structure. 
     
     
         19 . The method of  claim 18 , wherein the method comprises managing the encrypted multi-map data structure and operations under a completeness constraint. 
     
     
         20 . The method of  claim 12 , wherein the method comprises generating an encrypted data structure for managing metadata about the encrypted data.