Noise in secure function evaluation

• US 20070083493A1
• Filed: 10/06/2005
• Published: 04/12/2007
• Est. Priority Date: 10/06/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dwork, Cynthia, McSherry, Frank
• Granted Patent: US 8,005,821 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification

Abstract

Techniques are provided for injecting noise into secure function evaluation to protect the privacy of the participants. A system and method are illustrated that can compute 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 method for computing a collective noisy result, comprising:

receiving a query;

applying the query to a subset of data to obtain a subset result;

dividing the subset result into one or more shares;

participating in combining shares of subset results to obtain a collective result;

generating random bits;

participating in combining the random bits, wherein a combination of random bits is used to generate noise, and said noise is combined with the collective result to obtain a collective noisy result.

2. The method of claim 1, wherein the subset of data is privately stored on a 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 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. The method of claim 1, further comprising consulting a policy to determine whether to apply said query.

7. The method of claim 6, wherein said policy is stored separately from said subset of data.

8. A method for computing a collective noisy result, comprising:

distributing a query from a first computer to a plurality of computers;

applying the query by the computers to a plurality of subsets of data, to obtain a plurality of subset results;

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

the computers participating in combining the shares of subset results to obtain a collective result;

generating random bits by a plurality of said computers;

the computers participating in combining the random bits;

at least one computer generating noise based on a combination of the random bits;

at least one computer generating a collective noisy result by combining said collective result with the noise.

9. The method of claim 8, wherein at least one subset of data is privately stored on a computer.

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

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

12. The method of claim 8, further comprising limiting a number of queries that may be applied to at least one subset of data.

13. The method of claim 8, further comprising consulting a policy to determine whether to apply said query.

14. The method of claim 13, wherein said policy is stored separately from said subset of data.

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

a plurality of computing devices, each having access to a subset of data;

a mechanism for distributing a query to the computing devices;

each computing device applying the query to its subset of data to obtain a subset result;

each computing device dividing its subset result into one or more shares;

at least one computing device participating in combining the shares to obtain a collective result;

each computing device generating random bits;

at least one computing device participating in combining the random bits, generating noise based on said random bits, and combining said noise to the collective result to obtain a collective noisy result.

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

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

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

19. The system of claim 15, wherein there is a limit on a number of queries that may be applied to at least one subset of data.

20. The system of claim 15, wherein at least one computing device comprises a policy to determine whether to apply said query.