Computer-implemented system and method for establishing distributed secret shares in a private data aggregation scheme

• US 9,264,407 B2
• Filed: 04/03/2014
• Issued: 02/16/2016
• Est. Priority Date: 04/03/2014
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Bilogrevic, Igor, Freudiger, Julien, Uzun, Ersin
• Primary Examiner(s): Gee, Jason K
• Application Number:
  US14/244,797
• Publication Number:
  US 20150288662A1
• Time in Patent Office: 684 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 65/403 Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

A probabilistic system and method facilitates the sharing of a secret among participating users in a private way. The secret shares satisfy the condition that their sum equal a predefined number that is chosen by a third party aggregator. Without interacting with any other user, each user computes a secret share according to a predefined probability density function. If enough parties join, their secret shares can be combined by the aggregator with relative efficiency into a secret with a high likelihood of success.

Claims

1. A computer-implemented system for establishing distributed secret shares in a private data aggregation scheme, comprising the steps of:

an aggregator server comprising a processor and memory within which code for execution by the processor is stored, further comprising;

a random generator maintained in the memory and chosen at random from a cyclic group of a set of prime order defined over a range of values of private data; and

a distribution function over the cyclic group and a set of statistical parameters bounding the distribution function, also maintained in the memory;

a plurality of participant computers each comprising a processor and memory within which code for execution by the processor is stored, for each participant computer further comprising;

one of the values of the private data maintained in the memory;

a state initialization module configured in the participant computer to receive the set of prime order, the statistical parameters and the random generator from the aggregator server;

a secret share module configured in the participant computer to create a secret share by a probabilistic random sampling of the distribution function bounded by the statistical parameters; and

an encryption module configured in the participant computer to encrypt the private data value held by the participant computer into encrypted data using the participant computer'"'"'s secret share;

the aggregator server further comprising;

an aggregation module configured in the aggregator server to combine the encrypted data of each participant computer into an encrypted aggregate using the aggregator'"'"'s secret share; and

a decryption module configured in the aggregator server to find a decrypted aggregate.

2. A system according to claim 1, further comprising:

the aggregator server further comprising;

a range of values within which the decrypted aggregate is expected to be, the expected range comprises [m, M], where 0<

m<

M<

<

μ and

μ

is a mean of the distribution function,

wherein the decryption module is further configured to repeat the finding of the decrypted aggregate when the decrypted aggregate falls outside the range of values.

3. A system according to claim 2, further comprising:

the aggregator server further comprising;

a secret share module configured to determine the secret share sk₀ for the aggregator upon each repeated finding of the decrypted aggregate in accordance with;

4. A system according to claim 1, further comprising:

the aggregator server further comprising;

the aggregation module further configured in the aggregator server to solve the encrypted aggregate V of the participant computers in accordance with;

5. A system according to claim 1, further comprising:

each participant computer further comprising;

the state initialization module further configured to receive a range of the statistical parameters from the aggregator server;

the secret share module further configured in the participant computer to create a vector comprising a plurality of secret shares for each participant computer, to encrypt the private data value held by the participant computer into a vector containing the encrypted data using each of the plurality of secret shares, and to provide the vector containing the encrypted data to the central authority; and

the aggregator server further comprising;

the decryption module further configured in the aggregator server to provide an entry within the vectors that the participant computers will use for a next encryption attempt when the decrypted aggregate is not initially found.

6. A computer-implemented method for establishing distributed secret shares in a private data aggregation scheme, comprising the steps of:

selecting, through an aggregator server, a random generator chosen at random from a cyclic group of a set of prime order defined over a range of values of private data;

choosing, also through the aggregator server, a distribution function over the cyclic group and a set of statistical parameters bounding the distribution function;

providing the set of prime order, the statistical parameters and the random generator to a plurality of participant computers that each hold one of the values of the private data;

creating a secret share on each participant computer by a probabilistic random sampling of the distribution function bounded by the statistical parameters, and encrypting on each participant computer the private data value held by the participant computer into encrypted data using the participant computer'"'"'s secret share; and

combining, through the aggregator server, the encrypted data of each participant computer into an encrypted aggregate using the aggregator server'"'"'s secret share, and finding a decrypted aggregate,

