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

• US 7,409,406 B2
• Filed: 09/08/2003
• Issued: 08/05/2008
• Est. Priority Date: 09/08/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Bayardo, Roberto Javier, Bawa, Mayank
• Primary Examiner(s): Cottingham; John
• Assistant Examiner(s): RAYYAN, SUSAN F
• Application Number:
  US10/657,458
• Publication Number:
  US 20050055327A1
• Time in Patent Office: 1,793 Days
• Field of Search: 707/1, 707/3, 707 9- 10, 707/100, 707/102, 707/104.1
• US Class Current: 707/742
• 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 processor-implemented 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;

grouping the content providers into a plurality of privacy groups;

passing a content vector from a first content provider in a privacy group of the plurality of privacy groups to a second content provider in the privacy group of the plurality of privacy groups;

the first and second content providers operating on the content vector with a randomized algorithm;

sending a plurality of content vectors to a designated host, each content vector of the plurality of content vectors corresponding to a respective privacy group of the plurality of privacy groups;

aggregating the plurality of content vectors into a materialized index comprising the privacy-preserving index structure;

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

returning a list of the content providers having a subset of the content to be shared of the access-controlled documents that comprise a set of the keywords that satisfy a query.

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

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

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

5. The method of claim 1, 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.

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

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

8. The method of claim 1, wherein at least one privacy group of the plurality of privacy groups comprises at least three content providers.

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

10. The method of claim 9, further comprising arranging the content providers in the at least one privacy group in a ring formation.

11. The method of claim 10, wherein content providers in the ring formation sequentially operate on the content vector with a randomized algorithm.

12. The method of claim 11, further comprising the content providers in the ring formation passing the content vector and operating on the content vector with a randomized algorithm until the content vector has completed rounds around the ring formation.

13. The method of claim 12, further comprising each of the content providers in the ring formation ORing the passed content vector.

14. The method of claim 13, wherein the ORing introduces false positives in a result returned in response to the query.

15. The method of claim 1, wherein the plurality of content providers are all grouped into a single privacy group.