Granted Patent B2

US 12,386,985 · App. 18/368,811 · Granted Aug 12, 2025

Inventor: Matthew Tran Clegg (Los Angeles, CA)

Assignee: Google LLC

G06F21/606

Abstract

Claims (62)

1. A method, comprising:

receiving, by a controller comprising one or more data processing apparatus and from a content distributor, plan data specifying a set of distribution plans that cause distribution of content with electronic documents from multiple online publishers;

transmitting, by the controller, instructions for each given publisher among the multiple online publishers to submit secret shares of each register of a multi-register sketch representing presentations of the content at an electronic document provided by the given online publisher, wherein multiple secret shares for a given register is required to recover a value of the given register;

transmitting, by the controller and to a plurality of multi-party computation (MPC) devices, a notification that the content distributor has requested an analysis of the presentations of the content distributed according to the set of distribution plans;

receiving, by the controller and from each given MPC device among the plurality of MPC devices, a result share of the analysis of the presentation of the content distributed according to the set of distribution plans, wherein multiple result shares generated by the plurality of MPC devices are required to recover a final result of the analysis of the presentation of the content distributed according to the set of distribution plans;

transmitting, by the controller and to the content distributor, a set of result shares received from the plurality of MPC devices.

2. The method of claim 1 , further comprising:

receiving, by the plurality of MPC devices and from each given online publisher among the multiple online publishers, the secret shares of each register of the multi-register sketch representing the presentations of the content at the electronic document provided by the given publisher;

computing, by the plurality of MPC devices and using the secret shares, a non-zero register count for each multi-register sketch received from the multiple online publishers without revealing individual values of registers in the multi-register sketch; and

adding, by the plurality of MPC devices, random noise to the non-zero register count to obtain noisy result shares; and

transmitting, by the plurality of MPC devices, the noisy result shares to the controller.

3. The method of claim 2 , wherein computing the non-zero register count for each multi-register sketch comprises computing a number of bits having a value of 1 in a union of multiple multi-register sketches received from the multiple online publishers.

4. The method of claim 3 , further comprising:

receiving, from the multiple online publishers, different bit strings; and

performing a Boolean exclusive-or (XOR) on the different bit strings to obtain an output bit stream that is unknown to any of the multiple online publishers.

5. The method of claim 4 , further comprising determining the random noise based, at least in part, on the output bit stream.

6. The method of claim 5 , wherein determining the random noise comprises:

converting the output bit stream into a one-hot vector having a specified bit length; and

computing a dot product of the one-hot vector and a quantile vector of the specified bit length, wherein the quantile vector represents quantiles of a discrete Gaussian distribution.

7. The method of claim 6 , further comprising computing a frequency vector representing, for each number of presentations between one and a specified number, how many different users were presented content distributed according to the set of distribution plans different numbers of times between one and the specified number.

8. A non-transitory computer readable medium storing instructions that, upon execution by one or more data processing apparatus, cause the one or more data processing apparatus to perform operations comprising:

receiving, from a content distributor, plan data specifying a set of distribution plans that cause distribution of content with electronic documents from multiple online publishers;

transmitting instructions for each given publisher among the multiple online publishers to submit secret shares of each register of a multi-register sketch representing presentations of the content at an electronic document provided by the given online publisher, wherein multiple secret shares for a given register is required to recover a value of the given register;

transmitting, to a plurality of multi-party computation (MPC) devices, a notification that the content distributor has requested an analysis of the presentations of the content distributed according to the set of distribution plans;

receiving, from each given MPC device among the plurality of MPC devices, a result share of the analysis of the presentation of the content distributed according to the set of distribution plans, wherein multiple result shares generated by the plurality of MPC devices are required to recover a final result of the analysis of the presentation of the content distributed according to the set of distribution plans;

transmitting, by the controller and to the content distributor, a set of result shares received from the plurality of MPC devices.

9. The non-transitory computer readable medium of claim 8 , wherein the instructions cause the one or more data processing apparatus to cause operations comprising:

receiving, by the plurality of MPC devices and from each given online publisher among the multiple online publishers, the secret shares of each register of the multi-register sketch representing the presentations of the content at the electronic document provided by the given publisher;

computing, by the plurality of MPC devices and using the secret shares, a non-zero register count for each multi-register sketch received from the multiple online publishers without revealing individual values of registers in the multi-register sketch; and

