Oblivious RAM with logarithmic overhead
US11023168B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 26, 2019 |
| Grant date | Jun 1, 2021 |
| Priority date | — |
| Expiry date | Dec 4, 2039 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L67/10
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.