Differentially private aggregate classifier for multiple databases

• US 8,375,030 B2
• Filed: 12/03/2010
• Issued: 02/12/2013
• 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
• Primary Examiner(s): Pham, Hung Q
• Application Number:
  US12/960,221
• Publication Number:
  US 20120143922A1
• Time in Patent Office: 802 Days
• Field of Search: None
• US Class Current: 707/736
• 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;

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;

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

selecting obliviously, from additive shares of all noise values, a first additive share of the noise value associated with the smallest database based on the obfuscated index, wherein a second additive share of the noise value 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, 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, wherein the noise value is distributed according to a Laplace distribution.

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

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

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

7. The method of claim 1, wherein the determining of the differentially private classifier is performed by a. cryptographic protocol.

8. The method of claim 1., wherein the determining of the differentially private classifier is performed by a secret sharing protocol.

9. 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:

a processor for combining classifiers to determine an aggregate classifier and 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, wherein the processor is further configured for determining an obfuscated index of the smallest database resulting from a permutation of indexes of the set of databases;

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

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

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

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

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