Privacy-preserving data aggregation using homomorphic encryption

• US 7,856,100 B2
• Filed: 12/19/2005
• Issued: 12/21/2010
• Est. Priority Date: 12/19/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Jiahe Helen, Huang, Qiang, Jao, David
• Primary Examiner(s): Moazzami; Nasser
• Assistant Examiner(s): Louie; Oscar A
• Application Number:
  US11/311,916
• Publication Number:
  US 20070140479A1
• Time in Patent Office: 1,828 Days
• Field of Search: None
• US Class Current: 380/30
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

A method and system for collecting data from devices using a homomorphic encryption of the data is provided. A collection system of a device adds contributions to homomorphically encrypted data and forwards the requests to another device. When the device receives a reply to the request, it uncombines its contribution to the homomorphic encryption of the data. The device then forwards the reply to the previous device. The initiator device ultimately removes its contribution to the encryption and identifies the data.

Claims

1. A method in a device that provides data, the method comprising:

receiving by the device from a previous device a request for device data that includes a public key and a homomorphic encryption of received data based on the public key;

combining by the device the received public key with a device public key into a combined public key;

generating by the device a homomorphic encryption of device data to be added to the request using the combined public key;

combining by the device the generated homomorphic encryption of the device data with the homomorphic encryption of the received data into a homomorphic encryption of the combined data; and

forwarding by the device to a next device the combined public key and the homomorphic encryption of the combined data

wherein (G,·

) is a group and gε

G and the homographic encryption of the device data is represented by the following;

x_i=g^ri

y_i=(g^s·

g^si)^ri·

g^mi=g^ris+s)·

g^mi

where r_i is a device-specific number, g^s is the received public key, g^s+si is the combined public key, s and s_i are secrets for the received and device public keys, and m_i is the device data and

wherein (g^r, g^rs·

g^m) is the homomorphic encryption of the received data and where the combined homomorphic encryption of the data is represented by the following;

x′

=g^r+ri

y′

=g^(r+ri)(s+si)·

g^m+mi

where x′

is a first component and y′

is a second component of the combined homomorphic encryption represented by (x′

, y′

).

2. The method of claim 1 including:

receiving from the next device a reply that includes a return public key and a homomorphic encryption of collected data;

uncombining from the return public key the device public key;

uncombining from the homomorphic encryption of the collected data the device public key; and

forwarding to the previous device the uncombined public key and the uncombined homomorphic encryption of the collected data.

3. The method of claim 2 wherein the uncombined public key is represented by the following:

4. The method of claim 3 wherein the uncombined homomorphic encryption of the collected data is represented by the following:

x′

=g^r

y′

=g<sup>r(s−

si)</sup>·

g^m

where x′ and

y′

are first and second components of the uncombined homomorphic encryption of the collected data encryption represented by (x′

, y′

).

5. The method of claim 4 wherein an initiator device upon receiving a reply for data, determines g^m as represented by the following:

6. The method of claim 5 wherein the initiator device determines m by comparing g^m to g^k where k represents possible values of m.

7. A method of collecting information of devices of a cluster, the method comprising:

distributing a new public key to devices of the cluster including;

receiving from a previous device a request for data that includes a public key and a homomorphic encryption of data including a first component and a second component;

sending to one or more key holder devices a request for a key holder public key, the request including the first component of the homomorphic encryption of the received data;

receiving from the one or more key holder devices a key holder public key derived from a key holder secret and a key holder device first component that is the first component modified to factor in the key holder public key;

combining the one or more key holder public keys with the received public key into the new public key;

combining the one or more key holder first components with the received first component into a new first component;

providing the new public key to each device of the cluster; and

providing the aggregator device of the cluster the second component of the homomorphic encryption; and

for each of a plurality of devices of the cluster, sending by that device of the plurality of devices of the cluster to other devices of the cluster shares of information that that device of the plurality of devices of the cluster is to contribute;

for each of a plurality of devices of the cluster, sending by that device of the plurality of devices of the cluster to the aggregator device of the cluster a homomorphic encryption of a total of the shares received from other devices of the cluster based on the new public key; and

at the aggregator device, adding by the aggregator device the homomorphic encryption of the totals of the shares received from each of the plurality of devices of the cluster into a homomorphic encryption of aggregate data of the cluster.

8. The method of claim 7 where (G,·

) is a group and gε

G, g^s is a public key for secret s, and the homographic encryption of data is (g^r, g^rs·

g^m), with g^r being the first component and g^rs·

g^m being the second component, wherein a key holder first component x_i is represented by the following;

p_i=g^si

x_i=g^rsi

where p_i is the public key contribution of key holder device i;

x_i is the first component contribution of key holder device i; and

s_i is a secret of key holder device i.

9. The method of claim 8 wherein the new public key and the first component are represented by the following:

p′

=g^{s+s0+ . . . +sn}

x′

=g^{r(s+s0+ . . . +sn)}

where n is the number of the key holder device.

10. A method of collecting information of devices of a cluster, the method comprising:

distributing a new public key to devices of the cluster;

for each of a plurality of devices of the cluster, sending by that device of the plurality of devices of the cluster to other devices of the cluster shares of information that that device of the plurality of devices of the cluster is to contribute;

for each of a plurality of devices of the cluster, sending by that device of the plurality of devices of the cluster to an aggregator device a homomorphic encryption of a total of the shares received from other devices of the cluster based on the new public key; and

at the aggregator device, adding by the aggregator device the homomorphic encryption of the totals of the shares received from each of the plurality of devices of the cluster into a homomorphic encryption of aggregate data of the cluster

wherein (G,·

) is a group and gε

G and the homographic encryption of data is (g^r, g^rs·

g^m) with g^r being a first component of (G,·

) and g^rs·

g^m being a second component of (G,·

) and wherein a device of the cluster totals shares based on the new public key as represented by the following;

x_j=g^rj

y_j=g^rjsi·

g^mj

 

where x_j is a first component for device j and y_j is a second component for device j, r_j is a device-specific number, g^s is the new public key, and m_j is the total of the shares sent to the device j.

11. The method of claim 10 including

forwarding the request with the aggregated homomorphic data to a next device;

and

upon receiving a response to the request including a return public key and a homomorphic encryption of collected data, modifying the return public key and the second component of the homographic encryption of the collected data to remove the contribution of each key holder device to the public key.

12. The system of claim 11 wherein the data is configuration data.

13. A computer system configured for collecting data from devices, the system including:

a memory storing computer-executable instructions of;

a component that receives a request for device data that includes a public key from a previous device and a homomorphic encryption of received data;

a component that generates a new public key;

a component that homomorphically encrypts a combination of the homomorphic encryption of the received data and device data;

a component that forwards the new public key and the homomorphic encryption of the combined data to a next device;

a component that receives a reply for data that includes a public key and a homomorphic encryption of collected data

a component that uncombines the contribution of the device to the received public key and the homomorphic encryption of the combined data and

a component that forwards the reply to the previous device;

wherein the device is a cluster device of a cluster that contributes to the collected data by distributing shares of its contribution to other cluster devices and that totals the shares received from other cluster devices and forwards the totals to an aggregator device for aggregating into the total contribution of the cluster; and

a processor for executing the computer-executable instructions stored in the memory.