Method for differentially private aggregation in a star topology under a realistic adversarial model

• US 10,223,547 B2
• Filed: 10/11/2016
• Issued: 03/05/2019
• Est. Priority Date: 10/11/2016
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Rane, Shantanu, Bindschaedler, Vincent, Brito, Alejandro E., Uzun, Ersin, Rao, Vanishree
• Primary Examiner(s): Hoffman, Brandon S
• Assistant Examiner(s): Ambaye, Samuel
• Application Number:
  US15/290,738
• Publication Number:
  US 20180101697A1
• Time in Patent Office: 875 Days
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

One embodiment provides a system for noise addition to enforce data privacy protection in a star network. In operation, participants may add a noise component to a dataset. An aggregator may receive the noise components from the plurality of participants, compute an overall noise term based on the received noise components, and aggregate values using the noise components and overall noise term.

Claims

1. A system comprising one or more processors, the one or more processors comprising an aggregator and a plurality of participants, each participant of the plurality of participants being configured to add a noise component to a data component, and the aggregator configured to:

receive homomorphic encryptions of the noise components from each participant of the plurality of participants, wherein the noise components are sampled from a probability distribution;

decrypt the homomorphic encryptions of the noise components to determine an overall noise term based on a subset of the noise components; and

combine the noise components into the overall noise term, wherein the overall noise term is used to modify an aggregate function of the data components;

wherein the aggregator is further configured to compute the overall noise term from an aggregation of n noise components while hiding which n noise components were included in the overall noise term from all participants of the plurality of participants.

2. The system of claim 1, wherein the aggregator is further configured to obliviously compute the overall noise term.

3. The system of claim 1, wherein the aggregator is further configured to obliviously compute the overall noise term, and further configured to not influence any noise component of the plurality of noise components.

4. The system of claim 1, wherein the aggregator is further configured to prove to each participant of the plurality of participants that conditions on a generated binary sequence are satisfied showing that the aggregator is honest.

5. The system of claim 1, wherein a participant of the plurality of participants is configured to hide the noise component the participant is configured to add from the participant.

13. The system of claim 1, wherein the aggregator and the plurality of participants form a strict star topology.

6. A computer-implemented method for noise addition to enforce data privacy, the method comprising:

generating binary sequences;

generating homomorphic encryptions of the binary sequences to form ciphertexts;

sending the ciphertexts to each participant of the plurality of participants;

selecting, based on the ciphertext received at each participant, noise components sampled by the participant from a probability distribution to generate an encrypted value at each participant;

computing an overall noise term by aggregating n noise components while hiding which n noise components were included in the overall noise term from all participants of the plurality of participants;

receiving the encrypted value from each participant of the plurality of participants;

decrypting the encrypted value; and

,

aggregating the decrypted values with a private aggregation protocol.

8. The computer-implemented method of claim 6, wherein the private aggregation protocol is based on Shamir Secret Sharing.

9. The computer-implemented method of claim 6, further comprising, with a participant of the plurality of participants:

detecting cheating by the aggregator; and

in response to the detection of cheating, attempting to notify other participants of the plurality of participants of the detected cheating.

10. The computer-implemented method of claim 6, wherein each participant of the plurality of participants acts as a verifier to perform a verification to determine cheating by the aggregator.

11. The computer-implemented method of claim 10, wherein the verification is based on a generated binary sequence.

7. A computer-implemented method for noise addition to enforce data privacy, the method comprising:

generating binary sequences;

generating homomorphic encryptions of the binary sequences to form ciphertexts;

sending the ciphertexts to each participant of the plurality of participants;

selecting, based on the ciphertext received at each participant, noise components sampled by the participant from a probability distribution to generate an encrypted value at each participant;

receiving the encrypted value from each participant of the plurality of participants;

decrypting the encrypted value; and

,

aggregating the decrypted values with a private aggregation protocol;

wherein the encrypted values are denoted as e_i,j, and are computed with the following formula;

e_i,j=E_vA(b_i,j)<sup>ξ

i,j</sup>·

E_vA(r_i,j)

wherein;

E_vA is a function to generate a ciphertext based on public key v_A;

b_i,j is a generated binary sequence;

ξ

_i,j is a noise component; and

r_i,j is a blinding term.

12. A system for implementing differential privacy, the system comprising:

one or more processors; and

a storage device storing instructions that when executed by the one or more processors cause the one or more processors to perform a method, the method comprising;

generating binary sequences;

generating homomorphic encryptions of the binary sequences to form ciphertexts;

sending the ciphertexts to each participant of the plurality of participants;

selecting, based on the ciphertext received at each participant, noise components sampled by the participant from a probability distribution to generate an encrypted value at each participant;

computing an overall noise term by aggregating n noise components while hiding which n noise components were included in the overall noise term from all participants of the plurality of participants;

receiving the encrypted value from each participant of the plurality of participants;

decrypting the received encrypted value; and

,

aggregating the decrypted values with a private aggregation protocol.