Noise in secure function evaluation

• US 8,005,821 B2
• Filed: 10/06/2005
• Issued: 08/23/2011
• Est. Priority Date: 10/06/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: McSherry, Frank D., Dwork, Cynthia
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Tran; Bao G
• Application Number:
  US11/244,800
• Publication Number:
  US 20070083493A1
• Time in Patent Office: 2,147 Days
• Field of Search: 707/5, 707/531, 707/532, 707/3, 707/100, 707/1, 707/718, 707/722, 707/759, 704/9, 705/80, 705/50, 705/31, 705/26, 702/107, 703/3, 726/1, 725/19, 715/234, 715/758
• US Class Current: 707/718
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification

Abstract

Systems and methods for injecting noise into secure function evaluation to protect the privacy of the participants and for computing a collective noisy result by combining results and noise generated based on input from the participants. When implemented using distributed computing devices, each device may have access to a subset of data. A query may be distributed to the devices, and each device applies the query to its own subset of data to obtain a subset result. Each device then divides its subset result into one or more shares, and the shares are combined to form a collective result. The devices may also generate random bits. The random bits may be combined and used to generate noise. The collective result can be combined with the noise to obtain a collective noisy result.

Claims

1. A computer-implemented method for computing a collective noisy result, the method comprising:

a computer receiving a query from a querying entity, wherein the query received from the querying entity is regarding a data collection comprising a plurality of subsets of the data collection, each subset associated with a corresponding privacy principal;

the computer determining whether the query received from the querying entity conforms to a corresponding data-independent policy determined by each of a plurality of privacy principals, each data-independent policy based upon the querying entity; and

the computer limiting a number of queries applied to a subset of data associated with one of the plurality of privacy principals by applying the query received from the querying entity to the subset of data associated with the one of the plurality of privacy principals only if the query received from the querying entity conforms to the data independent policy determined by the privacy principal associated with the subset of data to obtain a subset result, by;

the computer dividing the subset result into one or more shares;

the computer participating in combining shares of subset results by exchanging shares with another computer to obtain a collective result;

the computer generating random bits;

the computer combining the random bits, wherein a combination of random bits is used to generate noise, wherein said noise is an unknown and unpredictable quantity having a known distribution, and wherein an amount of the noise generated is dependent upon the data independent policy; and

the computer combining said noise with the collective result to obtain a collective noisy result as the subset result.

2. The method of claim 1, wherein the subset of data is privately stored on the computer.

3. The method of claim 1, wherein the subset of data comprises personal information about a human.

4. The method of claim 1, wherein the query received from the querying entity is simultaneously received by a plurality of computers, and wherein a subset of data is privately stored on each of said computers.

5. The method of claim 1, wherein said combining the random bits uses distributed coin flipping.

6. A computer-implemented method for computing a collective noisy result, the method comprising:

receiving a query, associated with a querying entity, from a first computer at a plurality of computers;

determining whether the received query conforms to a corresponding data-independent policy determined by each of a plurality of privacy principals, each data-independent policy based upon the querying entity; and

the plurality of computers limiting a number of queries applied to each of a plurality of subsets of data, each subset of data associated with a privacy principal by applying the received query to a subset of data only if the received query conforms to the data independent policy determined by the privacy principal associated with the subset of data to obtain a plurality of subset results;

the plurality of computers dividing the subset results into one or more shares;

the plurality of computers combining the shares of subset results by exchanging shares with another computer to obtain a collective result;

the plurality of computers generating random bits;

the plurality of computers combining the random bits;

at least one computer of said plurality of computers generating noise based on a combination of the random bits wherein said noise is an unknown and unpredictable quantity having a known distribution, and wherein an amount of the noise generated is dependent upon the data independent policy; and

at least one computer of said plurality of computers generating a collective noisy result as said plurality of subset results by combining said collective result with an amount of the noise, wherein the amount of the noise combined with said collective result is dependent upon a total number of queries to which the data is exposed throughout a lifetime of the data.

7. The method of claim 6, wherein at least one subset of data is privately stored on one of said plurality of computers.

8. The method of claim 6, wherein at least one subset of data comprises personal information about a human.

9. The method of claim 6, wherein said combining the random bits uses distributed coin flipping.

10. A system for computing a collective noisy result, comprising:

a plurality of computing devices, each computing device having access to a subset of data, each subset of data associated with a privacy principal, and a corresponding data-independent policy, determined by the associated privacy principal, for determining one or more queries in which the computing device will participate, each of the data-independent policies based upon an origin of one or more of queries, wherein the corresponding data-independent policy of each computing device is independent of the subset of data and wherein the computing device will not participate in queries that do not conform to the data-independent policy;

a mechanism for distributing a query to the computing devices;

each computing device configured to limit a number of queries applied to its subset of data by applying the distributed query to each subset of data only if the distributed query conforms to the data independent policy determined by the privacy principal associated with the subset of data to obtain a subset result;

each computing device configured to divide its subset result into one or more corresponding shares;

at least one computing device configured to receive the corresponding shares of each computing device and to participate in combining the received shares by exchanging shares with another computer to obtain a collective result, wherein the at least one computing device cannot determine the corresponding computing device of each received share;

each computing device configured to generate random bits; and

at least one computing device configured to participate in combining the random bits and in generating noise based on said random bits, wherein said noise is an unknown and unpredictable quantity having a known distribution, said at least one computing device being further configured to combine an amount of said noise to the collective result to obtain a collective noisy result, wherein the amount of said noise combined with said collective result is dependent upon a total number of queries to which the data is exposed throughout a lifetime of the data, and wherein the amount of said noise is dependent upon the data independent policy.

11. The system of claim 10, wherein at least one subset of data is privately stored on a computer.

12. The system of claim 10, wherein at least one subset of data comprises personal information about a human.

13. The system of claim 10, wherein said combining the random bits uses distributed coin flipping.