Oblivious RAM with logarithmic overhead

1. A computer-implemented method when executed by data processing hardware of a client device causes the data processing hardware to perform operations comprising:

executing an instruction to execute a query (q) for a data block (B) residing on memory hardware of a distributed system in communication with the data processing hardware or on memory hardware of the client device;

determining whether the data block (B) is stored locally on the memory hardware of the client device; and

when the data block (B) is stored locally on the memory hardware of the client device:

retrieving the data block (B) from the memory hardware of the client device; and

issuing one or more fake queries to the distributed system for retrieving a corresponding dummy block (D) to conceal the retrieval of the data block (B) from the memory hardware of the client device.

2. The method of claim 1 , wherein the operations further comprise, after issuing the one or more fake queries to the distributed system:

receiving the corresponding dummy block (D) from the distributed system; and

discarding the corresponding dummy block (D).

3. The method of claim 1 , wherein the operations further comprise, when the data block (B) is stored on the memory hardware of the distributed system:

retrieving a value (v) associated with the data block (B) from an oblivious hash table using a corresponding key (k);

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; and

generating an output array that contains the un-queried key value pairs (k, v).

4. The method of claim 3 , wherein generating the output array comprises executing a multi-array shuffle routine on the extracted un-queried key value pairs (k, v) from the oblivious hash table.

5. The method of claim 4 , wherein executing the multi-array shuffle routine comprises:

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.

6. The method of claim 3 , wherein 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 ) comprising physical memory (RAM i ) residing on a storage abstraction of the distributed system.

7. The method of claim 6 , wherein the logarithmic number of memory levels (l i ) comprise 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 ).

8. The method of claim 7 , wherein the operations further comprise, 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).

9. The method of claim 1 , wherein the instruction to execute the query (q) for the data block (B) comprises an operation including a read or write operation on the data block and an address indicating a memory location for the data block (B).

10. The method of claim 9 , wherein the instruction to execute the query (q) for the data block (B) further comprises data when the operation includes the write operation.

11. A system comprising:

data processing hardware of a client device; 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 comprising:

executing an instruction to execute a query (q) for a data block (B) residing on memory hardware of a distributed system in communication with the data processing hardware or on the memory hardware of the client device;

determining whether the data block (B) is stored locally on the memory hardware of the client device; and

when the data block (B) is stored locally on the memory hardware of the client device:

retrieving the data block (B) from the memory hardware of the client device; and

issuing one or more fake queries to the distributed system for retrieving a corresponding dummy block (D) to conceal the retrieval of the data block (B) from the memory hardware of the client device.

12. The system of claim 11 , wherein the operations further comprise, after issuing the one or more fake queries to the distributed system:

receiving the dummy block (D) from the distributed system; and

discarding the received dummy block (D).

13. The system of claim 11 , wherein the operations further comprise, when the data block (B) is stored on the memory hardware of the distributed system:

retrieving a value (v) associated with the data block (B) from an oblivious hash table using a corresponding key (k);

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; and

generating an output array that contains the un-queried key value pairs (k, v).

14. The system of claim 13 , wherein generating the output array comprises executing a multi-array shuffle routine on the extracted un-queried key value pairs (k, v) from the oblivious hash table.

15. The system of claim 14 , wherein executing the multi-array shuffle routine comprises:

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.

16. The system of claim 13 , wherein 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 ) comprising physical memory (RAM i ) residing on a storage abstraction of the distributed system.

17. The system of claim 16 , wherein the logarithmic number of memory levels (l i ) comprise 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 ).

18. The system of claim 17 , wherein the operations further comprise, 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).

19. The system of claim 11 , wherein the instruction to execute the query (q) for the data block (B) comprises an operation including a read or write operation on the data block and an address indicating a memory location for the data block (B).

20. The system of claim 19 , wherein the instruction to execute the query (q) for the data block (B) further comprises data when the operation includes the write operation.