Privacy-preserving measurements of a campaign

• US 9,641,332 B1
• Filed: 01/30/2013
• Issued: 05/02/2017
• Est. Priority Date: 01/30/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yung, Marcel M. M., Czajka, Tomasz
• Primary Examiner(s): Hayes, John
• Assistant Examiner(s): Winter, John M
• Application Number:
  US13/754,433
• Time in Patent Office: 1,553 Days
• Field of Search: 705 71
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

A method of measuring a campaign performance includes transforming identifiers into non-identifiers, and providing the non-identifiers to an external processing party; receiving encrypted non-identifiers comprising the non-identifiers after encryption by the external processing party, other non-identifiers, spending values, and a public cryptographic key, each member of the other non-identifiers being associated with a corresponding member of the spending values; encrypting the non-identifiers to generate other encrypted non-identifiers, and determining an intersection of the encrypted non-identifiers and the other encrypted non-identifiers to generate common encrypted non-identifiers; identifying a subset of the spending values associated with members of the encrypted non-identifiers in the common encrypted non-identifiers; and deriving a total spending value based on the subset of the spending values.

Claims

1. A computer-implemented method, comprising:

transforming a set of identifiers indicative of participants that receive an incentive from first processing party, into a set of non-identifiers, and providing the set of non-identifiers to an external processing party, the transforming comprising,

computing, by a first computational thread of a processor, a hash function on the identifiers of the participants,

generating, by a second computational thread in parallel with the computing the hash function, a random exponent based on a random element, using a random number generator, and

exponentiating, by a third computational thread in parallel with the generating the random exponent, the hash function by the random exponent;

receiving a set of encrypted non-identifiers that comprises the set of non-identifiers after an encryption operation is performed by the external processing party, another set of non-identifiers indicative of customers of the external processing party, a set of encrypted spending values associated with the another set of non-identifiers indicative of the customers of the external processing party, and a public cryptographic key, wherein each member of the another set of non-identifiers is associated with a corresponding member of the set of spending values;

encrypting the set of non-identifiers to generate another set of encrypted non-identifiers, and determining an intersection of the set of encrypted non-identifiers and the another set of encrypted non-identifiers to generate a set of common encrypted non-identifiers indicative of an intersection between the participants associated with the first processing party and the customers associated with the external processing party;

identifying a subset of the set of encrypted spending values associated with each of the members in the set of common encrypted non-identifiers; and

computing a total spending value based on the subset of the set of spending values, the computing comprising,

performing homomorphic encryption on the subset of the set of spending values to generate encrypted spending information by generating homomorphic encryption values and a randomizing value, and multiplying the homomorphic encryption values and the randomizing value,

providing the encrypted spending information to the external processing party, wherein participants associated with encrypted spending information are unidentifiable by the external processing party, wherein the external processing party decrypts the encrypted spending information to generate decrypted spending information comprising a plaintext value,

the first processing party receiving the decrypted spending information, and

computing the total spending value based on the decrypted spending information.

2. The computer-implemented method of claim 1, wherein the method is performed without communication with a party other than the external processing party.

3. The computer-implemented method of claim 1, wherein the transforming comprises performing a full domain hash on the set of identifiers to generate a hashed set of identifiers, and exponentiating the hashed set of identifiers based on a random exponent.

4. The computer-implemented method of claim 1, wherein the encrypting comprises exponentiating the set of non-identifiers based on a generated random exponent, and the determining comprises deterministically checking the intersection between the set of encrypted non-identifiers and the another set of the encrypted non-identifiers.

5. The computer-implemented method of claim 1, wherein the identifying comprises generating and encrypting a random number, multiplying each of the spending items to generate a product, multiplying the encrypted random number by the product to generate an output result, and providing the output result to the external processing party.

6. The computer-implemented method of claim 1, wherein the external processing party comprises a merchant and the another set of non-identifiers is associated with credit card information of the customers of the merchant and the first processing party comprises a campaign promoter, and further wherein the set of identifiers comprises credit card information of credit card numbers associated with a campaign, such that the intersection represents credit card numbers of the customers of the merchant and the participants in the campaign, and wherein identities of the customers are not provided to the first processing party, and identities of the participants are not provided to the external processing party.