Granted Patent B2

US 10,069,631 · App. 15/073,330 · Granted Sep 4, 2018

Inventors: Shantanu Rane (Menlo Park, CA); Alejandro E. Brito (Mountain View, CA); Ersin Uzun (Campbell, CA)

Assignee: PALO ALTO RESEARCH CENTER INCORPORATED

H04L9/30G06F21/6218H04L9/008H04L9/085H04L2209/46

Abstract

Claims (65)

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.

Assignments (9)

Continuity (1)