Computer-Implemented System And Method For Establishing Distributed Secret Shares In A Private Data Aggregation Scheme
First Claim
Patent Images
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 generator maintained in the memory and chosen at random from a cyclic group of a set 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 participants each comprising a processor and memory within which code for execution by the processor is stored, for each participant further comprising;
one of the values of the private data maintained in the memory;
a state initialization module configured to receive the set prime order, the statistical parameters and the random generator from the aggregator server;
a secret share module configured to create a secret share by a probabilistic random sampling of the distribution function bounded by the statistical parameters; and
an encryption module configured to encrypt the private data value held by the participant into encrypted data using the participant'"'"'s secret share;
the aggregator server further comprising;
an aggregation module configured to combine the encrypted data of each participant into an encrypted aggregate using the aggregator'"'"'s secret share; and
a decryption module configured to find a decrypted aggregate.
6 Assignments
0 Petitions
Accused Products
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.
19 Citations
22 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 generator maintained in the memory and chosen at random from a cyclic group of a set 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 participants each comprising a processor and memory within which code for execution by the processor is stored, for each participant further comprising; one of the values of the private data maintained in the memory; a state initialization module configured to receive the set prime order, the statistical parameters and the random generator from the aggregator server; a secret share module configured to create a secret share by a probabilistic random sampling of the distribution function bounded by the statistical parameters; and an encryption module configured to encrypt the private data value held by the participant into encrypted data using the participant'"'"'s secret share; the aggregator server further comprising; an aggregation module configured to combine the encrypted data of each participant into an encrypted aggregate using the aggregator'"'"'s secret share; and a decryption module configured to find a decrypted aggregate. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A computer-implemented method for establishing distributed secret shares in a private data aggregation scheme, comprising the steps of:
-
selecting, through an aggregator, a generator chosen at random from a cyclic group of a set prime order defined over a range of values of private data; choosing, also through the aggregator, a distribution function over the cyclic group and a set of statistical parameters bounding the distribution function; providing the set prime order, the statistical parameters and the generator to a plurality of participants that each hold one of the values of the private data; creating a secret share for each participant by a probabilistic random sampling of the distribution function bounded by the statistical parameters, and encrypting the private data value held by the participant into encrypted data using the participant'"'"'s secret share; and combining, through the aggregator, the encrypted data of each participant into an encrypted aggregate using the aggregator'"'"'s secret share; and
finding a decrypted aggregate,wherein the steps are performed on a suitably-programmed computer. - View Dependent Claims (7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
Specification