# US 2021/0243171 A1 · Pure Differentially Private Algorithms for Summation in the Shuffled Model > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0243171 A1 - Document ID: US20210243171A1 - Status: Published application - Kind: A1 - Application number: 17/122,638 - Filed: 2020-12-15 - Published: 2021-08-05 - Earliest claimed: 2020-02-05 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Badih Ghazi; Noah Zeger Golowich; Shanmugasundaram Ravikumar; Pasin Manurangsi; Ameya Avinash Velingker; Rasmus Pagh - Web page: https://patentgrep.com/patent/US20210243171A1 ## CPC - H04L 63/0421: {Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer} - H04L 63/0428: {wherein the data content is protected, e.g. by encrypting or encapsulating the payload} - G06N 5/04: Inference or reasoning models - G06N 20/00: Machine learning - G06N 3/084: Backpropagation, e.g. using gradient descent - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract An encoding method for enabling privacy-preserving aggregation of private data can include obtaining private data including a private value, determining a probabilistic status defining one of a first condition and a second condition, producing a multiset including a 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. 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 is a noise message. 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. ## Claims ### Claim 1 A computer-implemented method for privacy-preserving aggregation of private data, the method comprising: obtaining, by one or more computing devices, private data comprising a private value; determining, by the one or more computing devices, a probabilistic status defining one of a first condition and a second condition; producing, by the one or more computing devices, 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; and providing, by the one or more computing devices, the multiset for aggregation with a plurality of additional multisets respectively generated for a plurality of additional private values. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein: determining, by the one or more computing devices, the probabilistic status defining one of the first condition and the second condition comprises sampling a first probability distribution to receive a first value or a second value, wherein the first condition comprises receipt of the first value and the second condition comprises receipt of the second value; and producing, by the one or more computing devices, the multiset comprising a plurality of multiset values comprises: in the first condition wherein the first value is received, producing the multiset wherein the plurality of multiset values is based at least in part on the private value; and in the second condition wherein the second value is received: sampling the noise distribution to receive a randomizer value; and producing the multiset wherein the plurality of multiset values comprises the noise message, wherein the noise message is based at least in part on the randomizer value. ### Claim 3 (depends on 2) The computer-implemented method of claim 2, wherein the first probability distribution is a Bernoulli distribution. ### Claim 4 (depends on 2) The computer-implemented method of claim 2, wherein the noise distribution is within a multiplicative factor of an underlying distribution of the private data. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein the noise distribution is a truncated discrete Laplacian distribution. ### Claim 6 (depends on 7) The computer-implemented method of claim 7, wherein the plurality of multiset values based at least in part on the private value comprises an amount of zero values greater by one than an amount of one values if the private value equals zero and an amount of one values fewer by one than an amount of zero values if the private value equals one. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, 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. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, wherein providing, by the one or more computing devices, the multiset for aggregation comprises transmitting, by the one or more computing devices, the multiset to a shuffler model configured to shuffle the multiset with the plurality of additional multisets. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, wherein providing, by the one or more computing devices, the multiset for aggregation comprises adding half of a total amount of the plurality of additional multisets to the sum of the plurality of multiset values. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, wherein providing, by the one or more computing devices, the multiset for aggregation further comprises debiasing each of the plurality of multiset values. ### Claim 11 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; 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. ### Claim 12 (depends on 11) The computer-implemented method of claim 11, wherein: determining, by the one or more computing devices, the probabilistic status defining one of the first condition and the second condition comprises sampling a first probability distribution to receive a first value or a second value, wherein the first condition comprises receipt of the first value and the second condition comprises receipt of the second value; and in the first condition wherein the first value is received, producing the multiset wherein the plurality of multiset values is based at least in part on the private value; and in the second condition wherein the second value is received: sampling the noise distribution to receive a randomizer value; and producing the multiset wherein the plurality of multiset values comprises the noise message, wherein the noise message is based at least in part on the randomizer value. ### Claim 13 (depends on 11) The computer-implemented method of claim 11, wherein the first probability distribution is a Bernoulli distribution. ### Claim 14 (depends on 11) The computer-implemented method of claim 11, wherein the noise distribution is within a multiplicative factor of an underlying distribution of the private data. ### Claim 15 (depends on 11) The computer-implemented method of claim 11, wherein the noise distribution is a truncated discrete Laplacian distribution. ### Claim 16 (depends on 11) The computer-implemented method of claim 11, wherein the plurality of multiset values based at least in part on the private value comprises an amount of zero values greater by one than an amount of one values if the private value equals zero and an amount of one values fewer by one than an amount of zero values if the private value equals one. ### Claim 17 (depends on 11) The computer-implemented method of claim 11, 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. ### Claim 18 (depends on 11) The computer-implemented method of claim 11, wherein providing, by the one or more computing devices, the ordered plurality of multisets for ordered aggregation comprises transmitting, by the one or more computing devices, the ordered plurality of multisets to a shuffler model configured to shuffle the ordered plurality of multisets with the ordered plurality of additional multisets while maintaining an order of the ordered plurality of multisets and the ordered plurality of additional multisets. ### Claim 19 (depends on 11) The computer-implemented method of claim 11, further comprising: generating a plurality of respective sums for each multiset in the ordered plurality of multisets, each of the plurality of respective sums comprising a sum of the plurality of multiset values from a respective multiset; and providing a combinatorial sum of the respective sums for each of the plurality of private values, the combinatorial sum recombining the respective sums with respect to an order of the ordered plurality of multisets and the ordered plurality of additional multisets. ### Claim 20 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; and providing the multiset for aggregation with a plurality of additional multisets respectively generated for a plurality of additional private values.