FAULT-TOLERANT AGGREGATION OF ENCRYPTED DATA IN A STAR NETWORK

• US 20170272246A1
• Filed: 03/17/2016
• Published: 09/21/2017
• Est. Priority Date: 03/17/2016
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Rane, Shantanu, Brito, Alejandro E., Uzun, Ersin
• Granted Patent: US 10,069,631 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: H04L 2209/46 Secure multiparty computation, e.g. millionaire problem
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• 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

One embodiment provides a system that facilitates encrypted-domain aggregation of data in a star network. During operation, the system receives a set of ciphertexts, representing respective encrypted polynomial shares, of an input value from each participant in a plurality of participants. Each ciphertext in the set of ciphertexts is associated with a specific participant in the plurality of participants. The system computes an encrypted partial value for each participant by aggregating in the encrypted-domain a respective ciphertext associated with that participant received from the plurality of participants and sends a message comprising the encrypted partial value to that participant. This encrypted partial value is encrypted based on a public key of a corresponding participant. The system receives a decrypted partial value from each participant and computes a target value based on a set of decrypted partial values received from a set of participants in the plurality of participants.

Claims

1. A computer-implemented method for facilitating encrypted-domain aggregation of data in a star network, the method comprising:

receiving a set of ciphertexts of an input value from each participant of a plurality of participants via the star network, wherein the set of ciphertexts represents respective encrypted polynomial shares of the input value of that participant, and wherein each ciphertext in the set of ciphertexts is associated with a specific participant in the plurality of participants;

computing an encrypted partial value for each participant by aggregating in the encrypted-domain a respective ciphertext associated with that participant received from the plurality of participants, wherein the encrypted partial value is encrypted based on a public key of that participant;

sending a message comprising the encrypted partial value for each participant to the corresponding participant;

receiving a decrypted partial value representing a decryption of the encrypted partial value from each participant; and

computing a target value based on a set of decrypted partial values received from a set of participants in the plurality of participants.

2. The method of claim 1, wherein the public key of each participant is based on a homomorphic cryptosystem.

3. The method of claim 1, wherein the aggregation of a respective ciphertext associated with each participant is a computation of one of:

a summation, a weighted summation, a histogram, a mean, a variance and higher moments, a linear combination, a classifier, and a count query.

4. The method of claim 1, further comprising sending a large prime number to the plurality of participants, wherein the polynomial secret sharing at each participant is performed by computing a modulo value using the large prime number.

5. The method of claim 1, wherein computing the target value comprises:

determining whether the number of participants in the set of participants is greater than a threshold;

in response to the number of participants being greater than the threshold, determining a set of coefficients of a target polynomial; and

evaluating the target polynomial based on a base value and the coefficients.

6. The method of claim 1, further comprising:

dividing the plurality of participants into a number of cohorts;

assigning an obfuscator to a respective cohort, wherein the obfuscator adds an obfuscation value in a ciphertext from the obfuscator; and

computing a target value for a respective cohort, wherein the target value includes the obfuscation value.

7. The method of claim 6, wherein the plurality of participants are obfuscators of a previous round;

and

wherein a participant, which is not an obfuscator in a cohort, includes a negative obfuscation value in a ciphertext.

8. The method of claim 6, further comprising:

determining a number of current participants to be less than or equal to a cohort size;

forming a final cohort with the current participants without an obfuscator; and

computing a target value for the final cohort.

9. The method of claim 1, wherein computing an encrypted partial value further comprises including a random value in the aggregation.

10. A computer system for facilitating encrypted-domain aggregation of data in a star network, the system comprising:

a processor; and

a storage device storing instructions that when executed by the processor cause the processor to perform a method, the method comprising;

receiving a set of ciphertexts of an input value from each participant of a plurality of participants via the star network, wherein the set of ciphertexts represents respective encrypted polynomial shares of the input value of that participant, and wherein each ciphertext in the set of ciphertexts is associated with a specific participant in the plurality of participants;

computing an encrypted partial value for each participant by aggregating in the encrypted-domain a respective ciphertext associated with that participant received from the plurality of participants, wherein the encrypted partial value is encrypted based on a public key of that participant;

sending a message comprising the encrypted partial value for each participant to the corresponding participant;

receiving a decrypted partial value representing a decryption of the encrypted partial value from each participant; and

computing a target value based on a set of decrypted partial values received from a set of participants in the plurality of participants.

11. The computer system of claim 10, wherein the public key of each participant is based on a homomorphic cryptosystem.

12. The computer system of claim 10, wherein the aggregation of a respective ciphertext associated with each participant is a computation of one of:

a summation, a weighted summation, a histogram, a mean, a variance and higher moments, a linear combination, a classifier, and a count query.

13. The computer system of claim 10, wherein the method further comprises sending a large prime number to the plurality of participants, wherein the polynomial secret sharing at each participant is performed by computing a modulo value using the large prime number.

14. The computer system of claim 10, wherein computing the target value comprises:

determining whether the number of participants in the set of participants is greater than a threshold;

in response to the number of participants being greater than the threshold, determining a set of coefficients of a target polynomial; and

evaluating the target polynomial based on a base value and the coefficients.

15. The computer system of claim 10, wherein the method further comprises:

dividing the plurality of participants into a number of cohorts;

assigning an obfuscator to a respective cohort, wherein the obfuscator adds an obfuscation value in a ciphertext from the obfuscator; and

computing a target value for a respective cohort, wherein the target value includes the obfuscation value.

16. The computer system of claim 15, wherein the plurality of participants are obfuscators of a previous round;

and

wherein a participant, which is not an obfuscator in a cohort, includes a negative obfuscation value in a ciphertext.

17. The computer system of claim 15, wherein the method further comprises:

determining a number of current participants to be less than or equal to a cohort size;

forming a final cohort with the current participants without an obfuscator; and

computing a target value for the final cohort.

18. The computer system of claim 10, wherein computing an encrypted partial value further comprises including a random value in the aggregation.

19. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for facilitating encrypted-domain aggregation of data in a star network, the method comprising:

receiving a set of ciphertexts of an input value from each participant of a plurality of participants via the star network, wherein the set of ciphertexts represents respective encrypted polynomial shares of the input value of that participant, and wherein each ciphertext in the set of ciphertexts is associated with a specific participant in the plurality of participants;

computing an encrypted partial value for each participant by aggregating in the encrypted-domain a respective ciphertext associated with that participant received from the plurality of participants, wherein the encrypted partial value is encrypted based on a public key of that participant;

sending a message comprising the encrypted partial value for each participant to the corresponding participant;

receiving a decrypted partial value representing a decryption of the encrypted partial value from the first participant; and

computing a target value based on a set of decrypted partial values received from a set of participants in the plurality of participants.

20. The storage medium of claim 19, wherein the method further comprises:

dividing the plurality of participants into a number of cohorts;

assigning an obfuscator to a respective cohort, wherein the obfuscator adds an obfuscation value in a ciphertext from the obfuscator; and

computing a target value for a respective cohort, wherein the target value includes the obfuscation value.