Information integration across autonomous enterprises

• US 8,041,706 B2
• Filed: 10/25/2007
• Issued: 10/18/2011
• Est. Priority Date: 06/09/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Evfimievski, Alexandre Valentinovich, Agrawal, Rakesh, Srikant, Ramakrishnan
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): PHILLIPS, III, ALBERT M
• Application Number:
  US11/924,519
• Publication Number:
  US 20080065910A1
• Time in Patent Office: 1,454 Days
• Field of Search: 707/999.01, 707/714, 707/770
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A system, method, and computer program product for processing a query spanning separate databases while revealing only minimal information beyond a query answer, by executing only specific information-limiting protocols according to query type.

Claims

1. A method comprising:

using a computer to process a query spanning a first database accessible by a first computer client and a second database accessible by a second computer client, the first database containing a first table containing a first set of values, and the second database containing a second table containing a second set of values;

executing specific information-limiting protocols according to a query type to produce a query answer, wherein said protocols process equijoin queries,

wherein a equijoin query includes;

references to the first computer client and the second computer client;

hash functions configured to be applied to sets of the first and second computer clients;

a secret key assigned to the first computer client and two secret keys assigned to the second computer client;

an encrypted hashed set of the first computer client;

a reordered and encrypted hashed set of the first computer client assigned to the second computer client; and

a set encrypted with both of the secret keys of the second computer client assigned to the first computer client as 3-tuples;

returning the query answer to the first computer client so that the first computer client learns from the query answer an intersection of the first set of values and the second set of values, and a cardinality of the second set of values;

learning by the first computer client the distribution of duplicates in the second table; and

revealing the query to the second computer client so that the second computer client learns from the query a cardinality of the first set of values.

2. The method of claim 1 wherein said protocols process queries of at least one of the following query types:

intersection, equijoin, intersection size, and equijoin size.

3. The method of claim 1 wherein said protocols use commutative encryption to limit the information revealed beyond the query answer.

4. The method of claim 1 including rejecting said query if no information-limiting protocol exists for the corresponding query type.

5. A general purpose computer system programmed with instructions comprising:

processing a query spanning a first database accessible by a first computer client and a second database accessible by a second computer client, the first database containing a first table containing a first set of values, and the second database containing a second table containing a second set of values;

executing specific information-limiting protocols according to a query type to produce a query answer, wherein said protocols process equijoin queries,

wherein an equijoin query includes;

the first and second computer clients;

hash functions configured to be applied to the sets of the first and second computer clients;

a secret key assigned to the first computer client and two secret keys assigned to the second computer client;

an encrypted hashed set of the first computer client;

a reordered and encrypted hashed set of the first computer client assigned to the second computer client; and

a set encrypted with both of the secret keys of the second computer client assigned to the first computer client as 3-tuples;

randomly choosing a secret key and encrypting a hashed second set of values;

returning the query answer to the first computer client so that the first computer client learns from the query answer an intersection of the first set of values and the second set of values, extra information for values in the intersection, and a cardinality of the second set of values; and

revealing the query to the second computer client so that the second computer client learns from the query a cardinality of the first set of values.

6. The system of claim 5 wherein said protocols process queries of at least one of the following query types:

intersection, equijoin, intersection size, and equijoin size.

7. The system of claim 5 wherein said protocols use commutative encryption to limit the information revealed beyond the query answer.

8. The system of claim 5 including rejecting said query if no information-limiting protocol exists for the corresponding query type.

9. A computer program product comprising a machine-readable medium having computer-executable program instructions thereon comprising:

code for a query spanning a first database accessible by a first computer client and a second database accessible by a second computer client, the first database containing a first table containing a first set of values, and the second database containing a second table containing a second set of values;

code for executing specific information-limiting protocols according to a query type to produce a query answer, wherein said protocols process equijoin queries,

wherein an equijoin query includes;

the first and second computer clients;

hash functions configured to be applied to the sets of the first and second computer clients;

a secret key assigned to the first computer client and two secret keys assigned to the second computer client;

an encrypted hashed set of the first computer client;

a reordered and encrypted hashed set of the first computer client assigned to the second computer client;

a set encrypted with both of the secret keys of the second computer client assigned to the first computer client as 3-tuples;

code for returning the query answer to the first computer client so that the first computer client learns from the query answer a cardinality of an intersection of the first set of values and the second set of values, and a cardinality of the second set of values; and

code for revealing the query to the second computer client so that the second computer client learns from the query a cardinality of the first set of values.