Patent Publication Number: US-2023137882-A1

Title: Oblivious RAM with Logarithmic Overhead

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This U.S. patent application is a continuation of, and claims priority under 35 U.S.C. § 120 from, U.S. patent application Ser. No. 17/313,597, filed on May 6, 2021, which claims priority under 35 U.S.C. § 120 from, U.S. patent application Ser. No. 16/365,224, filed on Mar. 26, 2019, now U.S. Pat. No. 11,023,168, which claims priority under 35 U.S.C. § 119(e) to U.S. Provisional Application 62/653,762, filed on Apr. 6, 2018. The disclosures of these prior applications are considered part of the disclosure of this application and are hereby incorporated by reference in their entireties. 
    
    
     TECHNICAL FIELD 
     This disclosure relates to oblivious random access memory with logarithmic overhead. 
     BACKGROUND 
     Enterprises and individuals are using distributed storage systems (i.e., cloud storage services) to store data on memory overlying multiple memory locations. Many of these enterprises and individuals encrypt their data before uploading onto the distributed storage system. In order to use essential functionalities offered by the cloud storage services, such as performing search queries on stored data, enterprises are required to provide plaintext access to the cloud storage services. As a result, many government and sensitive private sectors, such as health, finance, and legal, or reluctant to use cloud storage services, despite their increased convenience and cost advantages. Additionally, encryption alone may not suffice for ensuring data privacy, as the mere knowledge of data access patterns can provide a significant amount of information about the data without ever needing to decrypt the data. 
     SUMMARY 
     One aspect of the disclosure provides a method for concealing access patterns. The method includes executing, by data processing hardware, an instruction to execute a query (q) for a data block (B), the data block (B) associated with a corresponding memory level (l i ) of a logarithmic number of memory levels (l i ) of memory. Each memory level (l i ) includes physical memory (RAM i ) residing on memory hardware of a distributed system in communication with the data processing hardware. The method also includes retrieving, by the data processing hardware, a value (v) associated with the data block (B) from an oblivious hash table using a corresponding key (k), and extracting, by the data processing hardware, un-queried key value pairs (k, v) from the oblivious hash table associated with un-queried data blocks after executing a threshold number of queries (q) for data blocks. The method also includes executing, by the data processing hardware, a multi-array shuffle routine on the extracted key value pairs from the oblivious hash table to generate an output array containing the un-queried key value pairs (k, v). 
     Implementations of the disclosure may include one or more of the following optional features. In some implementations, executing the multi-array shuffle routine includes merging one or more input arrays of data blocks (B) each having a capacity less than a threshold capacity into a new array, and shuffling the new array obliviously. In some examples, the logarithmic number of memory levels (l i ) include a logarithmic number of memory levels (l i ) of increasing size where each memory level (l i ) has a storage capacity equal to the joint capacity of all preceding smaller memory levels (l i ). The instruction to execute the query (q) for the data block (B) may include a read or write operation on the data block and an address indicating a memory location for the data block (B). Here, when the instruction to execute the query (q) includes the write operation on the data block (B), the instruction to execute the query (q) for the data block (B) further includes data. 
     In some examples, the method also includes, when the corresponding memory level (l i ) associated with the data block (B) is not a lowest memory level (l l ), moving the data block (B) to the lowest memory level (l l ) after executing the instruction to execute the query (q). In these examples, after moving the data block (B) to the lowest memory level (l l ), the method may also include, updating, by the data processing hardware, a memory-level map in communication with the data processing hardware to indicate that the corresponding memory level (l i ) associated with the data block (B) now includes the lowest memory level (l l ). 
     In some implementations, the data processing hardware resides on a client device. In these implementations, the client device may store a memory-level map in memory hardware of the client device. The memory-level map maps each data block stored on the memory hardware of the distributed system to a corresponding query memory level (l q ). 
     In some examples, the method also includes executing, by the data processing hardware, an instruction to execute a new query (q) for another data block (B), and determining, by the data processing hardware, whether the other data block (B) is stored locally on memory hardware of a client device. In these examples, when the other data block (B) is stored locally on the memory hardware of a client device, the method also includes retrieving, by the data processing hardware, the other data block (B) from the memory hardware of the client device. Additionally, when the other data block (B) is stored locally on the memory hardware of the client device, the method may also include, issuing, by the data processing hardware, one or more fake queries to the distributed system for retrieving a corresponding dummy block (D) to conceal the retrieval of the other data block (B) from the memory hardware of the client device. 
     Another aspect of the disclosure provides a system for concealing access patterns. The system includes data processing hardware, and memory hardware in communication with the data processing hardware and storing instructions, that when executed by the data processing hardware, cause the data processing hardware to perform operations. These operations include executing an instruction to execute a query (q) for a data block (B), the data block (B) associated with a corresponding memory level (l i ) of a logarithmic number of memory levels (l i ) of memory. Each memory level (l i ) includes physical memory (RAM i ) residing on a storage abstraction of a distributed system in communication with the data processing hardware. The operations also includes retrieving a value (v) associated with the data block (B) from an oblivious hash table using a corresponding key (k), and extracting un-queried key value pairs (k, v) from the oblivious hash table associated with un-queried data blocks after executing a threshold number of queries (q) for data blocks. The operations also include executing a multi-array shuffle routine on the extracted key value pairs from the oblivious hash table to generate an output array containing the un-queried key value pairs (k, v). 
     This aspect may include one or more of the following optional features. In some implementations, executing the multi-array shuffle routine includes merging one or more input arrays of data blocks (B) each having a capacity less than a threshold capacity into a new array, and shuffling the new array obliviously. In some examples, the logarithmic number of memory levels (l i ) include a logarithmic number of memory levels (l i ) of increasing size where each memory level (l i ) has a storage capacity equal to the joint capacity of all preceding smaller memory levels (l i ). The instruction to execute the query (q) for the data block (B) may include a read or write operation on the data block and an address indicating a memory location for the data block (B). Here, when the instruction to execute the query (q) includes the write operation on the data block (B), the instruction to execute the query (q) for the data block (B) further includes data. 
     In some implementations, the operations also include, when the corresponding memory level (l i ) associated with the data block (B) is not a lowest memory level (l l ), moving the data block (B) to the lowest memory level (l l ) after executing the instruction to execute the query (q). In these implementations, after moving the data block (B) to the lowest memory level (l l ), the operations may also include, updating a memory-level map in communication with the data processing hardware to indicate that the corresponding memory level (l i ) associated with the data block (B) now includes the lowest memory level (l l ). 
     The data processing hardware and the memory hardware may reside on a client device. In some examples, the client device stores a memory-level map in the memory hardware of the client device. The memory-level map maps each data block stored on the memory hardware of the distributed system to a corresponding query memory level (l q ). 
     In some examples, the operations also include executing an instruction to execute a new query (q) for another data block (B) and determining whether the other data block (B) is stored locally on memory hardware of a client device. In these examples, when the other data block (B) is stored locally on the memory hardware of a client device, the operations also includes retrieving the other data block (B) from the memory hardware. Additionally, when the other data block (B) is stored locally on the memory hardware of the client device, the operations may also include, issuing one or more fake queries to the distributed system for retrieving a corresponding dummy block (D) to conceal the retrieval of the other data block (B) from the memory hardware. 
     The details of one or more implementations of the disclosure are set forth in the accompanying drawings and the description below. Other aspects, features, and advantages will be apparent from the description and drawings, and from the claims. 
    
    
     
       DESCRIPTION OF DRAWINGS 
         FIGS.  1 A and  1 B  are schematic views of an example system using oblivious hash functions and an oblivious multi-array shuffle for storing and moving data blocks obliviously on non-transitory data storage of a distributed system. 
         FIG.  2    provides a schematic view of an example logarithmic number of memory levels of non-transitory memory. 
         FIG.  3    provides a schematic view of an example memory-level map. 
         FIG.  4    provides an example algorithm for executing an initialization phase and an access phase of an O-RAM routine. 
         FIGS.  5 A and  5 B  provide example algorithms for executing an oblivious multi-array shuffle routine. 
         FIG.  6 A  provides an example algorithm for constructing an oblivious bin tree. 
         FIG.  6 B  provides an example algorithm for constructing an oblivious cuckoo hash bin. 
         FIGS.  6 C and  6 D  provide an example algorithm for constructing an oblivious hash table. 
         FIG.  7    is a schematic view of an example computing device. 
         FIG.  8    is a flowchart of an example method for concealing access patterns of data blocks retrieved by a client. 
     
    
    
     Like reference symbols in the various drawings indicate like elements. 
     DETAILED DESCRIPTION 
       FIGS.  1 A and  1 B  depict an example system  100  for storing N data blocks (B) owned by a client  104  on a distributed system  140  and obliviously moving the data blocks (B) around the distributed system  140  to conceal access patterns while preserving search functionalities on the data blocks by the client  104 . A client device  120  (e.g., a computer) associated with the client  104  communicates, via a network  130 , with the distributed system  140  having a scalable/elastic non-transitory storage abstraction  200 . The client device  120  may include associated memory hardware  122  and associated data processing hardware  124 . The storage abstraction  200  (e.g., key/value store, file system, data store, etc.) is overlain on storage resources  114  to allow scalable use of the storage resources  114  by one or more client devices  120 . 
     In some implementations, the distributed system  140  executes a computing device  112  that manages access to the storage abstraction  200 . For instance, the client device  120  may encrypt and store the data blocks (B) on the storage abstraction  200 , as well as retrieve and decrypt the data blocks (B) from the storage abstraction  200 . While the example shown depicts the system  100  having a trusted side associated with the client device  120  in communication, via the network  130 , with an untrusted side associated with the distributed system  140 , the system  100  may be alternatively implemented on a large intranet having a trusted computing device(s) (CPU) and untrusted data storage. 
     In some implementations, the distributed system  100  includes resources  110 ,  110   a - z . The resources  110  may include hardware resources  110  and software resources  110 . The hardware resources  110  may include computing devices  112  (also referred to as data processing devices and data processing hardware) or non-transitory memory  114  (also referred to as memory hardware and storage resources). The software resources  110  may include software applications, software services, application programming interfaces (APIs) or the like. The software resources  110  may reside in the hardware resources  110 . For example, the software resources  110  may be stored in the memory hardware  114  or the hardware resources  110  (e.g., the computing devices  112 ) may be executing the software resources  110 . 
     A software application (i.e., a software resource  110 ) may refer to computer software that causes a computing device to perform a task. In some examples, a software application may be referred to as an “application,” an “app,” or a “program.” Example applications include, but are not limited to, system diagnostic applications, system management applications, system maintenance applications, word processing applications, spreadsheet applications, messaging applications, media streaming applications, social networking applications, and gaming applications. 
     The memory hardware  114 ,  122  may be physical devices used to store programs (e.g., sequences of instructions) or data (e.g., program state information) on a temporary or permanent basis for use by a computing device  112  and/or a client device  120  (i.e., the data processing hardware  124  of the client device  120 ). The memory hardware  114 ,  122  may be volatile and/or non-volatile addressable semiconductor memory. Examples of non-volatile memory include, but are not limited to, flash memory and read-only memory (ROM)/programmable read-only memory (PROM)/erasable programmable read-only memory (EPROM)/electronically erasable programmable read-only memory (EEPROM) (e.g., typically used for firmware, such as boot programs). Examples of volatile memory include, but are not limited to, random access memory (RAM), oblivious random access memory (ORAM), dynamic random access memory (DRAM), static random access memory (SRAM), phase change memory (PCM) as well as disks or tapes. 
     The network  130  may include various types of networks, such as local area network (LAN), wide area network (WAN), and/or the Internet. Although the network  130  may represent a long range network (e.g., Internet or WAN), in some implementations, the network  130  includes a shorter range network, such as a local area network (LAN). In some implementations, the network  130  uses standard communications technologies and/or protocols. Thus, the network  130  can include links using technologies, such as Ethernet, Wireless Fidelity (WiFi) (e.g., 802.11), worldwide interoperability for microwave access (WiMAX), 3G, Long Term Evolution (LTE), digital subscriber line (DSL), asynchronous transfer mode (ATM), InfiniBand, PCI Express Advanced Switching, Bluetooth, Bluetooth Low Energy (BLE), etc. Similarly, the networking protocols used on the network  130  can include multiprotocol label switching (MPLS), the transmission control protocol/Internet protocol (TCP/IP), the User Datagram Protocol (UDP), the hypertext transport protocol (HTTP), the simple mail transfer protocol (SMTP), the file transfer protocol (FTP), etc. The data exchanged over the network  130  can be represented using technologies and/or formats including the hypertext markup language (HTML), the extensible markup language (XML), etc. In addition, all or some of the links can be encrypted using conventional encryption technologies, such as secure sockets layer (SSL), transport layer security (TLS), virtual private networks (VPNs), Internet Protocol security (IPsec), etc. In other examples, the network  130  uses custom and/or dedicated data communications technologies instead of, or in addition to, the ones described above. 
     The data blocks (B) correspond to atomic units of data and each have size B bytes each. For example, a typical value for B for storage on a distributed system may be 64 KB to 256 B. A notation N denotes a total number of the data blocks (B) associated with the client  104  and stored on the storage abstraction  200  using Oblivious Random Access Memory (O-RAM). Each of the N data blocks is stored at a corresponding memory location  118 ,  118 A-N ( FIG.  1 B ) of the storage abstraction  200  overlain across the memory hardware  114 . 
     In some implementations, the client device  120  and the distributed system  140  execute an O-RAM routine  400  for obliviously storing and moving encrypted data blocks (B) across the memory locations  118  of the storage abstraction  200  to completely hide data access patterns (which data blocks (B) were read/written) from the distributed system  140 . During an initialization phase, the O-RAM routine  400  may cause the distributed system  140  to allocate new memory locations  118  of the storage abstraction  200  for storing encrypted data blocks (B) and organize/divide/partition the storage abstraction  200  into multiple arrays L (A 1 , A 2 , . . . , A L ) each having sizes N 1 , N 2 , . . . , N L , wherein N i ≥N i+1  for i=1, . . . , L−1. Each array L is randomly permuted by a permutation not known by the distributed system  140  storing the arrays L. During an access phase, the O-RAM routine  400  allows the client device  120  to access (read/write) and encrypted data block (B) stored on the storage abstraction  200  by executing an instruction  450  on the data processing hardware  124  of the client device  120  to execute a query (q) for the data block (B). The instruction  450  may indicate an operation (read or write), an address of the memory location  118  storing the data block (B), and the data block (B) when the operation is a write operation. By executing the instruction  450 , the client device  120  is able to retrieve the data block (B) without revealing the contents of the data block (B) as well as the sequence of the query (q) executed by the client device  120  to the distributed system  140 . Further, execution of the instruction  450  completely hides data access patterns (which data blocks (B) were read/written) from the distributed system  140 . 
     Referring to  FIG.  1 B , in some implementations, the distributed storage system  140  includes loosely coupled memory hosts  110 ,  110   a - z  (e.g., computers or servers), each having a computing resource  112  (e.g., one or more processors or central processing units (CPUs)) in communication with storage resources  114 ,  114   a - z  (e.g., memory hardware, memory hardware, flash memory, dynamic random access memory (DRAM), phase change memory (PCM), and/or disks) that may be used for caching data. The storage abstraction  200  overlain on the storage resources  114  allows scalable use of the storage resources  114  by one or more client devices  120 ,  120   a - n . The client devices  120  may communicate with the memory hosts  110  through the network  130  (e.g., via remote procedure calls (RPC)). 
     In some implementations, the distributed storage system  140  is “single-sided,” eliminating the need for any server jobs for responding to real and/or fake queries  402 ,  404  from client devices  120  to retrieve data blocks (B) and/or dummy blocks (D) from the storage abstraction  200  when the client devices  120  execute instructions  450  to execute queries (q) for data blocks (B). “Single-sided” refers to the method by which most of the request processing on the memory hosts  110  may be done in hardware rather than by software executed on CPUs  112  of the memory hosts  110 . Additional concepts and features related to a single-sided distributed caching system can be found in U.S. Pat. No. 9,164,702, which is hereby incorporated by reference in its entirety. 
     The distributed system  140  may obliviously move data blocks (B) around the storage resources  114  (e.g., memory hardware) of the remote memory hosts  110  (e.g., the storage abstraction  200 ) and get the data blocks (B) from the remote memory hosts  110  via RPCs or via remote direct memory access (RDMA)-capable network interface controllers (NIC)  116 . A network interface controller  116  (also known as a network interface card, network adapter, or LAN adapter) may be a computer hardware component that connects a computing device/resource  112  to the network  130 . Both the memory hosts  110   a - z  and the client device  120  may each have a network interface controller  116  for network communications. The O-RAM route  400  executing on the physical processor  112  of the hardware resource  110  registers a set of remote direct memory accessible regions/locations  118 A-N of the memory (storage resources)  114  with the network interface controller  116 . Each memory location  118  is configured to store a corresponding data block (B). 
     In some implementations, when the client device  120  executes the instruction  450  to execute the query (q) for a data block (B) and determines that the data block (B) is stored locally at the memory hardware  122  of the client device  120 , the client device  120  retrieves the data block (B) from the memory hardware  122  and sends one or more fake queries  404  to the NIC  116  for retrieving corresponding dummy blocks (D) to conceal the retrieval of the data block (B) from the local memory hardware  122 . The client device  120  may discard each retrieved dummy block (D). On the other hand, if the client device  120  determines that the data block (B) is stored on the storage abstraction  200 , the client device  120  may send a real query  402  to the NIC  116  for retrieving the corresponding data block (D) from the storage abstraction  200 . 
     Referring back to  FIG.  1 A , the client device  120  stores a memory-level map  300  locally in the memory hardware  122  that maps memory levels (l i ) of memory  118 ,  122 ,  200 . The memory levels (l i ) provide a hierarchical oblivious structure that includes a logarithmic number of memory levels (l i ) of increasing size where each memory level (l i ) has a storage capacity equal to the joint capacity of all preceding smaller memory levels (l i ). Each memory level (l i ) includes physical memory (RAM i )  210  residing on the storage abstraction  200  (e.g., memory hardware  114 ) of the distributed system  140 . 
       FIG.  2    provides a schematic view of example memory levels (l i ) that includes four logarithmic levels of memory  200 . The four levels may be extended to log N levels 
     
       
         
           
             
               { 
               
                 l 
                 i 
               
               } 
             
             ⁢ 
             
               
                 log 
                 ⁢ 
                 N 
               
               
                 i 
                 = 
                 α 
               
             
           
         
       
     
     of size 2 i  where 2 is equal to O(log N) for a RAM capacity of N data blocks (B) of size B. The first level (Level 1) (i=1) includes physical memory (RAM 1 )  210  storing all of the N data blocks (B) and resides on the storage abstraction  200  of the distributed system  140 . The RAM 1  includes a size of N 1  data blocks (B) and corresponds to a capacity equal to a joint capacity of each of the preceding smaller levels (Level 2, Level 3, and Level 4). In the example shown, the value for N 1  is equal to 16 data blocks (B), (B 1 -B N ) stored in RAM 1 . 
     The second level (Level 2) (i=2) includes physical memory (RAM 2 )  210  residing on the storage abstraction  200  of the distributed system  114 . The RAM 2  includes a size of N 2  data blocks (B) and corresponds to a capacity equal to a joint capacity of each of the preceding smaller levels (Level 3 and Level 4). Since N 1  corresponds to the joint capacity of all the preceding smaller levels, N 2  is equal to the value of N 1  divided by two (i.e., N 2 =N 1 /2) such that the size capacity of N 2  data blocks (B) stored in RAM 2  of Level 2 decreases by half from the size/capacity of N 1  data blocks (B) stored in RAM i  of Level 1. In the example shown, the value for N 2  is equal to 8 data blocks (B) stored in RAM 2 . 
     The third level (Level 3) (i=3) includes physical memory (RAM 3 )  210  residing on the storage abstraction  200  of the distributed system  114 . The RAM 3  includes a size of N 3  data blocks (B) and corresponds to a capacity equal to a capacity of the preceding smallest fourth level (Level 4). Since N 2  corresponds to the joint capacity of all the preceding smaller levels (Level 3 and Level 4), N 3  is equal to the value of N 2  divided by two (i.e., N 3 =N 2 /2) such that the size/capacity of N 3  data blocks (B) stored in RAM 3  of Level 3 decreases by half from the size/capacity of N 2  data blocks (B) stored in RAM 2  of Level 2. In the example shown, the value for N 3  is equal to 4 data blocks (B) stored in RAM 3 . 
     The fourth level (Level 4) (i=4) includes physical memory (RAM 4 )  210  that may reside on the storage abstraction  200  of the distributed system  114  or on the memory hardware  122  of the client device  120 . As the memory levels (l i ) include four levels, the fourth level (Level 4) corresponds to a lowest memory level (l l ). The fourth level (Level 4) may correspond to a receiving level that receives new data blocks (B) stored in the RAM 4  at the fourth level. The RAM 4  includes a size N 4  data blocks (B). Since N 3  has the capacity of the fourth level (Level 4), N 4  is equal to the value of N 3  such that the size/capacity of N 4  data blocks (B) stored in RAM 4  of Level 4 is equal to the size/capacity of N 3  data blocks (B) stored in RAM 3  of Level 3. In the example shown, the value for N 4  is equal to 4 data blocks (B) stored in RAM 4 . In some examples, a stash or shelter of virtual memory may reside on the memory hardware  122  at the client device  120  for storing the new data blocks (B) added to the RAM 4  at the fourth level. 
     In some examples, only data blocks (B) (e.g., items) assigned to the smallest/lowest memory level (l l ) in the hierarchy (e.g., Level 4 in the example of  FIG.  2   ) can be accessed more than once from the corresponding level. For each other level, once the user device  120  accesses a data block (B) from the corresponding level (i.e., by executing the instruction  450 ), the data block (B) moves to the smallest/lowest memory level (l l ) in the hierarchy. Once a memory level (l i ) reaches capacity (e.g., the level is full), the number of data blocks (B) assigned to that level move to an adjacent larger/higher memory level (l-1) in the hierarchy. Accordingly, adding new data blocks to the receiving level (l l ) can result in the level becoming full, thereby invoking a change of steps that moves data blocks (B) toward the larger memory levels (l i ) in the hierarchy of logarithmic levels of memory  200 . In a worst case scenario, the change of steps may result in moving data blocks (B) across all of the memory levels (l i ) in the hierarchy until reaching the largest memory level (e.g., Level 1 in the example of  FIG.  2   ). 
       FIG.  3    provides a schematic view of an example memory-level map  300  residing at the client device  120  for mapping the memory levels (l i ) of the memory  200 . In the example shown, the example memory-level map  300  maps the four memory levels (l i ) of  FIG.  2   . The memory-level map  300  maps each data block (B), (B 1 -B N ) to a corresponding query memory level (l q ) associated with a lowest one of the memory levels (l i ) at which the corresponding data block (B) of the executed query (q) is stored. For instance, data blocks (B 1 , B N ) each include a corresponding query memory level (l q ) equal to Level 1 indicating that the data blocks (B 1 , B N ) are stored in RAM 1 . Thus, if the client device  120  executes a query (q) for either of the data blocks (B 1 , B N ), the client device  120  will send a real query  402  to RAM residing at the storage abstraction  200  to retrieve the requested data blocks (B 1 , B N ). 
     Data block (B 2 ) includes a corresponding query memory level (l q ) equal to Level 4 indicating that the data block (B 2 ) is stored in in the lowest memory level (l i ) corresponding to RAM 4 . Thus, if the client device  120  executes a query (q) for the data block (B 2 ), the client device  120  will send a real query  402  to RAM 4  residing at the storage abstraction  200  to retrieve the requested data blocks (B 3 ). 
     Data block (B 3 ) includes a corresponding query memory level (l q ) equal to Level 3 indicating that the data block (B 3 ) is stored in RAM 3 . Thus, if the client device  120  executes a query (q) for the data block (B 3 ), the client device  120  will send a real query  402  to RAM 3  residing at the storage abstraction  200  to retrieve the requested data blocks (B 3 ). 
     Data block (B 4 ) includes a corresponding query memory level (l q ) equal to Level 2 indicating that the data block (B 4 ) is stored in RAM 2 . Thus, if the client device  120  executes a query (q) for the data block (B 4 ), the client device  120  will send a real query  402  to RAM 4  residing at the storage abstraction  200  to retrieve the requested data blocks (B 4 ). 
     In some implementations, when query memory level (l q ) is not the lowest memory level (l i ) (i.e., l q  ii) (e.g., Level 4), the client device  120  updates the memory-level map  300  to indicate that the retrieved data block (B) is now stored in RAM 4  of the lowest memory level (l i ). In the example shown, when the client device  120  retrieves a data block (B) from the storage abstraction  200  (e.g., RAM 1 , RAM 2 , or RAM 3 ) having a corresponding query memory level (l q ) less than the lowest memory level (l l ), the retrieved data block (B) moves to the lowest memory level (l l ) (Level 4) corresponding to RAM 4  and the client device  120  updates the memory-level map  300  to indicate that the retrieved data block (B) now includes a corresponding query memory level (l q ) equal to Level 4, i.e., the lowest memory level (h). 
       FIG.  4    provides an example algorithm associated with execution of the O-RAM routine  400 . As set forth above, the O-RAM routine  400  includes an initialization phase (ORAM.Init) and an access phase (ORAM.Acess). The O-RAM routine  400  may use an oblivious hash table  600  ( FIGS.  1 ,  6 C, and  6 D ) for obliviously moving and storing the N data blocks (B) across the hierarchy of logarithmic memory levels (l i ) of the storage abstraction  200 . For example, the O-RAM routine  400  may initialize (OblivHT.Init) and build (OblivHT.Build) the oblivious hash table  600  containing the whole database D (i.e., memory levels (l i )) of N data blocks (B) during the initialization phase (ORAM.Init). During the access phase, the O-RAM routine  400  may execute a lookup (OblivHT.Lookup) in the hash table  600  by using a key k to retrieve a corresponding value v associated with a queried data block (B). The key k may be set to the address specified in the query instruction  400  for the queried data block (B). (e.g., key) associated with an address (addr) specified in a corresponding query instruction  400  for a data block (B) associated. The O-RAM routine  400  may further invoke an oblivious shuffle (ORAM.Shuffle) that executes an extraction phase (OblivHT.Extract) of the oblivious hash table  600 , an oblivious multi-array shuffle routine (OblivMultArrShuff)  500  ( FIGS.  1 A,  5 A and  5 B ), and a subsequent build phase (OblivHT.Build) in order to construct an updated oblivious hash table  600 . The extraction phase (OblivHT.Extract) of the oblivious hash table  600  extracts data blocks (B) from each level in the oblivious hash table  600  after execution of a number of queries (i.e., instructions  400 ) to output a database containing only un-queried items (k i , v i ) and padded to size N. 
     Referring back to  FIG.  1 A , in some implementations, the client device  120  and the distributed system  140  execute the oblivious multi-array shuffle routine (OblivMultArrShuff)  500  (also referred to as “shuffle routine  500 ”) configured to leverage entropy of the multiple input arrays L (A 1 , A 2 , . . . , A L ) for the N data blocks (B) stored on the storage abstraction  200 . In some examples, the shuffle routine  500  assumes that each input array L has been previously shuffled in an order unknown by the untrusted server during the initialization phase of the O-RAM routine  400 . This assumption provides gains in efficiency. Moreover, the shuffle algorithm attains improved efficiency over general oblivious sorting algorithms under a restriction that there exists L′=O(log log λ) such that 
     
       
         
           
             
               
                 
                   ❘ 
                   &#34;\[LeftBracketingBar]&#34; 
                 
                 
                   A 
                   
                     L 
                     ′ 
                   
                 
                 
                   ❘ 
                   &#34;\[RightBracketingBar]&#34; 
                 
               
               + 
               … 
               + 
               
                 
                   ❘ 
                   &#34;\[LeftBracketingBar]&#34; 
                 
                 
                   A 
                   L 
                 
                 
                   ❘ 
                   &#34;\[RightBracketingBar]&#34; 
                 
               
             
             = 
             
               
                 O 
                 ⁡ 
                 ( 
                 
                   
                     
                       N 
                       ⁢ 
                       log 
                       ⁢ 
                       log 
                       ⁢ 
                       λ 
                     
                     ) 
                   
                   
                     log 
                     ⁢ 
                     N 
                   
                 
                 ) 
               
               . 
             
           
         
       
     
     The shuffle routine  500  may sample a random permutation from each input array L as well as a random Assign function that merges the elements (e.g., data blocks (B)) from separate arrays. Thereafter, the shuffle routine  500  may obliviously apply the sampled Assign function to the previously shuffled input arrays L (A 1 , A 2 , . . . , A L ). Accordingly, the shuffle routine  500  does not have the task of hiding the access pattern within each of the input arrays since the shuffle routine  500  assumes that they are already shuffled. In order to provide access pattern obliviousness for access patterns with non-repeating entries, the shuffle routine  500  may partition an output array configured to contain a number of data blocks (B) from each input array that is proportional to a fraction of a total number of data blocks (B) assigned to that input array. For instance, the shuffle routine  500  may retrieve an upper bound limit of data blocks (B) from each input array that are assigned to the output array partition and hide the exact number of data blocks (B) retrieved from each array. These accesses are obliviously since the shuffle routine  500  is not concerned with hiding access patterns within each array. In fact, by partitioning the output array, the shuffle routine  500  is generating a random permutation on the fly that permits retrieval of the first data blocks (B) in each of the input arrays. 
     After retrieving the data blocks (B) assigned to the output array, the shuffle routine  500  sorts the retrieved data blocks (B) obliviously in order to separate the exact number of data blocks (B) retrieved from each input array without revealing these numbers. The oblivious sorting of the retrieved data blocks (B) assigns the retrieved data blocks (B) to corresponding positions within the output array. Leftover data blocks (B) (e.g., remaining data blocks (B)) in each input array that were not retrieved for assignment to the output array remain in their corresponding input arrays and padded to hide their exact sizes. Thereafter, the shuffle routine  500  may recursively shuffle each of the input arrays containing the leftover data blocks (B). Here, the oblivious sorting is upon small arrays that are of size O(log 3  λ) while performing 
     
       
         
           
             O 
             ⁡ 
             ( 
             
               N 
               
                 
                   log 
                   3 
                 
                 ⁢ 
                 λ 
               
             
             ) 
           
         
       
     
     of these shuffles. Accordingly, the total shuffle cost remains O(N log log λ). 
     In some implementations, building the oblivious multi-array shuffle routine  500  includes a first step function (OblMultArrShuff) of merging all input arrays L (A 1 , A 2 , . . . , A L ) that include a size below a size threshold and shuffle them obliviously into a new input array, while simultaneously updating the Assign function mapping which was sampled at random. After the input arrays are shuffled, a second step function (OblMultArrShuff.Shuffle) of the shuffle routine  500  includes slicing the input arrays and the output array in order to initialize each of the partitions of the output arrays using the corresponding data blocks (B) retrieved from the input arrays. Here, the assignment of the data blocks (B) retrieved from each of the input arrays to corresponding partitions in the output array is executed using a wrapping function (OblMultArrShuff.BinShuffle) that wraps the functionality of obliviously shuffling the data blocks (B) retrieved from the input arrays into the output array. The wrapping function (OblMultArrShuff.BinShuffle) is further configured to return leftover input arrays that include leftover/unassigned data blocks (B) from the input arrays that will be subsequently shuffled using the second step (OblMultArrShuff.Shuffle) of the shuffle routine  500 .  FIGS.  5 A and  5 B  provide an example oblivious multi-array shuffle routine  500  executing the first and second step functions OblMultArrShuff, OblMultArrShuff.Shuffle ( FIG.  5 A ) and the wrapping function OblMultArrShuff.BinShuffle ( FIG.  5 B ). 
     In some implementations, the O-RAM routine  400  initializes oblivious hash tables  600  in order to achieve hierarchical structure of logarithmic memory levels (l i ) of increasing size (e.g., shown in  FIG.  2   ) when shuffling/moving the data blocks (B) between different memory levels (l i ). The oblivious hash tables  600  allow one time access to the items (e.g., data blocks (B)) associated therewith for use in storing the items at each memory level (l i ) of the hierarchical structure. Here, the O-RAM routine  400  leverages entropy associated data blocks (B) in each of the memory levels (l i ) that were not queried in order to more efficiently merge and shuffle the un-queried data blocks (B) in two memory levels (l i ). Specifically, an extract algorithm associated with the oblivious hash tables  600  separates the un-queried and queried items in each table, and thereafter, the multi-array shuffle routine  500  shuffles the arrays that include the un-queried items in each level for initializing a new joint has table. As the un-queried items (e.g., data blocks (B)) are already shuffled during a previous initialization of the oblivious hash table in their corresponding memory level (l i ) and the oblivious hash table query algorithm reveals information access pattern information about the items that were queried. 
     An oblivious hash table (OblivHT) may be defined by an initialization phase (OblivHT.Init), a build phase (OblivHT.Build), a lookup phase (OblivHT.Lookup), and an extraction phase (OblivHT.Extract) as follows:
         ({tilde over (D)}, st)←OblivHT.Init(D): an algorithm that takes as input an array of key-value pairs D={(k i , v i )} i=1   N  and outputs a processed version of it {tilde over (D)}.   ({tilde over (H)}, st′)←OblivHT.Build(D, st): an algorithm that takes as input a processed database D and a state and initializes the hash table {tilde over (H)} and updates the state st.   (v,  , st′)←OblivHT.Lookup(k, {tilde over (H)}, st): an algorithm that takes as input the oblivious has table and the state produced in the build phase and a lookup key and outputs the value v, corresponding to the key k together with updated hash table {tilde over (H)}′ and state st′.   ({tilde over (D)}, st′)←OblivHT.Extract({tilde over (H)}, {tilde over (S)}, st): an algorithm that takes the hash table and the state after the execution of a number of queries and outputs a database, which contains only the un-queried items (k i , v i )∈D and is padded to size N.       

     In some implementations, the O-RAM routine  400  modifies the oblivious hash table  600  with oblivious bins for data (B) of a smaller size. Similar to the oblivious hash table (OblivHT), an oblivious bin (OblivBin) may be defined by an initialization phase (OblivBin.Init), a build phase (OblivBin.Build), a lookup phase (OblivBin.Lookup), and an extraction phase (OblivBin.Extract) as follows:
         ({tilde over (D)}, st)←OblivBin.Init(D): an algorithm that takes as input an array of key-value pairs D={(k i , v i )} i=1   N  and outputs a processed version of it {tilde over (D)}.   ({tilde over (S)}, {tilde over (H)}, st′)←OblivBin.Build({tilde over (D)}, st): an algorithm that takes as input a processed database {tilde over (D)} and a state, initializes the hash table {tilde over (H)} and an additional array {tilde over (S)}, and updates the state st.   (v, {tilde over (S)}′,  , st′)←OblivBin.Lookup(k, {tilde over (H)}, {tilde over (S)}, st): an algorithm that takes as input the oblivious has table and the state produced in the build phase and a lookup key and outputs the value v i  corresponding to the key k i  together with updated hash table {tilde over (H)}′ and state st′.   ({tilde over (D)}, st′)←OblivHT.Extract({tilde over (H)}, st): an algorithm that takes the hash table and the state after the execution of a number of queries and outputs a database, which contains only the un-queried items (k i , v i )∈D and is padded to size N.       

     Different schemes may be utilized for instantiating oblivious bins for use in building the oblivious hash table  600 . In some examples, for oblivious hash tables  600  associated with logarithmic complexity during look up, an oblivious bin tree may provide a structure for sets of small sizes.  FIG.  6 A  provides an example algorithm  600   a  for constructing an oblivious bin tree.  FIG.  6 B  provides an example algorithm  600   b  for constructing an oblivious cuckoo hash bin. Thereafter, the oblivious hash table  600  having O(N log log λ) lookup complexity may be constructed using either of the oblivious bin constructions of  FIG.  6 A or  6 B . 
     In some implementations, the oblivious hash table  600  uses additional dummy items for providing oblivious properties of the hash table  600  without allowing an adversary to select the dummy items in challenge query sequences. Moreover, construction of the oblivious hash table  600  may assume that the input for the build phase (OblivHT.Build) includes both real and dummy items shuffled together at random. Here, the output of the extract phase (OblivHT.Extract) will also include un-queries real items mixed with a number of dummy items.  FIGS.  6 C and  6 D  provide an example algorithm  600   c  for constructing the oblivious hash table  600 . 
     A software application (i.e., a software resource) may refer to computer software that causes a computing device to perform a task. In some examples, a software application may be referred to as an “application,” an “app,” or a “program.” Example applications include, but are not limited to, system diagnostic applications, system management applications, system maintenance applications, word processing applications, spreadsheet applications, messaging applications, media streaming applications, social networking applications, and gaming applications. 
     The non-transitory memory may be physical devices used to store programs (e.g., sequences of instructions) or data (e.g., program state information) on a temporary or permanent basis for use by a computing device. The non-transitory memory may be volatile and/or non-volatile addressable semiconductor memory. Examples of non-volatile memory include, but are not limited to, flash memory and read-only memory (ROM)/programmable read-only memory (PROM)/erasable programmable read-only memory (EPROM)/electronically erasable programmable read-only memory (EEPROM) (e.g., typically used for firmware, such as boot programs). Examples of volatile memory include, but are not limited to, random access memory (RAM i ), dynamic random access memory (DRAM), static random access memory (SRAM), phase change memory (PCM) as well as disks or tapes. 
       FIG.  7    is schematic view of an example computing device  700  that may be used to implement the systems and methods described in this document. The computing device  700  is intended to represent various forms of digital computers, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, and other appropriate computers. The components shown here, their connections and relationships, and their functions, are meant to be exemplary only, and are not meant to limit implementations described and/or claimed in this document. 
     The computing device  700  includes a processor  710 , memory  720 , a storage device  730 , a high-speed interface/controller  740  connecting to the memory  720  and high-speed expansion ports  750 , and a low speed interface/controller  760  connecting to a low speed bus  770  and a storage device  730 . Each of the components  710 ,  720 ,  730 ,  740 ,  750 , and  760 , are interconnected using various busses, and may be mounted on a common motherboard or in other manners as appropriate. The processor  710  can process instructions for execution within the computing device  700 , including instructions stored in the memory  720  or on the storage device  730  to display graphical information for a graphical user interface (GUI) on an external input/output device, such as display  780  coupled to high speed interface  740 . In other implementations, multiple processors and/or multiple buses may be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices  700  may be connected, with each device providing portions of the necessary operations (e.g., as a server bank, a group of blade servers, or a multi-processor system). 
     The memory  720  stores information non-transitorily within the computing device  700 . The memory  720  may be a computer-readable medium, a volatile memory unit(s), or non-volatile memory unit(s). The non-transitory memory  720  may be physical devices used to store programs (e.g., sequences of instructions) or data (e.g., program state information) on a temporary or permanent basis for use by the computing device  700 . Examples of non-volatile memory include, but are not limited to, flash memory and read-only memory (ROM)/programmable read-only memory (PROM)/erasable programmable read-only memory (EPROM)/electronically erasable programmable read-only memory (EEPROM) (e.g., typically used for firmware, such as boot programs). Examples of volatile memory include, but are not limited to, random access memory (RAM), dynamic random access memory (DRAM), static random access memory (SRAM), phase change memory (PCM) as well as disks or tapes. 
     The storage device  730  is capable of providing mass storage for the computing device  700 . In some implementations, the storage device  730  is a computer-readable medium. In various different implementations, the storage device  730  may be a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations. In additional implementations, a computer program product is tangibly embodied in an information carrier. The computer program product contains instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory  720 , the storage device  730 , or memory on processor  710 . 
     The high speed controller  740  manages bandwidth-intensive operations for the computing device  700 , while the low speed controller  760  manages lower bandwidth-intensive operations. Such allocation of duties is exemplary only. In some implementations, the high-speed controller  740  is coupled to the memory  720 , the display  780  (e.g., through a graphics processor or accelerator), and to the high-speed expansion ports  750 , which may accept various expansion cards (not shown). In some implementations, the low-speed controller  760  is coupled to the storage device  730  and a low-speed expansion port  790 . The low-speed expansion port  790 , which may include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet), may be coupled to one or more input/output devices, such as a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, e.g., through a network adapter. 
     The computing device  700  may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a standard server  700   a  or multiple times in a group of such servers  700   a , as a laptop computer  700   b , or as part of a rack server system  700   c.    
       FIG.  8    is a flowchart of an example method  800  executed by the computing device  700  (e.g., data processing hardware  124 ) of  FIG.  7    for concealing access patterns to a storage abstraction  200  on a distributed system  140 . At operation  802 , the method  800  includes executing an instruction  450  to execute a query (q) for a data block (B). The data block (B) is associated with a corresponding memory level (l i ) of a logarithmic number of memory levels (l i ) of memory. Each memory level (l i ) includes physical memory (RAM i ) residing on memory hardware  114  (e.g., storage abstraction  200 ) of the distributed system  140  in communication with the data processing hardware  124 . At operation  804 , the method  800  includes retrieving a value (v) associated with the data block (B) from an oblivious hash table  600  using a corresponding key (k). At operation  806 , the method  800  includes extracting un-queried key value pairs (k, v) from the oblivious hash table  600  associated with un-queried data blocks (B) after executing a threshold number of queries (q) for data blocks (B). The method  800  also includes, at operation  808 , executing a multi-array shuffle routine  500  on the extracted key value pairs (k, v) from the oblivious hash table  600  to generate an output array containing the un-queried key value pairs (k, v). 
     Various implementations of the systems and techniques described herein can be realized in digital electronic and/or optical circuitry, integrated circuitry, specially designed ASICs (application specific integrated circuits), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include implementation in one or more computer programs that are executable and/or interpretable on a programmable system including at least one programmable processor, which may be special or general purpose, coupled to receive data and instructions from, and to transmit data and instructions to, a storage system, at least one input device, and at least one output device. 
     These computer programs (also known as programs, software, software applications or code) include machine instructions for a programmable processor, and can be implemented in a high-level procedural and/or object-oriented programming language, and/or in assembly/machine language. As used herein, the terms “machine-readable medium” and “computer-readable medium” refer to any computer program product, non-transitory computer readable medium, apparatus and/or device (e.g., magnetic discs, optical disks, memory, Programmable Logic Devices (PLDs)) used to provide machine instructions and/or data to a programmable processor, including a machine-readable medium that receives machine instructions as a machine-readable signal. The term “machine-readable signal” refers to any signal used to provide machine instructions and/or data to a programmable processor. 
     The processes and logic flows described in this specification can be performed by one or more programmable processors, also referred to as data processing hardware, executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry. 
     To provide for interaction with a user, one or more aspects of the disclosure can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube), LCD (liquid crystal display) monitor, or touch screen for displaying information to the user and optionally a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user&#39;s client device in response to requests received from the web browser. 
     A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the disclosure. Accordingly, other implementations are within the scope of the following claims.