Efficient implementation for differential privacy using cryptographic functions

• US 10,229,282 B2
• Filed: 09/23/2016
• Issued: 03/12/2019
• Est. Priority Date: 06/12/2016
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Sierra, Yannick L., Thakurta, Abhradeep Guha, Vaishampayan, Umesh S., Hurley, John C., Mowery, Keaton F., Brouwer, Michael
• Primary Examiner(s): Waliullah, Mohammed
• Application Number:
  US15/275,284
• Publication Number:
  US 20170357820A1
• Time in Patent Office: 900 Days
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: H04L 63/0421 Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

The system described may implement a 1-bit protocol for differential privacy for a set of client devices that transmit information to a server. Implementations of the system may leverage specialized instruction sets or engines built into the hardware or firmware of a client device to improve the efficiency of the protocol. For example, a client device may utilize these cryptographic functions to randomize information sent to the server. In one embodiment, the client device may use cryptographic functions such as hashes including SHA or block ciphers including AES. Accordingly, the system provides an efficient mechanism for implementing differential privacy.

Claims

1. A non-transitory machine-readable medium storing instructions which, when executed by one or more processors of a system, cause the system to perform operations for differential privacy when determining a frequency of values, the operations comprising:

identifying, at a client device, a value from a known set of values to transmit to a server;

determining a random bit position within a representation of the identified value;

randomizing, by the client device, the identified value using a public pseudorandom function that inputs the representation of the identified value and the random bit position and outputs a string of bits;

selecting a single bit value from the string of bits at a bit position based on the random bit position;

creating a privatized bit value of the single bit value by performing a biased coin flip operation to determine whether to flip the single bit value; and

transmitting, to the server, the privatized bit value and the random bit position, wherein the server precomputes a vector for each respective value of the known set of values using the public pseudorandom function, identifies one or more of the vectors including a bit matching the privatized bit value at the bit position based on the random bit position, and updates a frequency estimation of one or more of the known set of values corresponding to the vectors identified.

2. The medium of claim 1, wherein the transmitting the privatized bit value and the random bit position to the server includes transmitting only the privatized bit value and the random bit position as an identifier for the value from the known set of values.

3. The medium of claim 1, wherein the pseudorandom function is a cryptographic function that is hardware-accelerated on the client device.

4. The medium of claim 3, wherein the cryptographic function is a block cipher or a hash function.

5. The medium of claim 4, wherein the block cipher is an Advanced Encryption Standard (AES) algorithm or the hash function is a Secure Hash Algorithm (SHA).

6. The medium of claim 1, wherein the pseudorandom function uses a specialized cryptographic instruction set for a processor of the client device.

7. The medium of claim 6, wherein the specialized cryptographic instruction set includes a cryptographic function, and wherein the cryptographic function is a block cipher or a hash function.

8. The medium of claim 7, wherein the block cipher is an Advanced Encryption Standard (AES) algorithm or the hash function is a Secure Hash Algorithm (SHA).

9. The medium of claim 1, wherein the representation of the identified value is a hash value from a cryptographic hash function.

10. The medium of claim 1, wherein the randomizing receives the bit position and the pseudorandom function outputs only the single bit value at the bit position as the string of bits.

11. The medium of claim 1, further comprising applying statistical noise to the privatized bit value before transmitting the privatized bit value to the server.

12. The medium of claim 1, wherein the known set of values includes user interaction data for one or more users of the client device.

13. A device, comprising:

a memory storing instructions; and

a processor coupled to the memory to execute the instructions from the memory, the processor being configured to;

identify a value from a known set of values to transmit to a server;

determine a random bit position within a hash representation of the identified value;

randomize the identified value using an Advanced Encryption Standard (AES) function that inputs the hash representation of the identified value as a key and the random bit position as data, and outputs a single bit value of a resulting ciphertext at a bit position based on the random bit position;

create a privatized bit value of the single bit value by performing a biased coin flip operation to determine whether to flip the single bit value; and

