System and method for searching a database or data sharing system for the presence of data

• US 20040034628A1
• Filed: 04/22/2003
• Published: 02/19/2004
• 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
• Granted Patent: US 8,538,937 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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 of searching a data store by a client for the existence of a specific data in the data store that resides on a server, comprising:

the client rendering a search request for the specific data confidential;

the server receiving the confidential search request;

the server searching the data store based on the confidential search request, and a confidential list of data items stored on the data store;

the server returning a confidential search result; and

the client determining whether the specific data exists in the data store based on the confidential search result.

2. The method of claim 1, wherein rendering the search request confidential comprises generating a search request message from a data number.

3. The method of claim 2, wherein the data number is a unique number that is associated with the data items in the data store.

4. The method of claim 1, wherein the confidential search request contains a search data item;

and

wherein the server generates a polynomial having the search data item as a root.

5. The method of claim 4, wherein the server randomly generates the polynomial using a random number.

6. The method of claim 4, wherein the server generates the polynomial based on the confidential list of data items stored in the data store.

7. The method of claim 6, wherein the server solves the polynomial by substituting the search data item into the polynomial to generate a zero result.

8. The method of claim 7, wherein solving the polynomial comprises using an oblivious polynomial evaluation.

9. The method of claim 4, wherein rendering the search result confidential comprises encrypting the search data item.

10. The method of claim 1, wherein if the client determines that the specific data exists in the data store, the client sends a second search request to the server, requesting the specific data.

11. The method of claim 1, wherein the data store is accessible over a network.

12. The method of claim 11, wherein the network comprises the Internet.

13. The method of claim 1, wherein rendering the search request confidential comprises encrypting a data item associated with the specific data using a secret key.

14. The method of claim 11, wherein the client is connected through the network to a plurality of servers;

and

wherein the client broadcasts the confidential search request to the plurality of servers.

15. The method of claim 1, wherein the data store is shared by a plurality of peer-to-peer servers over a network.

16. A computer program product having instruction codes for searching a data store by a client for the existence of a specific data in the data store that resides on a server, comprising:

a first set of instruction codes for use by the client to render a search request for the specific data confidential;

a second set of instruction codes for use by the server to receive the confidential search request;

a third set of instruction codes for use by the server to search the data store based on the confidential search request, and a confidential list of data items stored on the data store;

a fourth set of instruction codes for use by the server to return a confidential search result; and

a fifth set of instruction codes for use by the client to determine whether the specific data exists in the data store based on the confidential search result.

17. The computer program product of claim 16, wherein the first set of instruction codes generates a search request message from a data number;

and

wherein the data number is a unique number that is associated with the data items in the data store.

18. The computer program product of claim 16, wherein the confidential search request contains a search data item;

and

wherein the server generates a polynomial having the search data item as a root.

19. The computer program product of claim 18, wherein the server solves the polynomial using an oblivious polynomial evaluation.

20. The computer program product of claim 16, wherein the first set of instruction codes renders the search request confidential by encrypting a data item associated with the specific data using a secret key.

21. The computer program product of claim 16, wherein the client is connected to a plurality of servers;

and

wherein the client comprises a sixth set of instruction codes for broadcasting the confidential search request to the plurality of servers.

22. The computer program product of claim 16, wherein the data store is shared by a plurality of peer-to-peer servers over a network.

23. A system for searching a data store by a client for the existence of a specific data in the data store that resides on a server, comprising:

means for use by the client for rendering a search request for the specific data confidential;

means for use by the server for receiving the confidential search request;

means for use by the server for searching the data store based on the confidential search request, and a confidential list of data items stored on the data store;

means for use by the server for returning a confidential search result; and

means for use by the client for determining whether the specific data exists in the data store based on the confidential search result.

24. The system of claim 23, wherein the means for rendering the search request confidential generates a search request message from a data number;

and

wherein the data number is a unique number that is associated with the data items in the data store.

25. The system of claim 23, wherein the confidential search request contains a search data item;

and

wherein the server generates a polynomial having the search data item as a root.

26. The system of claim 25, wherein the server solves the polynomial using an oblivious polynomial evaluation.

27. The system of claim 23, wherein the means for rendering the search request confidential encrypts a data item associated with the specific data using a secret key.

28. The system of claim 23, wherein the client is connected to a plurality of servers over a network.

29. The system of claim 28, wherein the client further comprises means for broadcasting the confidential search request to the plurality of servers.

30. The system of claim 23, wherein the data store is shared by a plurality of peer-to-peer servers over a network.