Pure differentially private algorithms for summation in the shuffled model

A computer-implemented method to enable privacy-preserving aggregation of private data, the method comprising:

• obtaining, by one or more computing devices, private data comprising a private vector, the private vector comprising an ordered plurality of private values;
• producing, by the one or more computing devices, an ordered plurality of multisets respective to the ordered plurality of private values, each of the ordered plurality of multisets respectively comprising a plurality of multiset values, wherein, for each of the ordered plurality of multisets, the method comprises:
• determining, by the one or more computing devices, a probabilistic status defining one of a first condition and a second condition;
• in response to the probabilistic status having the first condition, the plurality of multiset values is based at least in part on the private value;
• and
• in response to the probabilistic status having the second condition, the plurality of multiset values comprises a noise message;
• wherein the noise message is produced based at least in part on a noise distribution that comprises a discretization of a continuous unimodal distribution supported on a range from zero to a number of multiset values included in the plurality of multiset values;
• wherein the noise message comprises a plurality of one values and a plurality of zero values;
• wherein an amount of the plurality of one values is equivalent to a randomizer value sampled from the noise distribution and an amount of the plurality of zero values is equivalent to the randomizer value subtracted from the number of multiset values included in the plurality of multiset values;
• and
• providing, by the one or more computing devices, the plurality of ordered multisets for ordered aggregation with an ordered plurality of additional multisets respectively generated for a plurality of additional private vectors.

A computing system configured for privacy-preserving aggregation of private data, the computing system comprising:

• one or more processors;
• and
• one or more memory devices storing computer-readable instructions that, when implemented, cause the one or more processors to perform operations for privacy-preserving aggregation of private data, the operations comprising:
• obtaining private data comprising a private value;
• determining a probabilistic status defining one of a first condition and a second condition;
• producing a multiset comprising a plurality of multiset values, wherein:
• in response to the probabilistic status having the first condition, the plurality of multiset values is based at least in part on the private value;
• and
• in response to the probabilistic status having the second condition, the plurality of multiset values comprises a noise message;
• wherein the noise message is produced based at least in part on a noise distribution that comprises a discretization of a continuous unimodal distribution supported on a range from zero to a number of multiset values included in the plurality of multiset values;
• wherein the noise message comprises a plurality of one values and a plurality of zero values;
• wherein an amount of the plurality of one values is equivalent to a randomizer value sampled from the noise distribution and an amount of the plurality of zero values is equivalent to the randomizer value subtracted from the number of multiset values included in the plurality of multiset values;
• and
• providing the multiset for aggregation with a plurality of additional multisets respectively generated for a plurality of additional private values.