wherein the steps are performed on a suitably-programmed computer.

7. A method according to claim 6, further comprising the steps of:

setting a range of values within which the decrypted aggregate is expected to be; and

repeating the finding of the decrypted aggregate when the decrypted aggregate falls outside the range of values.

8. A method according to claim 7, wherein the expected range comprises [m, M], where 0<

m<

M<

<

μ and

μ

is a mean of the distribution function.

9. A method according to claim 7, further comprising the step of:

determining the secret share sk₀ for the aggregator server upon each repeated finding of the decrypted aggregate in accordance with;

10. A method according to claim 7, further comprising the step of:

limiting the finding of the decrypted aggregate to a maximum number of repetitions.

11. A method according to claim 10, further comprising the step of:

requiring each participant computer to repeat the creating of a secret share and the encrypting of the one value of the private data held by that participant computer when the maximum number of repetitions is exceeded; and

thereafter, again combining the encrypted data of each participant computer and reattempting the finding of the decrypted aggregate.

12. A method according to claim 6, further comprising the step of:

selecting the statistical parameters from the group comprising mean, standard deviation and variance.

13. A method according to claim 6, further comprising the step of:

solving the secret share of the aggregator as a difference between the set of prime order and product of a number of the participant computers and the mean modulo the set of prime order.

14. A method according to claim 6, further comprising the step of:

temporally tying the hash function to a single time step that is applicable to the encrypting of the one value of the private data held by each participant computer and the combining of the encrypted data of each participant computer.

15. A method according to claim 6, further comprising the step of:

rounding the random sampling to an integer value for use as the secret share of each participant computer.

16. A method according to claim 6, further comprising the step of:

solving the encrypted data c_i of each participant computer i in a group of n users U={u₁, . . . , u_n} in accordance with;

c_i=g^xi·

H(t)^ski

where g represents the random generator, such that gε

, where is the cyclic group of the set of prime order p;

x_i represents the one value of the private data for the participant computer i, such that x_iε

_p;

sk_i represents the secret share for the participant computer x_i, which is an integer element in _p; and

H(t) represents the hash function at time t.

17. A method according to claim 6, further comprising the step of:

appending an homomorphic message authentication code (MAC) m_i created by each participant computer i in a group of n users U={u₁, . . . , u_n} in accordance with;

m_i=MAC(g^xi)

where g represents the random generator, such that gε

, where is the cyclic group of the set of prime order p; and

x_i represents the one value of the private data for the participant computer i, such that x_iε

_p;

sk_i; and

solving an aggregated multiplicatively homomorphic message authentication code in accordance with;

18. A method according to claim 6, further comprising the step of

appending an homomorphic message authentication code (MAC) m_i encrypted by each participant computer i in a group of n users U={u₁, . . . , u_n} using a public key (PK) encryption scheme with multiplicative homomorphism in accordance with:

m_i=Enc_PK[g^xi]

where g represents the random generator, such that gε

, where is the cyclic group of the set of prime order p; and

x_i represents the one value of the private data for the participant computer i, such that x_iε

_p;

sk_i; and

solving an aggregated multiplicatively homomorphic message authentication code in accordance with;

19. A method according to claim 6, further comprising the steps of:

providing a range of the statistical parameters to the participant computers;

creating a vector comprising a plurality of secret shares for each participant computer, and encrypting the private data value held by the participant computer into a vector containing the encrypted data using each of the plurality of secret shares;

providing the vector containing the encrypted data to the central authority; and

when the decrypted aggregate is not initially found by the central authority, providing an entry within the vectors that the participant computers will use for a next encryption attempt.

20. A method according to claim 6, further comprising the steps of:

providing a request to use a series of the secret shares to the participant computers;

encrypting the private data value held by the participant computer into a vector containing the encrypted data using each of the plurality of secret shares in the series;

providing the vector containing the encrypted data to the central authority; and

when the decrypted aggregate is not initially found by the central authority, providing an entry within the series of the secret shares that the participant computers will use for a next encryption attempt.

21. A method according to claim 6, wherein the distribution function comprises a Gaussian distribution.

22. A non-transitory computer readable storage medium storing code for executing on a computer system to perform the method according to claim 6.