Differentially private aggregate classifier for multiple databases

• US 20120143922A1
• Filed: 12/03/2010
• Published: 06/07/2012
• Est. Priority Date: 12/03/2010
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Rane, Shantanu, Pathak, Manas A., Ramakrishnan, Bhiksha
• Granted Patent: US 8,375,030 B2
• Time in Patent Office: Days
• US Class Current: 707/803
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06Q 10/00 Administration; Management

Abstract

Embodiments of the invention disclose a system and a method for determining a differentially private aggregate classifier for a set of databases, wherein each database in the set of databases is associated with a classifier and a noise value, wherein the classifier and the noise value are determined locally for each database, such that a combination of the classifier and the noise value ensure a differential data privacy of the database, and wherein the differentially private aggregate classifier preserves the differential data privacy of each database. The differentially private aggregate classifier is a combination of the classifiers of the set of databases modified with the noise value corresponding to a smallest database in the set of databases.

Claims

1. A method for determining a differentially private aggregate classifier for a set of databases, wherein each database in the set of databases is associated with a classifier and a noise value, wherein the classifier and the noise value are determined locally for each database, such that a combination of the classifier and the noise value ensure a differential data privacy of the database, and wherein the differentially private aggregate classifier preserves the differential data privacy of each database, comprising the steps of:

combining classifiers to determine an aggregate classifier; and

modifying the aggregate classifier with a noise value corresponding to a smallest database in the set of databases to produce the differentially private aggregate classifier, wherein the steps of the method are performed by a processor.

2. The method of claim 1, wherein the smallest database has a smallest number of entries, wherein data structures of the entries are identical for all databases.

3. The method of claim 1, further comprising:

determining an obfuscated index of the smallest database resulting from a permutation of indexes of the databases;

selecting obliviously, from additive shares of all noise values, a first additive share of a noise value associated with the smallest database based on the obfuscated index, wherein a second additive share is stored in one or more databases; and

determining the differentially private aggregate classifier by obliviously combining each classifier, the first and the second additive shares of the noise value.

4. The method of claim 1, wherein the noise value is distributed according to a Laplace distribution.

5. The method of claim 1, wherein the noise value for each database is determined based on a size of the database.

6. The method of claim 1 wherein the classifier is a binary logistic regression classifier.

7. The method of claim 6, wherein the classifier is a multiclass classifier constructed from a combination of binary logistic regression classifiers.

8. The method of claim 3 wherein the determining of the differentially private classifier is performed by a cryptographic protocol.

9. The method of claim 3 wherein the determining of the differentially private classifier is performed by a secret sharing protocol.

10. A system for determining a differentially private aggregate classifier for a set of databases, wherein each database in the set of databases is associated with a classifier and a noise value, wherein the classifier and the noise value are determined locally for each database, such that a combination of the classifier and the noise value ensure a differential data privacy of the database, and wherein the differentially private aggregate classifier preserves the differential data privacy of each database, comprising:

means for combining classifiers to determine an aggregate classifier; and

means for modifying the aggregate classifier with a noise value corresponding to a smallest database in the set of databases to produce the differentially private aggregate classifier.

11. The system of claim 10, wherein the smallest database has a smallest number of entries, wherein data structures of the entries are identical for all databases.

12. The system of claim 10, further comprising:

means for determining an obfuscated index of the smallest database resulting from a permutation of indexes of the databases;

means for selecting obliviously, from additive shares of all noise values, a first additive share of a noise value associated with the smallest database based on the obfuscated index, wherein a second additive share is stored in one or more databases; and

means for determining the differentially private aggregate classifier by obliviously combining each classifier, the first and the second additive shares of the noise value.

13. The system of claim 10, wherein the noise value is distributed according to a Laplace distribution.

14. The system of claim 10, wherein the noise value for each database is determined based on a size of the database.

15. A computer readable medium storing a differentially private aggregate classifier for a set of databases, wherein each database in the set of databases is associated with a classifier and a noise value, wherein the classifier and the noise value are determined locally for each database, such that a combination of the classifier and the noise value ensure a differential data privacy of the database, wherein the differentially private aggregate classifier is a combination of the classifiers of the set of databases modified with the noise value corresponding to a smallest database in the set of databases.