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

• US 6,438,554 B1
• Filed: 10/11/2000
• Issued: 08/20/2002
• 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, Di-Crescenzo, Giovanni, Ishai, Yuval
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/686,262
• Time in Patent Office: 678 Days
• Field of Search: 707/2, 707/3, 707/9, 707/10, 709/203, 709/219, 709/229, 713/182, 713/162
• 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 verifying validity of a commodity determined by a server for privately retrieving selected information from a first database, said method comprising the steps of:

identifying, at the server, an address in the first database, and determining a query for encoding the address;

communicating the address and the query to an inquiring processor and the first database, respectively;

executing, at the first database, the query using a second database whose contents are known to the inquiring processor, and transmitting result of the query to the inquiring processor; and

decoding, at the inquiring processor, a result of the query to verify the validity of the commodity based on the identified address.

2. A method for verifying validity of a commodity determined by a server for privately retrieving selected information from a first database, said method comprising the steps of:

identifying, at a server, a first address in the first database, and determining a query for encoding the first address;

communicating the first address and the query to an inquiring processor and the first database, respectively;

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

executing the query on a second database, and transmitting a first result of the query to the inquiring processor, wherein contents of the second database are known to the inquiring processor;

combining the first and second databases; and

executing the query based on the combined first and second databases, and transmitting a second result of the query to the inquiring processor.

3. The method of claim 2 further comprising the steps of:

decoding the first result and the second result at the inquiring processor; and

extracting the selected information from the first and second decoded results.