Oblivious RAM with Logarithmic Overhead
First Claim
1. A method comprising:
- 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 (li) of a logarithmic number of memory levels (li) of memory, each memory level (li) comprising physical memory (RAMi) residing on memory hardware of a distributed system in communication with the data processing hardware;
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);
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; and
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).
3 Assignments
0 Petitions
Accused Products
Abstract
A method includes executing an instruction to execute a query for a data block, the data block associated with a corresponding memory level of a logarithmic number of memory levels (li) of memory, each memory level (li) including physical memory (RAMi) residing on memory hardware of a distributed system. The method also includes retrieving a value associated with the data block from an oblivious hash table using a corresponding key, and extracting un-queried key value pairs from the oblivious hash table associated with un-queried data blocks after executing a threshold number of queries for data blocks. The method also includes 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.
4 Citations
22 Claims
-
1. A method comprising:
-
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 (li) of a logarithmic number of memory levels (li) of memory, each memory level (li) comprising physical memory (RAMi) residing on memory hardware of a distributed system in communication with the data processing hardware; 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); 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; and 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). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A system comprising:
-
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 comprising; executing an instruction to execute a query (q) for a data block (B), the data block (B) associated with a corresponding memory level (li) of a logarithmic number of memory levels (li) of memory, each memory level (li) comprising physical memory (RAMi) residing on a storage abstraction of a distributed system in communication with the data processing hardware; 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 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). - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
Specification