Preserving privacy when statistically analyzing a large database

• US 20060161527A1
• Filed: 01/18/2005
• Published: 07/20/2006
• Est. Priority Date: 01/18/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kobliner, Yaacov Nissim, Dwork, Cynthia
• Granted Patent: US 7,653,615 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes

Abstract

A database has a plurality of entries and a plurality of attributes common to each entry, where each entry corresponds to an individual. A query q is received from a querying entity query q and is passed to the database, and an answer a is received in response. An amount of noise e is generated and added to the answer a to result in an obscured answer o, and the obscured answer o is returned to the querying entity. Thus, a level of protection of privacy is provided to each individual represented within the database.

Claims

1. A method in connection with a database having a plurality of entries and a plurality of attributes common to each entry, each entry corresponding to an individual, the method for providing a level of protection of privacy of the individual, the method comprising:

receiving from a querying entity a query q;

passing the query q to the database;

receiving in response an answer a;

generating an amount of noise e;

adding the noise e to the answer a to result in an obscured answer o; and

returning the obscured answer o to the querying entity.

2. The method of claim 1 comprising generating the amount of noise e by:

calculating a number r;

effectively flipping an unbiased coin r times and counting a number of times heads is observed h; and

subtracting r/2 from h to result in e.

3. The method of claim 1 wherein each attribute for each entry is represented as binary data.

4. The method of claim 1 comprising generating an amount of noise e that obscures the answer a to a large-enough degree to protect privacy, but not to such a large degree so as to substantively affect statistical analysis of the database.

5. The method of claim 4 comprising generating an amount of noise e that is small enough to be insignificant with regard to built-in sampling error.

6. The method of claim 1 comprising generating an amount of noise e based at least in part on a perceived amount of loss of privacy p that is considered acceptable.

7. The method of claim 1 comprising generating an amount of noise e based at least in part on a number of times t that a particular querying entity can query the database.

8. The method of claim 1 comprising determining t as:

t=O(n^c) for some c<

1,

such that t is sub-linear in n.

9. A method in connection with a database having a plurality of entries and a plurality of attributes common to each entry, each entry corresponding to an individual, the database being partitioned into parts such that a first part includes an attribute A for each entry and a second part includes an attribute B for each entry, the method for providing a level of protection of privacy of the individual when performing a statistical analysis on the partitioned database based on attributes A and B, the method comprising:

computing a probability of any particular entry having attribute A(Pr[A]) as a total number of entries with attribute A set divided by all entries in the database;

computing a probability of any particular entry having attribute B (Pr[B]) as a total number of entries with attribute B set divided by all entries in the database;

presuming that A implies B in probability with a gap of G if the probability of A given B (Pr[B|A])=Pr[B]+G;

determining G by iteratively;

selecting a Gx;

determining whether for such Gx, Pr[B|A]>

=Pr[B]+Gx, and based thereon determining whether G(x+1) should be higher or lower, a number of times until an estimation of G is settled upon;

finding an estimate of Pr[B|A] based on the estimate of G and the computed Pr[B]; and

with the estimated Pr[B|A] employing standard Boolean arithmetic to perform the statistical analysis.

10. The method of claim 9 wherein each attribute for each entry is represented as binary data.

11. The method of claim 9 comprising determining whether for a Gx, Pr[B|A]>

=Pr[B]+Gx, and based thereon determining whether G(x+1) should be higher or lower, by;

finding a random subset S of entries in the first part of the database such that for a first query based on the subset S and attribute A (q1=(S, A)) results in an answer1>

|S|Pr[A]+(|S|Pr[A](1−

Pr[A]))^1/2;

querying the second part of the database based on the found subset S and attribute B (q2=(S, B) results in an answer2;

determining whether answer2>

=|S|Pr[B]+(answer1−

|S|Pr[A]) Gx/(1−

Pr[A]); and

if so determining that G is in fact greater than Gx, while if not determining that G is in fact less Gx.

12. The method of claim 11 further comprising querying the database by:

receiving from a querying entity each query q;

passing the query q to the database;

receiving in response an answer a;

generates an amount of noise e;

adding the noise e to the answer a to result in an obscured answer o; and

returning the obscured answer o to the querying entity.