Method for searching a database or data sharing system for the presence of data

• US 8,538,937 B2
• Filed: 04/22/2003
• Issued: 09/17/2013
• Est. Priority Date: 06/17/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Numao, Masayuki, Watanabe, Yuji
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Kim, Paul
• Application Number:
  US10/421,256
• Publication Number:
  US 20040034628A1
• Time in Patent Office: 3,801 Days
• Field of Search: 707/2, 707/3, 707/10, 707/698, 707/747, 707/605
• US Class Current: 707/698
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A database search system ensures the privacy of a search request and the security of a database with high processing efficiency. The system comprises a database server residing on a network that stores predetermined data, and a client terminal issuing to the database server a search request for inquiring for desired data while keeping the desired data secret. The database server further comprises: a database storing predetermined data; and a search response message generation unit for receiving through a network the data search request in which data to be searched for is kept secret, searching the database by a predetermined computation based on the search request and a list of the data stored in the database while a data item involved with the search request is kept secret, and generating a response to the search request.

Claims

1. A method for searching a database server having a list of data items stored therein, the method comprising:

receiving a search request message that includes an encryption of a desired data item from a client by the database server, wherein a first algorithm is utilized for the encryption, wherein the desired data item is kept secret from the database server;

generating a search response message by the database server, wherein the search response message is generated based on the search request message and based on the list of data items using a second algorithm that creates a polynomial with the encryption of the desired data item as a root of the polynomial; and

transmitting the search response message to the client, wherein whether the desired data item is stored in the database server is determined based on the search response message using a third algorithm, wherein the presence of any other data items of the list of data items is not revealed to the client.

3. The method of claim 1, wherein generating the search response message further comprises generating an n^th-order polynomial equation having the data items in the list of data items as its roots and evaluating the n^th-order polynomial equation using the desired data item.

4. The method of claim 1, further comprising calculating a pair of values using a public key.

5. The method of claim 1, wherein the desired data item is kept secret by encrypting the desired data item using a public key.

6. The method of claim 1, further comprising determining by the client whether the desired data item is stored in the database server using the search response message and a private key.

2. A method for determining by a client whether a desired data item is stored in a database server having a list of data items stored therein, the method comprising:

generating a search request message, that includes an encryption of a desired data item by the client, wherein a first algorithm is utilized for the encryption;

transmitting the search request message to the database server, wherein the desired data item is kept secret from the database server;

receiving from the database server a search response message, wherein the search response messaged is generated based on the search request message and based on the list of data items using a second algorithm that creates a polynomial with the encryption of the desired data item as a root of the polynomial; and

determining whether the desired data item is stored in the database server based on the search response message using a third algorithm, wherein the presence of any other data items of the list of data items is not revealed to the client.

7. The method of claim 2, further comprising generating the search request message in accordance with a public key.

8. The method of claim 2, wherein keeping secret the desired data item comprises encryption of a data number associated with the desired data item.

9. The method of claim 2, further comprising determining whether the desired data item is stored in the database server using a private key.

10. The method of claim 2, further comprising transmitting the search request message to a plurality of servers.

11. A system for searching a database server having a list of data items stored therein, the system comprising:

a search request message generation unit that generates a search request message that includes an encryption of a desired data item transmitted from a client to the database server, wherein a first algorithm is utilized for the encryption, wherein the desired data item is kept secret from the database server; and

a search response message generation unit that generates a search response message based on the search request message and based on the list of data items using a second algorithm that creates a polynomial with the encryption of the desired data item as a root of the polynomial, wherein the search response message is used to determine whether the desired data item exists in the database server without revealing the presence of any other data items of the list of data items to the client, and wherein the search response message is transmitted from the database server to the client.

13. The system of claim 11, wherein the search response message further comprises an n^th-order polynomial equation having the data items in the list of data items as its roots and the n^th-order polynomial equation is evaluated using the desired data item.

14. The system of claim 11, further comprising a pair of values calculated using a public key.

15. The system of claim 11, wherein the desired data item is kept secret by encrypting the desired data item using a public key.

16. The system of claim 11, further comprising a determination by the client whether the desired data item is stored in the database server using the search response message and a private key.

12. A system for determining by a client whether a desired data item is stored in a database server having a list of data items, the system comprising:

a search request message generation unit that generates a search request message that includes an encryption of a desired data item transmitted to the database server, wherein a first algorithm is utilized for the encryption, wherein the desired data item is kept secret from the database server;

a search response message generation unit that generates a search response message based on the search request message and based on the list of data items using a second algorithm that creates a polynomial with the encryption of the desired data item as a root of the polynomial, wherein the search response message is used to determine whether the desired data item exists in the database server without revealing the presence of any other data items of the list of data items to the client; and

a search result determination unit that determines whether the desired data item is stored in the database server based on the search response message using a third algorithm.

17. The system of claim 12, wherein the search request message is generated in accordance with a public key.

18. The system of claim 12, wherein the desired data item is kept secret using an encryption of a data number associated with the desired data item.

19. The system of claim 12, further comprising a determination whether the desired data item is stored in the database server using a private key.

20. The system of claim 12, further comprising a transmission of the search request message to a plurality of servers.