Systems, methods, and apparatus to provide private information retrieval

Patent metadata

Field	Value
Publication number	US-2016283731-A1
Application number	US-201514665064-A
Country	US
Kind code	A1
Filing date	Mar 23, 2015
Priority date	Mar 23, 2015
Publication date	Sep 29, 2016
Grant date	—

Abstract

Systems, methods, and apparatus to provide private information retrieval. A disclosed example system includes a first trusted processing unit to store a first portion of data such that entities other than the first trusted processing unit are unable to access the first portion of the data in the first trusted processing unit; a second trusted processing unit to store a second portion of the data such that entities other than the second trusted processing unit are unable to access the second portion of the data in the second trusted processing unit; and a third trusted processing unit to: determine that a data element specified in a request is stored in the first trusted processing unit; request the data element from the first trusted processing unit; send a dummy request to the second trusted processing unit; and send the data element to a requester.

First claim

What is claimed is:

1 . A system, comprising:
a first trusted processing unit to store a first portion of data such that entities other than the first trusted processing unit are unable to access the first portion of the data in the first trusted processing unit; a second trusted processing unit to store a second portion of the data such that entities other than the second trusted processing unit are unable to access the second portion of the data in the second trusted processing unit; and a third trusted processing unit to:
determine that a data element specified in a request is stored in the first trusted processing unit;
request the data element from the first trusted processing unit;
send a dummy request to the second trusted processing unit; and
send the data element to a requester.

2 . A system as defined in claim 1 , wherein the second trusted processing unit is to send a dummy response to the third trusted processing unit in response to the dummy request.

3 . A system as defined in claim 2 , wherein the dummy request includes a first dummy indicator and the dummy response includes a second dummy indicator.

4 . A system as defined in claim 2 , wherein the dummy request specifies a second data element stored in the second trusted processing unit, and the third trusted processing unit is to discard the dummy response.

5 . A system as defined in claim 1 , wherein the third trusted processing unit is to request the data element from the first trusted processing unit such that only the first trusted processing unit and the third trusted processing unit can identify the data element that is requested from the first trusted processing unit.

6 . A system as defined in claim 1 , wherein the first trusted processing unit includes a data enclave generator to:
create a protected data enclave in a first portion of a first storage device, the first storage device being protected by the first trusted processing unit; and store the first portion of the data in the protected data enclave.

7 . A system as defined in claim 6 , wherein the data enclave generator is to identify data elements belonging to the first portion of the data to be stored in the protected data enclave by:
applying a function to the data elements; and comparing a) values that result from the applying of the function to b) a first value that corresponds to the first trusted processing unit and that is different than a second value that corresponds to the second trusted processing unit.

8 . A system as defined in claim 1 , wherein the third trusted processing unit includes a protected hashing enclave to sort data elements of the data into a first data bucket or a second data bucket, the first data bucket corresponding to the first trusted processing unit and the second data bucket corresponding to the second trusted processing unit.

9 . A system as defined in claim 8 , wherein the third trusted processing unit further includes a request processor to request the data element specified in the request from the first trusted processing unit based on the protected hashing enclave performing a hash function on the data element specified in the request and determining whether a result of the hash function corresponds to the first bucket or the second bucket.

10 . A system as defined in claim 1 , further including a fourth trusted processing unit to:
determine that the data element specified in the request is accessible via the third trusted processing unit and is not accessible via a fifth trusted processing unit; and request the data element from the third trusted processing unit such that only the fourth trusted processing unit and the third trusted processing unit can identify the data element that is requested from the third trusted processing unit, the fourth trusted processing unit being the requester to the third trusted processing unit.

11 . A method, comprising:
using trusted processing units, generating protected data enclaves to store a copy of data in a database, each of the protected data enclaves being accessible to only corresponding ones of the trusted processing units that generated the protected data enclaves; in response to receiving a first request for a record in the data at a first one of the trusted processing units, determining, using the trusted processing units, which one of the protected data enclaves contains the record; sending second requests between the trusted processing units to retrieve the record from the determined one of the protected data enclaves; sending dummy requests to the ones of the trusted processing units that correspond to ones of the protected data enclaves that do not contain the record; and sending the record to a requester.

12 . A method as defined in claim 11 , wherein the data is split between the protected data enclaves.

13 . A method as defined in claim 11 , wherein the database is stored on a computing device having a processor, and the generating of the protected data enclaves includes generating the protected data enclaves to prevent access by the processor to portions of memory in which the protected data enclaves are stored.

14 . A method as defined in claim 13 , wherein the determining of the one of the protected data enclaves that contains the record, the sending the one or more second requests, and sending the record to the requester are performed without the processor being able to determine the record that was requested and without the processor being able to determine the protected data enclave in which the record is stored.

15 . A method as defined in claim 11 , further including determining a size of the database and determining a number of the protected data enclaves to store the copy of the data based on a threshold amount of data that can be protected by one of the trusted processing units.

16 . A method as defined in claim 11 , wherein generating a first one of the data enclaves includes:
encrypting a portion of the data using a second one of the trusted processing units; and storing the encrypted data in a first memory, the portion of the data in the first memory being accessible only to the second one of the trusted processing units.

17 . A method as defined in claim 11 , wherein the plurality of the protected data enclaves include an entirety of the database.

18 . A method as defined in claim 11 , further including generating a protected hashing enclave at a second one of the trusted processing units, the protected hashing enclave indicating assignments of the data to ones of the protected data enclaves.

19 . A method as defined in claim 18 , wherein determining which one of the protected data enclaves contains the record includes:
performing a hash function on the first request to generate a hash value; and looking up the hash value in the protected hashing enclave to determine the one of the protected data enclaves contains the record.

20 . A method as defined in claim 18 , wherein determining which one of the protected data enclaves contains the record includes:
performing a hash function on the first request to generate a hash value; and looking up the hash value in the protected hashing enclave to determine which of two trusted processing units is in a path to the one of the protected data enclaves that contains the record.

21 . A method as defined in claim 18 , further including configuring the trusted processing units in a tree structure in which ones of the trusted processing units that corres

Assignees

• Intel Corp

Inventors

• Chow Richard
• Wang Edward
• Phegade Vinay

Classifications

• G06F16/278

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• G06F16/9014

  hash tables · CPC title

• G06F21/6218 Primary

  to a system of files or objects, e.g. local or distributed file system or database · CPC title

• G06F2221/2123

  Dummy operation · CPC title

• G06F16/9027 Primary

  Trees · CPC title