Cryptographic computation techniques for multi-party reach and frequency
Systems and methods for detecting a collision when combining a first encrypted data structure and a second encrypted data structure are disclosed. The system can receive the first encrypted data structure representative of a first plurality of registers. Each register in the first plurality of registers can have an encrypted fingerprint value, and an encrypted register identifier value. The system can receive the second encrypted data structure representative of a second plurality of registers. The system can calculate a first sum associated with a first register of the first plurality of registers based on the fingerprint value of the first register. The system can calculate a second sum associated with a second register of the second plurality of registers. The system can determine a validity bit associated with the collision based on a comparison of the first sum and the second sum.
1. A method for detecting a collision in secure multi-party computation when combining a first encrypted data structure and a second encrypted data structure into a combined encrypted data structure, comprising:
receiving, by a data processing system comprising one or more processors and a memory, the first encrypted data structure representative of a first plurality of registers, each register in the first plurality of registers having an encrypted fingerprint value, and an encrypted register identifier value;
receiving, by the data processing system, the second encrypted data structure representative of a second plurality of registers, each register in the second plurality of registers having an encrypted fingerprint value, and an encrypted register identifier value;
calculating, by the data processing system, a first sum associated with a first register of the first plurality of registers based on the encrypted fingerprint value of the first register;
calculating, by the data processing system, a second sum associated with a second register of the second plurality of registers based on the encrypted fingerprint value of the second register; and
determining, by the data processing system, a validity bit indicating whether the collision has occurred based on a comparison of the first sum and the second sum, wherein the validity bit is set as true when the encrypted fingerprint value of the first register or the encrypted fingerprint value of the second register when decrypted is indicative of a zero value.
2. The method of claim 1 , wherein the first register includes an encrypted first count value and the second register includes an encrypted second count value, and wherein the first sum is further calculated based on the encrypted first count value, and wherein the second sum is further calculated based on the encrypted second count value.
3. The method of claim 2 , the method further comprising:
generating a third register in the combined encrypted data structure by concatenating the first register and the second register when the validity bit is set as true; and
calculating a reach value associated with the third register based on a summation of the encrypted first count value and the encrypted second count value.
4. The method of claim 1 , wherein the first encrypted data structure is transmitted using a dense protocol, and wherein the encrypted fingerprint value of the first register prior to being encrypted is indicative of a zero value for one or more registers in the first plurality of registers.
5. The method of claim 1 , further comprising:
generating the combined encrypted data structure by concatenating the first encrypted data structure with the second encrypted data structure, the combined encrypted data structure representative of a third plurality of registers, a third register in the third plurality of registers having an encrypted count value, an encrypted fingerprint value, an encrypted register identifier value, and the validity bit.
6. The method of claim 5 , wherein the validity bit is encrypted by the data processing system prior to being transmitted to a worker computing device.
7. The method of claim 6 , further comprising:
transmitting, by the data processing system, the combined encrypted data structure to the worker computing device, each register in the third plurality of registers having an encrypted count value, an encrypted fingerprint value, an encrypted register identifier value, and an encrypted validity bit; and
wherein a reach value and a frequency value is calculated based on the encrypted count value and the encrypted validity bit.
8. The method of claim 1 , wherein the validity bit is set as true when the encrypted fingerprint value of the first register matches the encrypted fingerprint value of the second register.
9. The method of claim 1 , wherein the validity bit is set as false when the encrypted fingerprint value of the first register does not match the encrypted fingerprint value of the second register, and neither the encrypted fingerprint value of the first register nor the encrypted fingerprint value of the second register when decrypted is indicative of a zero value.
10. The method of claim 1 , wherein the encrypted register identifier value of the first register is equal to the encrypted register identifier value of the second register.
11. The method of claim 1 , wherein the first encrypted data structure has an additively homomorphic encryption, and wherein the data processing system calculates the first sum without having to decrypt the encrypted count value of the first register and the encrypted fingerprint value of the first register.
12. The method of claim 1 , wherein the first plurality of registers is received from a first publishing computing device, and wherein the second plurality of registers is received from a second publishing computing device.
13. The method of claim 1 , wherein calculating the first sum associated with the first register includes:
generating a plurality of vectors based on the encrypted count value and the encrypted fingerprint value associated with the first plurality of registers; and
wherein the first sum is calculated by summing each vector in the plurality of vectors.
14. The method of claim 13 , wherein a first vector in the plurality of vectors is generated by adding together the encrypted count values in the first plurality of registers.
15. The method of claim 13 , wherein the plurality of vectors is further based on a first random number and a second random number.
16. The method of claim 15 , where a second vector in the plurality of vectors is generated by:
multiplying the encrypted fingerprint values in the first plurality of registers with the first random number.
17. The method of claim 15 , where a third vector in the plurality of vectors is generated by:
multiplying the encrypted fingerprint values in the first plurality of registers with the second random number.
18. A computing device for detecting a collision in secure multi-party computation when combining a first encrypted data structure and a second encrypted data structure into a combined encrypted data structure, comprising:
one or more processors; and
one or more memory devices storing instructions that are executable by the one or more processors to cause the one or more processors to perform operations, the operations comprising:
receiving the first encrypted data structure representative of a first plurality of registers, each register in the first plurality of registers having an encrypted fingerprint value, and an encrypted register identifier value;
receiving the second encrypted data structure representative of a second plurality of registers, each register in the second plurality of registers having an encrypted fingerprint value, and an encrypted register identifier value;
calculating a first sum associated with a first register of the first plurality of registers based on the encrypted fingerprint value of the first register;
calculating a second sum associated with a second register of the second plurality of registers based on the encrypted fingerprint value of the second register; and
determining a validity bit indicating whether the collision has occurred based on a comparison of the first sum and the second sum, wherein the validity bit is set as true when the encrypted fingerprint value of the first register or the encrypted fingerprint value of the second register when decrypted is indicative of a zero value.
19. One or more non-transitory computer-readable media comprising instructions for detecting a collision in secure multi-party computation when combining a first encrypted data structure and a second encrypted data structure into a combined encrypted data structure, the instructions when executed by one or more computing devices, cause the one or more computing devices to perform operations comprising:
receiving the first encrypted data structure representative of a first plurality of registers, each register in the first plurality of registers having an encrypted fingerprint value, and an encrypted register identifier value;
receiving the second encrypted data structure representative of a second plurality of registers, each register in the second plurality of registers having an encrypted fingerprint value, and an encrypted register identifier value;
calculating a first sum associated with a first register of the first plurality of registers based on the encrypted fingerprint value of the first register;
calculating a second sum associated with a second register of the second plurality of registers based on the encrypted fingerprint value of the second register; and
determining a validity bit indicating whether the collision has occurred based on a comparison of the first sum and the second sum, wherein the validity bit is set as true when the encrypted fingerprint value of the first register or the encrypted fingerprint value of the second register when decrypted is indicative of a zero value.