Fault-tolerant aggregation of encrypted data in a star network

• US 10,069,631 B2
• Filed: 03/17/2016
• Issued: 09/04/2018
• 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
• Primary Examiner(s): Bayou, Yonas A
• Application Number:
  US15/073,330
• Publication Number:
  US 20170272246A1
• Time in Patent Office: 901 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 of physical devices, the method comprising:

receiving, by a computing device comprising a microprocessor, a set of ciphertexts of an input value from each participant of a plurality of participants via the star network, wherein a respective participant in the plurality of participants comprises a microprocessor, wherein the set of ciphertexts from a first participant of a plurality of participants represents respective encrypted polynomial shares of the input value of the first 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 the first participant by aggregating in the encrypted-domain a respective ciphertext associated with the first participant received from the plurality of participants, wherein the encrypted partial value is encrypted based on a public key of the first 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 subset of the set of decrypted partial values, wherein the subset corresponds to a subset of participants of the plurality of participants;

wherein computing the target value further comprises;

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

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

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

3. The method of claim 1, wherein the aggregation of a respective ciphertext associated with the first 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 encrypted polynomial share at the first participant is computing using a modulo value using the large prime number.

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

determining whether the number of participants in the set of participants is greater than the threshold, wherein the threshold is based on a degree of the polynomial.

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 the 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 of physical devices, the system comprising:

processing circuitry; and

a storage device storing instructions that when executed by the processing circuitry cause the processing circuitry 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 a respective participant in the plurality of participants comprises a microprocessor, wherein the set of ciphertexts from a first participant of a plurality of participants represents respective encrypted polynomial shares of the input value of the first 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 the first participant by aggregating in the encrypted-domain a respective ciphertext associated with the first participant received from the plurality of participants, wherein the encrypted partial value is encrypted based on a public key of the first 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 subset of the set of decrypted partial values, wherein the subset corresponds to a subset of participants of the plurality of participants;

wherein computing the target value further comprises;

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

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

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

12. The computer system of claim 10, wherein the aggregation of a respective ciphertext associated with the first 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 encrypted polynomial share at the first participant is computed using a modulo value using the large prime number.

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

determining whether the number of participants in the set of participants is greater than the threshold, wherein the threshold is based on a degree of the polynomial.

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 the 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, which includes a microprocessor, cause the computer to perform a method for facilitating encrypted-domain aggregation of data in a star network of physical devices, 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 a respective participant in the plurality of participants comprises a microprocessor, wherein the set of ciphertexts from a first participant of a plurality of participants represents respective encrypted polynomial shares of the input value of the first 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 the first participant by aggregating in the encrypted-domain a respective ciphertext associated with the first participant received from the plurality of participants, wherein the encrypted partial value is encrypted based on a public key of the first 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 subset of the set of decrypted partial values, wherein the subset corresponds to a subset of participants of the plurality of participants; and

wherein computing the target value further comprises;

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

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

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.