Security graph construction algorithm based on private set intersection and secret sharing

1 . A computer-implemented method comprising:

mapping, by one or more first devices, a first plurality of user identifiers that are active in a first region to generate a first plurality of anonymized user nodes of the first region;

communicating with one or more second devices of a second region, using a privacy set intersection (PSI) protocol, to identify one or more intersecting signals accessed by the first plurality of anonymized user nodes of the first region and a second plurality of anonymized user nodes of the second region;

constructing, by the one or more first devices, a user-signal-user graph based on, at least in part, the one or more intersecting signals and the first plurality of anonymized user nodes of the first region;

communicating with the one or more second devices of the second region, using a secret sharing protocol, to calculate a weight of each intersecting signal, wherein said communicating comprises:

using the secret sharing protocol to determine a count of anonymized user nodes connected to a particular intersecting signal from the first region and the second region;

using the secret sharing protocol to determine a count of anonymized user nodes connected to each signal of a different type that neighbors the particular intersecting signal from the first region and the second region; and

calculating the weight of the particular intersecting signal based on the count of anonymized user nodes connected to the particular intersecting signal and the count of anonymized user nodes connected to each signal of a different type that neighbors the particular intersecting signal; and

constructing, by the one or more first devices, a user-user graph with at least one edge determined by, at least in part, the weight of each intersecting signal from the user-signal-user graph.

2 . The computer-implemented method of claim 1 , wherein communicating with one or more second devices of a second region using a PSI protocol comprises:

encrypting, using a first encryption key for the one or more first devices, a list of signals accessed by the anonymized user nodes of the first region to generate a first plurality of encrypted signals.

3 . The computer-implemented method of claim 2 , further comprising:

receiving, from the one or more second devices of a second region, a first plurality of doubly encrypted signals accessed by the anonymized user nodes of the first region, wherein the first plurality of doubly encrypted signals are further encrypted based on a second encryption key for the one or more second devices of the second region; and

decrypting, using the first encryption key for the one or more first devices, the first plurality of doubly encrypted signals accessed by the anonymized user nodes of the first region to generate a third plurality of encrypted signals encrypted based on the second encryption key for the one or more second devices of the second region.

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

receiving, from the one or more second devices of a second region, a second plurality of encrypted signals accessed by the anonymized user nodes of the second region, wherein the second plurality of encrypted signals are encrypted based on the second encryption key for the one or more second devices of the second region; and

comparing the second plurality of encrypted signals and the third plurality of encrypted signals to identify the one or more intersecting signals accessed by the first plurality of anonymized user nodes of the first region and a second plurality of anonymized user nodes of the second region.

5 . The computer-implemented method of claim 1 , wherein said calculating the weight of the particular intersecting signal is performed without revealing information of the anonymized user nodes inside the second region to the one or more first devices of the first region.

6 . The computer-implemented method of claim 1 , wherein the at least one edge is a cross-regional edge, and at least one anonymized user node of the first region is connected to an anonymized user node of the second region via the cross-regional edge.

7 . One or more non-transitory computer-readable storage media encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

mapping a first plurality of user identifiers that are active in a first region to generate a first plurality of anonymized user nodes of the first region;

communicating with one or more devices of a second region, using a privacy set intersection (PSI) protocol, to identify one or more intersecting signals accessed by the first plurality of anonymized user nodes of the first region and a second plurality of anonymized user nodes of the second region;

constructing a user-signal-user graph based on, at least in part, the one or more intersecting signals and the first plurality of anonymized user nodes of the first region;

communicating with the one or more devices of the second region, using a secret sharing protocol, to calculate a weight of each intersecting signal, wherein said communicating comprises:

using the secret sharing protocol to determine a count of anonymized user nodes connected to a particular intersecting signal from the first region and the second region;

using the secret sharing protocol to determine a count of anonymized user nodes connected to each signal of a different type that neighbors the particular intersecting signal from the first region and the second region; and

calculating the weight of the particular intersecting signal based on the count of anonymized user nodes connected to the particular intersecting signal and the count of anonymized user nodes connected to each signal of a different type that neighbors the particular intersecting signal; and

constructing a use-user graph with at least one edge determined by, at least in part, the weight of each intersecting signal from the user-signal-user graph.

8 . The one or more non-transitory computer-readable storage media of claim 7 , wherein communicating with one or more devices of a second region using a PSI protocol comprises:

encrypting, using a first encryption key for the one or more computers, a list of signals accessed by the anonymized user nodes of the first region to generate a first plurality of encrypted signals.

9 . The one or more non-transitory computer-readable storage media of claim 8 , wherein the operations further comprise:

receiving, from the one or more devices of a second region, a first plurality of doubly encrypted signals accessed by the anonymized user nodes of the first region, wherein the first plurality of doubly encrypted signals are further encrypted based on a second encryption key for the one or more devices of the second region; and

decrypting, using the first encryption key for the one or more computers, the first plurality of doubly encrypted signals accessed by the anonymized user nodes of the first region to generate a third plurality of encrypted signals encrypted based on the second encryption key for the one or more devices of the second region.

10 . The one or more non-transitory computer-readable storage media of claim 9 , wherein the operations further comprise:

receiving, from the one or more devices of a second region, a second plurality of encrypted signals accessed by the anonymized user nodes of the second region, wherein the second plurality of encrypted signals are encrypted based on the second encryption key for the one or more devices of the second region; and

comparing the second plurality of encrypted signals and the third plurality of encrypted signals to identify the one or more intersecting signals accessed by the first plurality of anonymized user nodes of the first region and a second plurality of anonymized user nodes of the second region.

11 . The one or more non-transitory computer-readable storage media of claim 7 , wherein said calculating the weight of the particular intersecting signal is performed without revealing information of the anonymized user nodes inside the second region to the one or more computers of the first region.

12 . The one or more non-transitory computer-readable storage media of claim 7 , wherein the at least one edge is a cross-regional edge, and at least one anonymized user node of the first region is connected to an anonymized user node of the second region via the cross-regional edge.

13 . A computer system comprising one or more hardware computer processors configured to perform operations comprising:

mapping a first plurality of user identifiers that are active in a first region to generate a first plurality of anonymized user nodes of the first region;

communicating with one or more devices of a second region, using a privacy set intersection (PSI) protocol, to identify one or more intersecting signals accessed by the first plurality of anonymized user nodes of the first region and a second plurality of anonymized user nodes of the second region;

constructing a user-signal-user graph based on, at least in part, the one or more intersecting signals and the first plurality of anonymized user nodes of the first region;

communicating with the one or more devices of the second region, using a secret sharing protocol, to calculate a weight of each intersecting signal, wherein said communicating comprises:

using the secret sharing protocol to determine a count of anonymized user nodes connected to a particular intersecting signal from the first region and the second region;

using the secret sharing protocol to determine a count of anonymized user nodes connected to each signal of a different type that neighbors the particular intersecting signal from the first region and the second region; and

calculating the weight of the particular intersecting signal based on the count of anonymized user nodes connected to the particular intersecting signal and the count of anonymized user nodes connected to each signal of a different type that neighbors the particular intersecting signal; and

constructing a user-user graph with at least one edge determined by, at least in part, the weight of each intersecting signal from the user-signal-user graph.

14 . The computer system of claim 13 , wherein communicating with one or more devices of a second region using a PSI protocol comprises:

encrypting, using a first encryption key for the one or more hardware computer processors, a list of signals accessed by the anonymized user nodes of the first region to generate a first plurality of encrypted signals.

15 . The computer system of claim 14 , wherein the operations further comprise:

receiving, from the one or more devices of a second region, a first plurality of doubly encrypted signals accessed by the anonymized user nodes of the first region, wherein the first plurality of doubly encrypted signals are further encrypted based on a second encryption key for the one or more devices of the second region; and

decrypting, using the first encryption key for the one or more hardware computer processors, the first plurality of doubly encrypted signals accessed by the anonymized user nodes of the first region to generate a third plurality of encrypted signals encrypted based on the second encryption key for the one or more devices of the second region.

16 . The computer system of claim 15 , wherein the operations further comprise:

receiving, from the one or more devices of a second region, a second plurality of encrypted signals accessed by the anonymized user nodes of the second region, wherein the second plurality of encrypted signals are encrypted based on the second encryption key for the one or more devices of the second region; and

comparing the second plurality of encrypted signals and the third plurality of encrypted signals to identify the one or more intersecting signals accessed by the first plurality of anonymized user nodes of the first region and a second plurality of anonymized user nodes of the second region.

17 . The computer system of claim 13 , wherein said calculating the weight of the particular intersecting signal is performed without revealing information of the anonymized user nodes inside the second region to the one or more hardware computer processors of the first region.