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

Patent metadata

Field	Value
Publication number	US-10223547-B2
Application number	US-201615290738-A
Country	US
Kind code	B2
Filing date	Oct 11, 2016
Priority date	Oct 11, 2016
Publication date	Mar 5, 2019
Grant date	Mar 5, 2019

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.

First claim

The invention claimed is:

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.

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.

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 v A ( b i,j ) ξ i,j ·E v A ( r i,j )

wherein:
E v A 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.

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.

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.

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

Assignees

• Palo Alto Res Ct Inc

Inventors

• Rane Shantanu
• Bindschaedler Vincent
• Brito Alejandro E
• Uzun Ersin
• Rao Vanishree

Classifications

• G06F21/6245 Primary

  Protecting personal data, e.g. for financial or medical purposes · CPC title

• H04L2209/08

  Randomization, e.g. dummy operations or using noise · CPC title

• H04L9/008

  involving homomorphic encryption · CPC title

• H04L9/085

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• H04L2209/16

  Obfuscation or hiding, e.g. involving white box · CPC title