transmit, to the server, the privatized bit value and the random bit position, wherein the server precomputes a vector for each respective value of the known set of values using an AES function, identifies one or more of the vectors including a bit matching the privatized bit value at the bit position based on the random bit position, and updates a frequency estimation of one or more of the known set of values corresponding to the vectors identified.

14. The device of claim 13, wherein only the privatized bit value and the random bit position are transmitted to the server as an identifier for the value from the known set of values.

15. The device of claim 13, wherein the AES function is hardware-accelerated on the device.

16. The device of claim 13 wherein the processor includes a specialized AES instruction set, the specialized AES instruction set including the AES function.

17. The device of claim 13, wherein the server precomputes a vector for each respective value of the known set of values using an AES function, identifies one or more of the vectors including a bit matching the privatized bit value at the bit position based on the random bit position, and updates a frequency estimation of one or more of the known set of values corresponding to the vectors identified.

18. The device of claim 13, wherein the hash representation is determined using one of a SHA, SHA1, SHA2, SHA3, or MD5.

19. The device of claim 13, wherein the hash representation is determined using a hardware-accelerated hash function or a specialized instruction set for a hash function.

20. The device of claim 13, wherein the random bit position received as data is calculated as the random bit position divided by a bit size of the ciphertext, and the bit position is calculated as the random bit position modulo a bit size of the ciphertext.

21. A device, comprising:

a memory storing instructions; and

a processor coupled to the memory to execute the instructions from the memory, the processor being configured to;

identify a value from a known set of values to transmit to a server;

determine a random bit position within a hash of the identified value;

randomize the identified value using a Secure Hash Algorithm (SHA) function that inputs the hash of the identified value and the random bit position, and outputs a single bit value of a resulting hash at a bit position based on the random bit position, wherein the SHA function generates both the hash of the identified value and the resulting hash in response to a single function call;

create a privatized bit value of the single bit value by performing a biased coin flip operation to determine whether to flip the single bit value; and

transmit, to the server, only the privatized bit value and the random bit position, wherein the server precomputes a vector for each respective value of the known set of values using the SHA function, identifies one or more of the vectors including a bit matching the privatized bit value at the bit position based on the random bit position, and updates a frequency estimation of one or more of the known set of values corresponding to the vectors identified.

22. The device of claim 21, wherein only the privatized bit value and the random bit position are transmitted to the server as an identifier for the value from the known set of values.

23. The device of claim 21, wherein the SHA function is hardware-accelerated on the device or the processor includes a specialized SHA instruction set, the specialized SHA instruction set including the SHA function.

24. The device of claim 21, wherein the random bit position received as data is calculated as the random bit position divided by a bit size of the resulting hash, and the bit position is calculated as the random bit position modulo the bit size of the resulting hash.

25. A non-transitory machine-readable medium storing instructions which, when executed by one or more processors of a system, cause the system to perform operations to achieve differential privacy when determining a frequency of values, the operations comprising:

receiving, at a server, a single bit value and a random bit position from a client device, the single bit value representing an output of a cryptographic function performed on the client device to randomize an input from a known set of inputs, wherein the random bit position is a position with a representation of the input from the known set of inputs;

precomputing, at the server, a vector for each respective value of the known set of values using the cryptographic function;

identifying one or more of the vectors including a bit matching the single bit value at a bit position based on the random bit position; and

updating a frequency estimation of one or more of the known set of values corresponding to the vectors identified.

26. The medium of claim 25, wherein the single bit value is a privatized bit value.

27. The medium of claim 25, wherein the cryptographic function is a block cipher or a hash function.

28. The medium of claim 25, wherein the frequency estimation is part of a frequency distribution estimation that is within a predictable margin of error of an actual frequency distribution for the known set of values.

29. The medium of claim 25, wherein the frequency estimation for a particular value is calculated based on a weighted sum determination.

30. The medium of claim 25, wherein the frequency estimations are updated using a batch processing technique.

31. The medium of claim 25, wherein the vector for each respective value is an output concatenation of a string of bits from the cryptographic function that inputs the representation of the respective value with each possible value of the random bit position.