Device data hashing

1 . A computer-implemented method to improve a differential privacy system that comprises one or more computers, the method comprising:

by the differential privacy system:

generating, for a client device and using original data from the client device as input to a hash function of a software module installed on at least one of the one or more computers, an output value that is in a hashing domain for the hash function, the hashing domain indicating the possible outputs of the hash function and having a domain size;

determining randomly whether to include the output value that is a hash of the original data or at least one noise value in a message;

accessing, from a memory included in one of the one or more computers, a message size criterion that indicates a smaller value than the domain size of the hashing domain;

generating, using the hash function of the software module and the message size, one or more noise values;

in response to determining to not include the output value and to include at least one noise value in the message, generating the message that includes the one or more noise values instead of the output value and that satisfies the message size criterion that is a smaller value than the domain size of the hashing domain; and

transmitting, to an external system and using an encrypted channel on a network, the message.

2 . The method of claim 1 , comprising selecting, from two or more hash functions at least some of which have different collisions, the hash function for generating the output value,

wherein generating the message comprises generating the message that includes the one or more noise values and an identifier for the hash function.

3 . The method of claim 1 , comprising:

determining not to include the output value in the message; and

in response to determining not to include the output value in the message:

generating a quantity of noise values that is the message size; and

generating the message that includes the noise values without the output value.

4 . The method of claim 1 , comprising:

determining to include the output value in the message; and

in response to determining to include the output value in the message:

generating a quantity of noise values that is one fewer than the message size; and

generating the message that includes the noise values and the output value.

5 . The method of claim 1 , wherein accessing the message size comprises computing the message size.

6 . The method of claim 1 , wherein:

the output value and the one or more noise values each comprise an index for the hash function in the hashing domain, the method comprising:

randomly permuting locations of two or more values in the message before providing the message to the external system.

7 . The method of claim 1 , wherein providing the message to the external system comprises:

encrypting the message; and

providing the encrypted message to the external system.

8 . One or more non-transitory computer storage device encoded with instructions that, when executed by a differential privacy system comprising one or more computers, causes the differential privacy system that comprises the one or more computers to perform operations comprising:

selecting, from two or more hash functions at least some of which have different collisions and each of which have a different hash function identifier, a hash function for a software module installed on at least one of the one or more computers and that has a particular hash function identifier;

determining randomly whether to include an output value in a message;

generating, for a client device and using original data from the client device as input to the hash function of the software module that has the particular hash function identifier, the output value that is in a hashing domain for the hash function;

generating, using the output value, the message that includes the particular hash function identifier for the hash function; and

transmitting, to an external system and using an encrypted channel on a network, the message that includes the particular hash function identifier for the hash function.

9 . The computer storage device of claim 8 , wherein generating the message comprises:

determining whether to include the output value in the message; and

generating the message using a result of the determination whether to include the output value in the message.

10 . The computer storage device of claim 9 , the operations comprising:

determining not to include the output value in the message; and

in response to determining not to include the output value in the message:

generating a quantity of noise values that is the message size; and

generating the message that includes the noise values without the output value.

11 . The computer storage device of claim 9 , the operations comprising:

determining to include the output value in the message; and

in response to determining to include the output value in the message:

generating a quantity of noise values that is one fewer than the message size; and

generating the message that includes the noise values and the output value.

12 . The computer storage device of claim 8 , the operations comprising:

accessing a message size that is less than a size of the hashing domain; and

generating, using the hash function and the message size, one or more noise values, wherein generating the message comprises generating the message that includes the one or more noise values and the identifier for the hash function.

13 . The computer storage device of claim 12 , wherein:

the output value and the one or more noise values each comprise an index for the hash function in the hashing domain, the operations comprising:

randomly permuting locations of two or more values in the message before providing the message to the external system.

14 . A system for improved differential privacy and comprising one or more computers each of which includes at least one processor and one or more storage devices on which are stored instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

generating, for a client device and using original data from the client device as input to a hash function of a software module installed on at least one of the one or more computers, an output value that is in a hashing domain for the hash function, the hashing domain indicating the possible outputs of the hash function and having a domain size;

determining randomly whether to include the output value that is a hash of the original data or at least one noise value in a message;

accessing, from a memory included in one of the one or more computers, a message size criterion that indicates a smaller value than the domain size of the hashing domain;

generating, using the hash function of the software module and the message size, one or more noise values;

in response to determining to not include the output value and to include at least one noise value in the message, generating the message that includes the one or more noise values instead of the output value and that satisfies the message size criterion that is a smaller value than the domain size of the hashing domain; and

transmitting, to an external system and using an encrypted channel on a network, the message.

15 . The system of claim 14 , the operations comprising selecting, from two or more hash functions at least some of which have different collisions, the hash function for generating the output value,

wherein generating the message comprises generating the message that includes the one or more noise values and an identifier for the hash function.

16 . The system of claim 14 , the operations comprising:

determining not to include the output value in the message; and

in response to determining not to include the output value in the message:

generating a quantity of noise values that is the message size; and

generating the message that includes the noise values without the output value.

17 . The system of claim 14 , the operations comprising:

determining to include the output value in the message; and

in response to determining to include the output value in the message:

generating a quantity of noise values that is one fewer than the message size; and

generating the message that includes the noise values and the output value.

18 . The system of claim 14 , wherein accessing the message size comprises computing the message size.

19 . The system of claim 14 , wherein:

the output value and the one or more noise values each comprise an index for the hash function in the hashing domain, the method comprising:

randomly permuting locations of two or more values in the message before providing the message to the external system.