adding, by the plurality of MPC devices, random noise to the non-zero register count to obtain noisy result shares; and

transmitting, by the plurality of MPC devices, the noisy result shares to the controller.

10. The non-transitory computer readable medium of claim 9 , wherein computing the non-zero register count for each multi-register sketch comprises computing a number of bits having a value of 1 in a union of multiple multi-register sketches received from the multiple online publishers.

11. The non-transitory computer readable medium of claim 10 , wherein the instructions cause the one or more data processing apparatus to perform operations comprising:

receiving, from the multiple online publishers, different bit strings; and

performing a Boolean exclusive-or (XOR) on the different bit strings to obtain an output bit stream that is unknown to any of the multiple online publishers.

12. The non-transitory computer readable medium of claim 11 , wherein the instructions cause the one or more data processing apparatus to perform operations comprising determining the random noise based, at least in part, on the output bit stream.

13. The non-transitory computer readable medium of claim 12 , wherein determining the random noise comprises:

converting the output bit stream into a one-hot vector having a specified bit length; and

computing a dot product of the one-hot vector and a quantile vector of the specified bit length, wherein the quantile vector represents quantiles of a discrete Gaussian distribution.

14. The non-transitory computer readable medium of claim 6 , wherein the instructions cause the one or more data processing apparatus to perform operations comprising computing a frequency vector representing, for each number of presentations between one and a specified number, how many different users were presented content distributed according to the set of distribution plans different numbers of times between one and the specified number.

15. A system, comprising:

one or more memory devices; and

a controller, including one or more data processing apparatus, configured to access the one or more memory devices and execute instructions that cause the one or more data processing apparatus to perform operations comprising:

receiving, by the controller comprising one or more data processing apparatus and from a content distributor, plan data specifying a set of distribution plans that cause distribution of content with electronic documents from multiple online publishers;

transmitting, by the controller, instructions for each given publisher among the multiple online publishers to submit secret shares of each register of a multi-register sketch representing presentations of the content at an electronic document provided by the given online publisher, wherein multiple secret shares for a given register is required to recover a value of the given register;

transmitting, by the controller and to a plurality of multi-party computation (MPC) devices, a notification that the content distributor has requested an analysis of the presentations of the content distributed according to the set of distribution plans;

receiving, by the controller and from each given MPC device among the plurality of MPC devices, a result share of the analysis of the presentation of the content distributed according to the set of distribution plans, wherein multiple result shares generated by the plurality of MPC devices are required to recover a final result of the analysis of the presentation of the content distributed according to the set of distribution plans;

transmitting, by the controller and to the content distributor, a set of result shares received from the plurality of MPC devices.

16. The system of claim 15 , further comprising:

the plurality of MPC devices configured to perform operations comprising:

receiving, by the plurality of MPC devices and from each given online publisher among the multiple online publishers, the secret shares of each register of the multi-register sketch representing the presentations of the content at the electronic document provided by the given publisher;

computing, by the plurality of MPC devices and using the secret shares, a non-zero register count for each multi-register sketch received from the multiple online publishers without revealing individual values of registers in the multi-register sketch; and

adding, by the plurality of MPC devices, random noise to the non-zero register count to obtain noisy result shares; and

transmitting, by the plurality of MPC devices, the noisy result shares to the controller.

17. The system of claim 16 , wherein computing the non-zero register count for each multi-register sketch comprises computing a number of bits having a value of 1 in a union of multiple multi-register sketches received from the multiple online publishers.

18. The system of claim 17 , wherein the plurality of MPC devices are configured to perform operations comprising:

receiving, from the multiple online publishers, different bit strings; and

performing a Boolean exclusive-or (XOR) on the different bit strings to obtain an output bit stream that is unknown to any of the multiple online publishers.

19. The system of claim 18 , wherein the plurality of MPC devices are configured to perform operations comprising determining the random noise based, at least in part, on the output bit stream.

20. The system of claim 19 , wherein determining the random noise comprises:

converting the output bit stream into a one-hot vector having a specified bit length; and

computing a dot product of the one-hot vector and a quantile vector of the specified bit length, wherein the quantile vector represents quantiles of a discrete Gaussian distribution.

Assignments (1)

Continuity (2)

References Cited (27)