Method and apparatus for private information retrieval from a single electronic storage device

• US 6,167,392 A
• Filed: 06/01/1998
• Issued: 12/26/2000
• Est. Priority Date: 10/09/1997
• Status: Expired due to Term

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Technion R&D Foundation Ltd., Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Kushilevitz, Eyal, Ostrovsky, Rafail
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/087,893
• Time in Patent Office: 939 Days
• Field of Search: 707/9, 707/10, 707/3, 707/2, 707/101
• US Class Current: 1/1
• 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
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and apparatus for privately retrieving information from a single electronic storage device (e.g., a database) is described. An inquiring processor identifies a portion of a database memory with information for retrieval and encodes address of the information into a preselected mathematical function that conceals the identity of the selected information from the database. The inquiring processor transmits the encoded function to the database. The database cooperates by executing the encoded function on the database and transmits an encoded result that represents an evaluation of the encoded function to the inquiring processor. The inquiring processor, having knowledge of the selected mathematical function, decodes the encoded result to generate the information from the selected memory section of the database. The inquiry can be repeated until the inquiring processor can retrieve the selected information. The process minimizes the exchange of information between the database and the inquiring processor that is necessary to privately retrieve information.

Claims

1. A method of privately retrieving selected information from a database that contains the selected information, without requiring replication of said database, said method comprising the steps of:

a) selecting, at an inquiring processor from a set of known data addresses, the addresses of information to be retrieved from said database;

b) encoding, at said inquiring processor, said addresses into a mathematical function that does not reveal to said database the addresses of information to be retrieved;

c) communicating said mathematical function containing encoded addresses to said database;

d) executing said mathematical function against the entirety of said database, and transmitting the results of said execution to said inquiring processor; and

e) decoding said results at said inquiring processor, wherein the total amount of information exchanged between said database and said inquiring processor is less than the total amount of information stored in said database.

2. The method of claim 1, wherein said encoding step is based on a quadratic residuosity assumption.

3. The method of claim 1, wherein said encoding step is based on a homomorphic encryption function.

4. The method of claim 1, wherein said transmitting step further comprises the step of authenticating the results.

5. The method according to claim 1, and further comprising the step of repeating steps a)-e) until the decoding step reveals the desired information to said inquiring processor.

6. The method of claim 5, wherein said encoding step is based on a homomorphic encryption function.

7. The method of claim 5, wherein said encoding step is based on a quadratic residuosity assumption.

8. The method of claim 5, wherein said step of transmitting said encoded information further comprises the step of authenticating said encoded information.

9. The method of claim 1, wherein said communicating step further comprises the steps of:

a) forming an agreement between said inquiring processor and said database on a specification for retrieving data from said database;

b) providing, by said inquiring processor, a zero-knowledge proof to said database that the method of privately retrieving meets said agreed upon specification between said inquiring processor and said database.

10. A method of privately retrieving selected information from a database that contains the selected information, without requiring replication of said database, said method comprising the steps of:

a) identifying, at an inquiring processor, the addresses of information to be retrieved from said database;

b) encoding, at said inquiring processor, said addresses into a mathematical function that does not reveal to said database the addresses of information to be retrieved;

c) transmitting said mathematical function containing encoded addresses to said database;

d) executing the mathematical function against the entirety of said database, said execution step further comprising the steps of;

i) translating the data in said database into encoded information corresponding to said function, such that data in said identified addresses is decodable by said inquiring processor but not said database; and

ii) transmitting to said inquiring processor said encoded information; and

e) decoding said encoded information at said inquiring processor, wherein the total amount of information exchanged between said database and said inquiring processor is less than the total amount of information stored in said database.

11. The method of claim 10, wherein said step of transmitting said mathematical function containing encoded information further comprises the steps of:

a) forming an agreement between said inquiring processor and said database on a specification for retrieving data from said database;

b) providing, by said inquiring processor, a zero-knowledge proof to said database the method of privately retrieving meets said agreed upon specification between said inquiring processor and said database.

12. A method of privately retrieving selected information from a database that contains the selected information, without requiring replication of said database, said method comprising the steps of:

a) identifying, at an inquiring processor, the addresses of information to be retrieved from said database;

b) encoding, at said inquiring processor, said addresses into a mathematical function that does not reveal to said database the addresses of information to be retrieved;

c) transmitting said mathematical function containing encoded addresses to said database;

d) executing the mathematical function against the entirety of said database, said execution step further comprising the steps of;

(i) translating the data in said database into encoded information corresponding to said function, such that data in said identified addresses is decodable by said inquiring processor but not said database; and

(ii) transmitting to said inquiring processor said encoded information;

e) decoding said encoded information at said inquiring processor; and

f) repeating steps a) through e) until said inquiring processor can read the desired information wherein the total amount of information exchanged between said database and said inquiring processor is less than the total amount of information stored in said database.

13. The method of claim 12, wherein said encoding step is based on a homomorphic encryption function.

14. The method of claim 12, wherein said encoding step is based on a quadratic residuosity assumption.

15. The method of claim 12, wherein said step of transmitting said encoded information further comprises the step of authenticating said encoded information.

16. The method of claim 12, wherein said step of transmitting said mathematical function containing encoded information further comprises the steps of:

a) forming an agreement between said inquiring processor and said database on a specification for retrieving data from said database;

b) providing, by said inquiring processor, a zero-knowledge proof to said database that the method of privately retrieving meets said agreed upon specification between said inquiring processor and said database.

17. A method of querying a database from an inquiring database for an address of a selected key without revealing to said database which key is being searched, said method comprising the steps of:

a) selecting, at said database, a perfect hash function wherein said hash function provides a one-to-one correspondence between stored key values and hash values;

b) transmitting a description of said hash function to said inquiring processor;

c) reordering, at said database, database entries according to said hash function;

d) applying, at said inquiring processor, said hash function to the selected key; and

e) determining, at said inquiring processor, the address of the selected key in said reordered database.

18. A method of privately retrieving selected information from a database that contains the selected information, without requiring replication of said database, said method comprising the steps of:

a) identifying, at an inquiring processor, the addresses of information to be retrieved from said database;

b) encoding, at said inquiring processor, said addresses into a mathematical function that does not reveal the addresses of information to be retrieved to said database;

c) transmitting said mathematical function containing encoded addresses to said database;

d) executing the mathematical function against a subset of the entire database defined by said inquiring processor, said execution step further comprising the steps of;

(i) translating the data in said database into encoded information corresponding to said function, such that data in said identified addresses is decodable by said inquiring processor but not said database; and

(ii) transmitting to said inquiring processor said encoded information; and

e) decoding said encoded information at said inquiring processor.