Efficient implementation for differential privacy using cryptographic functions

• US 10,552,631 B2
• Filed: 03/08/2019
• Issued: 02/04/2020
• 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:
  US16/297,464
• Publication Number:
  US 20190205561A1
• Time in Patent Office: 333 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

One embodiment provides a system that implements a 1-bit protocol for differential privacy for a set of client devices that transmit information to a server. Implementations 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 to provide 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 an electronic device, cause the electronic device to perform operations for differential privacy when determining a frequency of values, the operations comprising:

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

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

outputting a set of bits by randomizing the identified value using a pseudorandom function that inputs the representation of the identified value and the randomized bit position within the representation of the identified value;

selecting a bit value from the set of bits at a bit position based on the randomized bit position;

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

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

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

3. The non-transitory machine-readable medium of claim 1, wherein the pseudorandom function is a cryptographic function that is hardware-accelerated on the electronic device.

4. The non-transitory machine-readable medium of claim 3, wherein the cryptographic function is a block cipher or a hash function.

5. The non-transitory machine-readable 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 non-transitory machine-readable medium of claim 1, wherein the pseudorandom function uses a specialized cryptographic instruction set for a processor of the electronic device.

7. The non-transitory machine-readable 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 non-transitory machine-readable 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 non-transitory machine-readable medium of claim 1, wherein the representation of the identified value is a hash value from a cryptographic hash function.

10. The non-transitory machine-readable medium of claim 1, wherein randomizing the identified value includes receiving the bit position and the pseudorandom function outputs only the bit value at the bit position as the set of bits.

11. The non-transitory machine-readable 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 non-transitory machine-readable medium of claim 1, wherein the known set of values includes user interaction data for one or more users of the electronic device.

13. An electronic device comprising:

a memory to store instructions; and

one or more processors coupled to the memory to execute the instructions, wherein the instructions cause the one or more processors to;

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

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

randomize the identified value via a cryptographic function, the cryptographic function to receive the hash representation of the identified value as a key and the randomized bit position as data, and output a bit value of a resulting ciphertext at a bit position based on the randomized bit position;

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

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

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

15. The electronic device of claim 13, wherein the cryptographic function is an Advanced Encryption Standard (AES) function.

16. The electronic device of claim 15, wherein the one or more processors include a specialized AES instruction set, the specialized AES instruction set including the AES function.

17. The electronic device of claim 13, wherein the server is to precompute a vector for each respective value of the known set of values using an AES function.

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

19. The electronic 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 electronic device of claim 13, wherein the randomized bit position received as data is calculated as the randomized bit position divided by a bit size of the ciphertext, and the bit position is calculated as the randomized bit position modulo a bit size of the ciphertext.

21. The electronic device of claim 13, wherein the cryptographic function is a Secure Hash Algorithm (SHA) function, the resulting ciphertext is a resulting hash, and the SHA function generates both the hash of the identified value and the resulting hash in response to a single function call.

22. The electronic device of claim 21, wherein the server is to precompute a vector for each respective value of the known set of values using a SHA function.

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

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

25. A data processing system on a server device, the system comprising:

a memory to store instructions; and

one or more processors coupled to the memory to execute the instructions, wherein the instructions cause the one or more processors to perform operations comprising;

receiving, at the server device, a bit value and a randomized bit position from a client device, the 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 randomized bit position is a position with a representation of the input from the known set of inputs;

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

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

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

26. The data processing system of claim 25, wherein the bit value is a privatized bit value.

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

28. The data processing system 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 data processing system of claim 25, wherein the frequency estimation for a particular value is calculated based on a weighted sum determination.

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

31. The data processing system of claim 25, wherein the vector for each respective value is an output concatenation of a set of bits from the cryptographic function that inputs the representation of the respective value with each possible value of the randomized bit position.