Secure multi-party reach and frequency estimation

Patent metadata

Field	Value
Publication number	US-11909864-B2
Application number	US-202017276643-A
Country	US
Kind code	B2
Filing date	Jul 28, 2020
Priority date	Feb 14, 2020
Publication date	Feb 20, 2024
Grant date	Feb 20, 2024

Abstract

Systems and methods for generating min-increment counting bloom filters to determine count and frequency of device identifiers and attributes in a networking environment are disclosed. The system can maintain a set of data records including device identifiers and attributes associated with device in a network. The system can generate a vector comprising coordinates corresponding to counter registers. The system can identify hash functions to update a counting bloom filter. The system can hash the data records to extract index values pointing to a set of counter registers. The system can increment the positions in the min-increment counting bloom filter corresponding to the minimum values of the counter registers. The system can obtain an aggregated public key comprising a public key. The system can encrypt the counter registers using the aggregated shared key to generate an encrypted vector. The system can transmit the encrypted vector to a networked worker computing device.

First claim

What is claimed is:

1. A method of generating an encrypted data structure representative of a set of identifiers having attributes that satisfy target criteria for secure and computationally efficient transmission, comprising:
maintaining, by a data processing system comprising one or more processors and a memory, in a database, a set of device identifiers, each of the set of device identifiers comprising a device attribute;
generating, by the data processing system, a vector data structure comprising a plurality of coordinates each corresponding to a respective one of a plurality of counter registers;
hashing, by the data processing system, a device identifier of the set of device identifiers using each of a plurality of hash functions to generate a plurality of hashed data record values;
extracting, by the data processing system, a plurality of register identifiers from the plurality of hashed data record values, each of the plurality of register identifiers corresponding to a respective counter register of the plurality of counter registers;
accessing, by the data processing system, each of the plurality of counter registers that correspond to the plurality of register identifiers to identify a set of counter registers that satisfy a minimum value threshold, wherein identifying the set of counter registers that satisfy the minimum value threshold comprises:
determining a value for each respective counter register of the plurality of counter registers to determine a minimum value;
comparing the value for each respective counter register of the plurality of counter registers; and
identifying one or more counter registers of the plurality of counter registers as satisfying the minimum value threshold if the value of the respective counter register is equal to the minimum value;

incrementing, by the data processing system, each of the set of counter registers that satisfy the minimum value threshold;
encrypting, by the data processing system, the vector data structure to create an encrypted data structure, such that the encrypted data structure can be combined with a second encrypted data structure; and
transmitting, by the data processing system, the encrypted vector data structure to a worker computing device.

2. The method of claim 1 , further comprising:
receiving, by the data processing system, a first device identifier comprising a first device attribute; and
storing, by the data processing system, the first device identifier comprising the first device attribute as a member of the set of device identifiers.

3. The method of claim 1 , further comprising identifying, by the data processing system, a uniformly distributed hash function as one of the plurality of hash functions, wherein the uniformly distributed hash function outputs uniformly distributed values.

4. The method of claim 1 , wherein hashing the device identifier of the set of device identifiers further comprises storing, by the data processing system, in the database, each of the plurality of hashed data record values in association with the device identifier.

5. The method of claim 1 , wherein extracting the plurality of register identifiers further comprises performing a modulus operation on each of the plurality of hashed data record values using a number of the plurality of counter registers.

6. The method of claim 1 , wherein the vector data structure is first vector in a matrix data structure comprising the first vector and a second vector, and wherein generating the vector data structure further comprises:
selecting, by the data processing system, a selected vector using a hash function of the plurality of hash functions and the device identifier of the set of device identifiers, wherein the selected vector is one of the first vector or the second vector; and
updating, by the data processing system, a coordinate of the selected vector of the matrix data structure using the hash function and the device identifier of the set of device identifiers.

7. The method of claim 6 , wherein selecting the selected vector further comprises:
hashing, by the data processing system, the device identifier of the set of device identifiers to generate a hashed device identifier;
determining, by the data processing system, a number of least significant bits of the hashed device identifier that satisfy a predetermined bit value; and
selecting, by the data processing system, the first vector as the selected vector or the second vector as the selected vector, based on the number of least significant bits of the hashed device identifier that satisfy the predetermined bit value.

8. The method of claim 7 , wherein updating the coordinate of the selected vector of the matrix data structure further comprises:
performing, by the data processing system, a modulus operation on the hashed device identifier to calculate a counter register index value;
selecting, by the data processing system, the coordinate using the counter register index value; and
incrementing, by the data processing system, the coordinate selected using the counter register index value.

9. A system for generating an encrypted data structure representative of a set of identifiers having attributes that satisfy target criteria for secure and computationally efficient transmission, comprising:
a data processing system comprising one or more processors and a memory, the data processing system configured to:
maintain, in a database, a set of device identifiers, each of the set of device identifiers comprising a device attribute;
generate a vector data structure comprising a plurality of coordinates each corresponding to a respective one of a plurality of counter registers;
hash, by the data processing system, a device identifier of the set of device identifiers using each of a plurality of hash functions to generate a plurality of hashed data record values;
extract, by the data processing system, a plurality of register identifiers from the plurality of hashed data record values, each of the plurality of register identifiers corresponding to a respective counter register of the plurality of counter registers;
access, by the data processing system, each of the plurality of counter registers that correspond to the plurality of register identifiers to identify a set of counter registers that satisfy a minimum value threshold, wherein identifying the set of counter registers that satisfy the minimum value threshold comprises:
determining a value for each respective counter register of the plurality of counter resisters to determine a minimum value;
comparing the value for each respective counter register of the plurality of counter registers; and
identifying one or more counter registers of the plurality of counter registers as satisfying the minimum value threshold if the value of the respective counter register is equal to the minimum value;

increment, by the data processing system, each of the set of counter registers that satisfy the minimum value threshold;
encrypt the vector data structure to create an encrypted data structure, such that the encrypted data structure can be combined with a second encrypted data structure; and
transmit the encrypted vector data structure to a worker computing device.

10. The system of claim 9 , wherein the data processing system is further configured to:
receive a first device identifier comprising a first device attribute; and
store the first device identifier comprising the first device attribute as a member of the set of device identifiers.

11. The system of claim 9 , wherein the data processing system is further configured to identify a uniformly distributed hash function as one of the plurality of hash func

Assignees

• Google Llc

Inventors

• Wright Craig
• Kreuter Benjamin R
• Koehler James Robert
• Skvortsov Evgeny
• Asuncion Arthur
• Book Laura Grace
• Ma Sheng
• Peng Jiayu
• Huang Xichen

Classifications

• H04L9/0825 Primary

  using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates · CPC title

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F21/6254

  by anonymising data, e.g. decorrelating personal data from the owner's identification · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• H04L9/008 Primary

  involving homomorphic encryption · CPC title