System and method for private information retrieval from a single electronic storage device using commodities

• US 6,216,128 B1
• Filed: 03/02/1999
• Issued: 04/10/2001
• Est. Priority Date: 10/09/1997
• Status: Expired due to Term

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Ostrovsky, Rafail, Ishai, Yuval, Di-Crescenzo, Giovanni
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/260,110
• Time in Patent Office: 770 Days
• Field of Search: 707/3, 707/9, 707/10, 709/203, 709/229, 709/219
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A method and system for privately retrieving selected information from a database. The method includes determining, at a server, a first commodity and a second commodity, communicating the first commodity to an inquiring processor and the second commodity to the database, and retrieving the selected information from the database based on the first commodity and the second commodity such that the selected information is not revealed to the database. The first and second commodities may, for example, include a random address in the database and a private information retrieval query for encoding the random address, respectively. The inquiring processor determines an address offset based on the random address and the address of selected information in the database, and sends the address offset to the database. The database cyclically shift its contents according the address offset, and executes the query on the cyclically shifted contents. The database then sends the result of the query to the inquiring processor, which extracts from the result the selected information in the database.

Claims

1. A method for privately retrieving selected information from a database in a communications network including a server, an inquiring processor distinct from said server and said database, and the database without requiring replication of the database, said method comprising the steps of:

determining, at the server, a first and a second commodity, wherein said determining step comprises the steps of;

identifying a random address in the database;

determining a query for encoding the random address such that the random address is not revealed to the database;

including the random address in the first commodity; and

including the query in the second commodity;

communicating the first commodity and the second commodity to the inquiring processor and the database, respectively; and

retrieving the selected information from the database based on the first commodity and the second commodity such that the selected information is not revealed to the database.

2. The method of claim 1 wherein the first commodity further includes trapdoor information for decoding the result at the inquiring processor.

3. A method for privately retrieving selected information from a database, said method comprising the steps of:

determining, at a server, a first commodity and a second commodity, said determining step comprising the steps of;

identifying a first address in the database; and

determining a query for encoding the first address;

communicating the first commodity and the second commodity to an inquiring processor and the database, respectively; and

retrieving the selected information from the database based on the first commodity and the second commodity such that the selection information is not revealed to the database, wherein said retrieving step comprises the steps of;

identifying, at the inquiring processor, a second address in the database that includes the selected information;

determining a difference between the second address and the first address, and communicating the determined difference to the database;

cyclically shifting contents of the database according to the determined difference; and

executing the query at the database, and transmitting a result of the query to the inquiring processor.

4. The method of claim 3 further comprising the step of:

decoding the result at the inquiring processor.

5. A method for privately retrieving selected information from a database in a communications network including a plurality of servers, an inquiring processor distinct from said plurality of servers and said database, and the database without requiring replication of the database, said method comprising the steps of:

determining, at a first server, a first commodity and a second commodity, wherein said determining step at the first server comprises the steps of;

identifying a first random address in the database;

determining a first query for encoding the first random address such that the first random address is not revealed to the database;

including the first random address in the first commodity; and

including the first query in the second commodity;

determining, at a second server, a third commodity and a fourth commodity;

communicating the first commodity and the third commodity to the inquiring processor;

communicating the second commodity and the fourth commodity to the database;

combining the second commodity and the fourth commodity at the database; and

retrieving the selected information from the database based on the first commodity, the third commodity, and the combined second and fourth commodities such that the selected information is not revealed to the database.

6. The method of claim 5, wherein said determining step at the second server comprises the steps of:

identifying a second random address in the database;

determining a second query for encoding the second random address such that the second random address is not revealed to the database;

including the second random address in the third commodity; and

including the second query in the fourth commodity.

7. The method of claim 6 wherein said combining step comprises the step of:

executing the first query at the database N times by cyclically shifting in increments contents of the database prior to each execution.

8. A method for privately retrieving selected information from a database, said method comprising the steps of:

determining, at a first server, a first commodity and a second commodity, said determining step at the first server comprises the steps of;

identifying a first address in the database; and

determining a first query for encoding the first address;

determining, at a second server, a third commodity and a fourth commodity, said determining step at the second server comprises the steps of;

identifying a second address in the database; and

determining a second query for encoding the second address;

communicating the first commodity and the third commodity to an inquiring processor;

communicating the second commodity and the fourth commodity to the database;

combining the second commodity and the fourth commodity at the database, said combining step comprises the step of;

executing the first query at the first database N times by cyclically shifting in increments contents of the database prior to each execution; and

retrieving the selected information from the database based on the first commodity, the third commodity, and the combined second and fourth commodities such that the selected information is not revealed to the database, and wherein the retrieving step comprises the steps of;

identifying, at the inquiring processor, a third address in the database that includes the selected information;

determining a difference between the third address and the sum of the second address and the first address, and communicating the determined difference to the first database;

cyclically shifting results of the N executions according to the determined difference; and

executing the second query based on the cyclically shifted results, and transmitting a result of the query to the inquiring processor.

9. The method of claim 8 further comprising the step of:

decoding the result of the second query at the inquiring processor.

10. A method for privately retrieving selected information from a database, said method comprising the steps of:

determining, at an inquiring processor, a first commodity and a second commodity, said determining step comprises the steps of;

identifying a first address in the database; and

determining a query for encoding the first address;

communicating the second commodity to the database; and

retrieving the selected information from the database based on the first commodity and the second commodity such that the selected information is not revealed to the database, and wherein said retrieving step comprises the steps of;

identifying, at the inquiring processor, a second address in the database that includes the selected information;

determining a difference between the second address and the first address, and communicating the determined difference to the database;

cyclically shifting contents of the database according to the determined difference; and

executing the query at the database, and transmitting a result of the query to the inquiring processor.

11. The method of claim 10 further comprising the step of:

decoding the result at the inquiring processor.