Granted Patent B2

US 12,192,342 · App. 17/916,871 · Granted Jan 7, 2025

Inventors: Gang Wang (Frederick, MD); Sarvar Patel (Montville, NJ); Marcel M. Moti Yung (New York, NY); Karn Seth (New York, NY); Kevin Wei Li Yeo (New York City, NY); Benjamin Kreuter (Jersey City, NJ); Mariana Raykova (New York City, NY); Tancrède Lepoint (New York, NY)

Assignee: Google LLC

H04L9/085H04L2209/466

Abstract

Claims (55)

1. A computer-implemented method comprising:

receiving, by a first computing system of a secure multi-party computation (MPC) system and from a client device, a digital component request and a nonce;

generating, based on the nonce and a function, an array comprising a share of a Bloom filter representing user group identifiers for user groups that include a user of the client device as a member;

for each of a plurality of user group identifiers, calculating, in collaboration with one or more second computing systems of the secure MPC system and using the array, a respective first secret share of one or more user group membership condition parameters representing whether the user of the client device is a member of a user group identified by the user group identifier;

for each digital component of a plurality of digital components:

identifying a given user group identifier corresponding to the digital component; and

calculating, in collaboration with each of the one or more second computing systems, a first secret share of a candidate parameter based at least on the respective first secret share of each user group membership condition parameter corresponding to a given user group identified by the given user group identifier and a second secret share of the user group membership condition parameter corresponding to a given user group identified by the given user group identifier held by each of the one or more second computing systems, wherein the candidate parameter indicates whether the digital component is an eligible candidate for the digital component request;

generating, based on the first secret share of the candidate parameter for each digital component and a selection value for each digital component, a first secret share of a selection result representing a selected digital component; and

sending the first secret share of the selection result to the client device.

2. The computer-implemented method of claim 1 , wherein calculating, in collaboration with the one or more second computing systems, the first secret share of the user group membership condition parameter comprises calculating the first secret share of the user group membership condition parameter using one of a garbled circuit protocol or a Goldreich-Micali-Wigderson (GMW) protocol.

3. The computer-implemented method of claim 1 , wherein calculating, in collaboration with each of the one or more second computing systems, the first secret share of the candidate parameter comprises calculating the first secret share of the candidate parameter based on respective secret shares of parameters for one or more additional conditions.

4. The computer-implemented method of claim 1 , further comprising:

receiving an additional nonce for an additional Bloom filter representing a set of blocked digital components;

generating an additional array representing a share of the additional Bloom filter; and

for one or more digital components of the plurality of digital components, calculating, in collaboration with the one or more second computing systems and using the additional array, a first secret share of a blocked condition parameter representing whether the digital component is blocked at the client device, wherein the candidate parameter for the digital component is based on the blocked condition parameter.

5. The computer-implemented method of claim 1 , wherein the first secret share of the selection result comprises a result calculated by performing a bitwise-XOR operation between a secret share of the selection result and a second mask received from the client device.

6. The computer-implemented method of claim 1 , wherein the first computing system comprises a serving pool comprising a set of processors and a load balancer that balances a computing load among the set of processors.

7. The computer-implemented method of claim 6 , wherein the first computing system comprises a log processor pool comprising an additional set of processors that generate snapshots based on updates to logs comprising data related to completed digital component selection processes and provide the snapshots to the serving pool.

8. A system comprising:

one or more processors of a first computing system; and

one or more non-transitory storage devices storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising:

receiving, by the first computing system of a secure multi-party computation (MPC) system and from a client device, a digital component request and a nonce;

generating, based on the nonce and a function, an array comprising a share of a Bloom filter representing user group identifiers for user groups that include a user of the client device as a member;

for each of a plurality of user group identifiers, calculating, in collaboration with one or more second computing systems of the secure MPC system and using the array, a respective first secret share of one or more user group membership condition parameters representing whether the user of the client device is a member of a user group identified by the user group identifier;

for each digital component of a plurality of digital components:

identifying a given user group identifier corresponding to the digital component; and

calculating, in collaboration with each of the one or more second computing systems, a first secret share of a candidate parameter based at least on the respective first secret share of each user group membership condition parameter corresponding to a given user group identified by the given user group identifier and a second secret share of the user group membership condition parameter corresponding to a given user group identified by the given user group identifier held by each of the one or more second computing systems, wherein the candidate parameter indicates whether the digital component is an eligible candidate for the digital component request;

