Preserving privacy when statistically analyzing a large database
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.
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 at a interface a query q from a querying entity; passing the query q to the database; receiving at a interface an answer a in response to the query q;
generating an amount of noise e at the interface 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, wherein r is calculated at least in part based on a number of times t that a particular querying entity queries the database and e generating an amount of noise e based at least in part on a perceived amount of loss of privacy p that is considered acceptable and small enough to be insignificant with regard to built-in sampling error;
adding the noise e to the answer a at the interface to result in an obscured answer o; and
the interface returning the obscured answer o to the querying entity.
2. The method of claim 1 wherein each attribute for each entry is represented as binary data.
3. 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.
4. 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.
5. A computer apparatus comprising:
a memory having stored thereon a database having a plurality of entries and a plurality of attributes common to each entry, each entry corresponding to an individual; and
a processor programmed to perform the steps of:
receiving a query q from a querying entity and for passing the query q to the database;
receiving from the database an answer a in response to the query q; generating an 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 and for adding the noise e to the answer a to result in an obscured answer o, wherein r is calculated at least in part based on a number of times t that a particular querying entity queries the database and e generates an amount of noise e based at least in part on a perceived amount of loss of privacy p that is considered acceptable and small enough to be insignificant with regard to built-in sampling error; and
returning the obscured answer o to the querying entity.
6. The computer apparatus of claim 5 wherein an amount of noise e is generated 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.
7. The computer apparatus of claim 5 , wherein the noise generating means determines t as:
t=O ( n c ) for some c <1,
such that t is sub-linear in n.