Using secure multi-party computation and probabilistic data structures to protect access to information
This document describes systems and techniques for protecting the security of information in content selection and distribution. In one aspect, a method includes receiving, by a first computing system of MPC systems, a digital component request including distributed point functions that represent a secret share of a respective point function that indicates whether a user of the client device is a member of a first user group. Selection values are identified. Each selection value corresponds to a respective digital component, a set of contextual signals, and a respective second user group identifier for a respective second user group to which the respective digital component is eligible to be distributed. A determination is made, for each selection value and using the distributed point functions in a secure MPC process, a candidate parameter that indicates whether the second user group identifier matches a user group that includes the user as a member.
1. A computer-implemented method comprising:
receiving, from a client device and by a first computing system of a plurality of multi-party computation (MPC) systems, a digital component request comprising distributed point functions that each represent a secret share of a respective point function that indicates whether a user of the client device is a member of a respective first user group identified by a respective first user group identifier;
identifying a plurality of selection values, wherein each selection value corresponds to a respective digital component, a set of contextual signals, and a respective second user group identifier for a respective second user group to which the respective digital component is eligible to be distributed;
determining, for each selection value and using the distributed point functions in a secure MPC process performed in collaboration with one or more second computing systems of the plurality of MPC systems, a candidate parameter that indicates whether the second user group identifier corresponding to the selection value matches a user group that includes the user as a member;
generating, based on the selection values and the candidate parameters, a first secret share of a selection result that identifies, from a plurality of candidate digital components, a given digital component having a highest selection value, wherein each candidate digital component is a digital component for which the candidate parameter for the selection value corresponding to the digital component indicates that the second user group identifier corresponding to the selection value matches a user group that includes the user as a member; and
transmitting, to the client device, the first secret share of a selection result identifying the given digital component.
2. The computer-implemented method of claim 1 , wherein determining the candidate parameter for each selection value comprises determining a first secret share of the candidate parameter for each selection value.
3. The computer-implemented method of claim 1 , wherein generating the first secret share of the selection result comprises:
generating an order of the selection values based on a magnitude of each selection value;
determining, based on the order of the selection values and the candidate parameter for each selection value, a first secret share of an accumulated value for each selection value, wherein the accumulated value for each selection value indicates a position of the selection value in the order of the selection values;
determining, for each selection value, a first secret share of a winner parameter based on (i) the candidate parameter for the selection value and (ii) a result of an equality test that indicates whether the accumulated value for the selection value is a specified value; and
determining, as the first secret share of the selection result, a first secret share of a sum of, for each selection value, a product of the winner parameter for the selection value and a digital component information element for the selection value.
4. The computer-implemented method of claim 3 , wherein determining the first secret share of the accumulated value for each selection value comprises:
for each individual selection value, determining a quantity of selection values, between a highest selection value and the individual selection value, that have a candidate parameter that indicates that the second user group identifier corresponding to the selection value matches at least one of the one or more first user group identifiers.
5. The computer-implemented method of claim 3 , wherein the specified value is one or logical true.
6. The computer-implemented method of claim 1 , wherein the distributed point functions are generated based on a plurality of user groups that include the user of the client device as a member.
7. The computer-implemented method of claim 1 , wherein:
the digital component request comprises a user group request key that is based on a set of contextual signals for a digital component slot; and
identifying the plurality of selection values comprises identifying, in a data structure, each selection value that has a lookup key that matches the user group request key.
8. A system, comprising:
a first computing system comprising one or more processors; and
one or more computer-readable media storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising:
receiving, from a client device and by the first computing system of a plurality of multi-party computation (MPC) systems, a digital component request comprising distributed point functions that each represent a secret share of a respective point function that indicates whether a user of the client device is a member of a respective first user group identified by a respective first user group identifier;
identifying a plurality of selection values, wherein each selection value corresponds to a respective digital component, a set of contextual signals, and a respective second user group identifier for a respective second user group to which the respective digital component is eligible to be distributed;
determining, for each selection value and using the distributed point functions in a secure MPC process performed in collaboration with one or more second computing systems of the plurality of MPC systems, a candidate parameter that indicates whether the second user group identifier corresponding to the selection value matches a user group that includes the user as a member;
generating, based on the selection values and the candidate parameters, a first secret share of a selection result that identifies, from a plurality of candidate digital components, a given digital component having a highest selection value, wherein each candidate digital component is a digital component for which the candidate parameter for the selection value corresponding to the digital component indicates that the second user group identifier corresponding to the selection value matches a user group that includes the user as a member; and
transmitting, to the client device, the first secret share of a selection result identifying the given digital component.
9. The system of claim 8 , wherein determining the candidate parameter for each selection value comprises determining a first secret share of the candidate parameter for each selection value.
10. The system of claim 8 , wherein generating the first secret share of the selection result comprises:
generating an order of the selection values based on a magnitude of each selection value;
determining, based on the order of the selection values and the candidate parameter for each selection value, a first secret share of an accumulated value for each selection value, wherein the accumulated value for each selection value indicates a position of the selection value in the order of the selection values;
determining, for each selection value, a first secret share of a winner parameter based on (i) the candidate parameter for the selection value and (ii) a result of an equality test that indicates whether the accumulated value for the selection value is a specified value; and
determining, as the first secret share of the selection result, a first secret share of a sum of, for each selection value, a product of the winner parameter for the selection value and a digital component information element for the selection value.
11. The system of claim 10 , wherein determining the first secret share of the accumulated value for each selection value comprises:
for each individual selection value, determining a quantity of selection values, between a highest selection value and the individual selection value, that have a candidate parameter that indicates that the second user group identifier corresponding to the selection value matches at least one of the one or more first user group identifiers.
12. The system of claim 11 , wherein the specified value is one or logical true.
13. The system of claim 8 , wherein the distributed point functions are generated based on a plurality of user groups that include the user of the client device as a member.
14. The system of claim 8 , wherein:
the digital component request comprises a user group request key that is based on a set of contextual signals for a digital component slot; and
identifying the plurality of selection values comprises identifying, in a data structure, each selection value that has a lookup key that matches the user group request key.
15. One or more non-transitory computer-readable media storing 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, from a client device and by the first computing system of a plurality of multi-party computation (MPC) systems, a digital component request comprising distributed point functions that each represent a secret share of a respective point function that indicates whether a user of the client device is a member of a respective first user group identified by a respective first user group identifier;
identifying a plurality of selection values, wherein each selection value corresponds to a respective digital component, a set of contextual signals, and a respective second user group identifier for a respective second user group to which the respective digital component is eligible to be distributed;
determining, for each selection value and using the distributed point functions in a secure MPC process performed in collaboration with one or more second computing systems of the plurality of MPC systems, a candidate parameter that indicates whether the second user group identifier corresponding to the selection value matches a user group that includes the user as a member;
generating, based on the selection values and the candidate parameters, a first secret share of a selection result that identifies, from a plurality of candidate digital components, a given digital component having a highest selection value, wherein each candidate digital component is a digital component for which the candidate parameter for the selection value corresponding to the digital component indicates that the second user group identifier corresponding to the selection value matches a user group that includes the user as a member; and
transmitting, to the client device, the first secret share of a selection result identifying the given digital component.
16. The one or more non-transitory computer-readable media of claim 15 , wherein determining the candidate parameter for each selection value comprises determining a first secret share of the candidate parameter for each selection value.
17. The one or more non-transitory computer-readable media of claim 15 , wherein generating the first secret share of the selection result comprises:
generating an order of the selection values based on a magnitude of each selection value;
determining, based on the order of the selection values and the candidate parameter for each selection value, a first secret share of an accumulated value for each selection value, wherein the accumulated value for each selection value indicates a position of the selection value in the order of the selection values;
determining, for each selection value, a first secret share of a winner parameter based on (i) the candidate parameter for the selection value and (ii) a result of an equality test that indicates whether the accumulated value for the selection value is a specified value; and
determining, as the first secret share of the selection result, a first secret share of a sum of, for each selection value, a product of the winner parameter for the selection value and a digital component information element for the selection value.
18. The one or more non-transitory computer-readable media of claim 17 , wherein determining the first secret share of the accumulated value for each selection value comprises:
for each individual selection value, determining a quantity of selection values, between a highest selection value and the individual selection value, that have a candidate parameter that indicates that the second user group identifier corresponding to the selection value matches at least one of the one or more first user group identifiers.
19. The one or more non-transitory computer-readable media of claim 18 , wherein the specified value is one or logical true.
20. The one or more non-transitory computer-readable media of claim 15 , wherein the distributed point functions are generated based on a plurality of user groups that include the user of the client device as a member.