generating, based on the first secret share of the candidate parameter for each digital component and a selection value for each digital component, a first secret share of a selection result representing a selected digital component; and

sending the first secret share of the selection result to the client device.

9. The system of claim 8 , wherein calculating, in collaboration with the one or more second computing systems, the first secret share of the user group membership condition parameter comprises calculating the first secret share of the user group membership condition parameter using one of a garbled circuit protocol or a Goldreich-Micali-Wigderson (GMW) protocol.

10. The system of claim 8 , wherein calculating, in collaboration with each of the one or more second computing systems, the first secret share of the candidate parameter comprises calculating the first secret share of the candidate parameter based on respective secret shares of parameters for one or more additional conditions.

11. The system of claim 8 , wherein the operations comprise:

receiving an additional nonce for an additional Bloom filter representing a set of blocked digital components;

generating an additional array representing a share of the additional Bloom filter; and

for one or more digital components of the plurality of digital components, calculating, in collaboration with the one or more second computing systems and using the additional array, a first secret share of a blocked condition parameter representing whether the digital component is blocked at the client device, wherein the candidate parameter for the digital component is based on the blocked condition parameter.

12. The system of claim 8 , wherein the first secret share of the selection result comprises a result calculated by performing a bitwise-XOR operation between a secret share of the selection result and a second mask received from the client device.

13. The system of claim 8 , wherein the first computing system comprises a serving pool comprising a set of processors and a load balancer that balances a computing load among the set of processors.

14. The system of claim 13 , wherein the first computing system comprises a log processor pool comprising an additional set of processors that generate snapshots based on updates to logs comprising data related to completed digital component selection processes and provide the snapshots to the serving pool.

15. A non-transitory computer readable storage medium carrying instructions that, when executed by one or more processors of a first computing system, cause the one or more processors to perform operations comprising:

receiving, by a first computing system of a secure multi-party computation (MPC) system and from a client device, a digital component request and a nonce;

generating, based on the nonce and a function, an array comprising a share of a Bloom filter representing user group identifiers for user groups that include a user of the client device as a member;

for each of a plurality of user group identifiers, calculating, in collaboration with one or more second computing systems of the secure MPC system and using the array, a respective first secret share of one or more user group membership condition parameters representing whether the user of the client device is a member of a user group identified by the user group identifier;

for each digital component of a plurality of digital components:

identifying a given user group identifier corresponding to the digital component; and

calculating, in collaboration with each of the one or more second computing systems, a first secret share of a candidate parameter based at least on the respective first secret share of each user group membership condition parameter corresponding to a given user group identified by the given user group identifier and a second secret share of the user group membership condition parameter corresponding to a given user group identified by the given user group identifier held by each of the one or more second computing systems, wherein the candidate parameter indicates whether the digital component is an eligible candidate for the digital component request;

generating, based on the first secret share of the candidate parameter for each digital component and a selection value for each digital component, a first secret share of a selection result representing a selected digital component; and

sending the first secret share of the selection result to the client device.

16. The non-transitory computer readable storage medium of claim 15 , wherein calculating, in collaboration with the one or more second computing systems, the first secret share of the user group membership condition parameter comprises calculating the first secret share of the user group membership condition parameter using one of a garbled circuit protocol or a Goldreich-Micali-Wigderson (GMW) protocol.

17. The non-transitory computer readable storage medium of claim 15 , wherein calculating, in collaboration with each of the one or more second computing systems, the first secret share of the candidate parameter comprises calculating the first secret share of the candidate parameter based on respective secret shares of parameters for one or more additional conditions.

18. The non-transitory computer readable storage medium of claim 15 , wherein the operations comprise:

receiving an additional nonce for an additional Bloom filter representing a set of blocked digital components;

generating an additional array representing a share of the additional Bloom filter; and

for one or more digital components of the plurality of digital components, calculating, in collaboration with the one or more second computing systems and using the additional array, a first secret share of a blocked condition parameter representing whether the digital component is blocked at the client device, wherein the candidate parameter for the digital component is based on the blocked condition parameter.

19. The non-transitory computer readable storage medium of claim 15 , wherein the first secret share of the selection result comprises a result calculated by performing a bitwise-XOR operation between a secret share of the selection result and a second mask received from the client device.

20. The non-transitory computer readable storage medium of claim 15 , wherein the first computing system comprises a serving pool comprising a set of processors and a load balancer that balances a computing load among the set of processors.

Assignments (1)

Priority Claims (1)

Continuity (1)

References Cited (43)