Uniform search system and method for selectively sharing distributed access-controlled documents

• US 20050055327A1
• Filed: 09/08/2003
• Published: 03/10/2005
• Est. Priority Date: 09/08/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Bayardo, Roberto Javier, Bawa, Mayank
• Granted Patent: US 7,409,406 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A privacy-preserving index system addresses the problem of providing a privacy-preserving search over distributed access-controlled content. Indexed documents can be readily reconstructed from inverted indexes used in the search. The privacy-preserving index system builds a centralized privacy-preserving index in conjunction with a distributed access-control enforcing search protocol. The privacy-preserving index utilizes a randomized algorithm for constructing a privacy-preserving index. The privacy-preserving index is strongly resilient to privacy breaches. The privacy-preserving index system allows content providers to maintain complete control in defining access groups and ensuring its compliance, and further allows system implementors to retain tunable knobs to balance privacy and efficiency concerns for their particular domains.

Claims

1. A method of selectively sharing a plurality of distributed access-controlled documents, comprising:

a plurality of content providers cooperating to create a privacy-preserving index structure; and

the privacy-preserving index structure mapping a plurality of keywords representing a content to be shared to the plurality of content providers.

2. The method of claim 1, wherein the content providers comprise a provider specific search interface for receiving a query and for authenticating a searcher.

3. The method of claim 2, further comprising the searcher submitting the query containing one or more keywords to a privacy-preserving index system.

4. The method of claim 3, further comprising returning a list of content providers that present the one or more keywords in the content to be shared.

5. The method of claim 4, wherein the list of content providers comprises at least 50% false positive content providers.

6. The method of claim 4, further comprising the searcher submitting the query annotated with an identity for the searcher to a specified content provider on the list of content providers.

7. The method of claim 6, further comprising the specified content provider authenticating the identity of the searcher for allowing access to the content to be shared.

8. The method of claim 7, further comprising the specified content provider returning to the searcher one or a plurality of documents that match the one or more keywords.

9. The method of claim 1, further comprising grouping the plurality of content providers into a plurality of privacy groups.

10. The method of claim 1, wherein the at least one privacy group comprises at least three contents.

11. The method of claim 1, wherein each of the content providers is grouped into one privacy group.

12. The method of claim 10, further comprising performing a randomized index construction algorithm to create the bit vectors for the content providers in the at least one privacy group.

13. The method of claim 12, further comprising arranging the content providers in the privacy group in a ring formation.

14. The method of claim 13, further comprising creating bit vectors for the plurality of content providers one or more keywords representing a content to be shared.

15. The method of claim 14, further comprising combining the bit vectors into group vectors.

16. The method of claim 15, further comprising storing the group vectors in a privacy-preserving index.

17. The method of claim 13, wherein creating the bit vectors for the content providers comprises creating a randomized bit vector.

18. The method of claim 17, further comprising passing the randomized bit vector to a first provider in the ring formation in the privacy group.

19. The method of claim 12, wherein a content provider performs the randomized index construction algorithm to create a provider keyword bit vector.

20. The method of claim 18, further comprising the first provider passing the provider keyword bit vector to a next content provider in the ring formation in the privacy group.

21. The method of claim 19, wherein content providers in the ring formation sequentially perform the randomized index construction algorithm on the provider keyword bit vector.

22. The method of claim 21, further comprising the content providers in the ring formation passing provider keyword bit vectors and performing the randomized construction algorithm on the keyword bit vector until the provider keyword bit vector has completed r rounds around the ring formation.

23. The method of claim 22, further comprising ORing the provider keyword bit vectors into a group keyword bit vector.

24. The method of claim 23, wherein ORing the provider keyword bit vectors into the group keyword bit vector introduces false positives in a result returned in response to the query.

25. A computer program product having a plurality of instruction codes for selectively sharing a plurality of distributed access-controlled documents, comprising:

a plurality of content providers comprising a first set of instruction codes for cooperating to create a privacy-preserving index structure; and

the privacy-preserving index structure comprising a second set of instruction codes for mapping a plurality of keywords representing a content to be shared to the plurality of content providers.

26. The computer program product of claim 25, wherein the content providers comprise a third set of instruction codes for receiving a query and for authenticating a searcher.

27. The computer program product of claim 26, further comprising the searcher submitting the query containing one or more keywords to a privacy-preserving index system.

28. The computer program product of claim 27, further comprising returning a list of content providers that present the one or more keywords in the content to be shared.

29. The computer program product of claim 25, further comprising a fourth set of instruction codes for grouping the plurality of content providers into a plurality of privacy groups.

30. The computer program product of claim 29, further comprising a fifth set of instruction codes for performing a randomized index construction algorithm to create the bit vectors for the content providers in the plurality of privacy groups.

31. A system for selectively sharing a plurality of distributed access-controlled documents, comprising:

a plurality of content providers that cooperate to create a privacy-preserving index structure; and

the privacy-preserving index structure map a plurality of keywords representing a content to be shared to the plurality of content providers.

32. The system of claim 31, wherein the content providers comprise a provider specific search interface for receiving a query and for authenticating a searcher.

33. The system of claim 32, wherein the searcher submits the query containing one or more keywords to a privacy-preserving index system.

34. The system of claim 33, wherein on receiving the query, at least some of the content providers return a list of filtered documents.

35. The system of claim 31, wherein the plurality of content providers are grouped into a plurality of privacy groups.