Differential privacy using a multibit histogram

• US 10,726,139 B2
• Filed: 09/30/2017
• Issued: 07/28/2020
• Est. Priority Date: 06/04/2017
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Bhowmick, Abhishek, Vyrros, Andrew H., Salesi, Matthew R., Vaishampayan, Umesh S.
• Primary Examiner(s): Getachew, Abiy
• Application Number:
  US15/721,894
• Publication Number:
  US 20180349620A1
• Time in Patent Office: 1,032 Days
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: G06F 17/145 Square transforms, e.g. Hadamard, Walsh, Haar, Hough, Slant transforms
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 21/606 by securing the transmission between two devices or processes
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD

Abstract

Embodiments described herein ensure differential privacy when transmitting data to a server that estimates a frequency of such data amongst a set of client devices. The differential privacy mechanism may provide a predictable degree of variance for frequency estimations of data. The system may use a multibit histogram model or Hadamard multibit model for the differential privacy mechanism, both of which provide a predictable degree of accuracy of frequency estimations while still providing mathematically provable levels of privacy.

Claims

1. A non-transitory machine-readable medium storing instructions which, when executed by one or more processors of a computing device, cause the computing device to perform operations comprising:

selecting a value of user data to transmit to a server from a set of user data values collected on a client device;

encoding the selected value using a Hadamard matrix, wherein the encoding flips a sign of an element of the Hadamard matrix, and wherein the element is selected based on the value of user data and a random integer;

privatizing the element by selectively flipping, in accordance with a predefined probability, a sign of the element of the Hadamard matrix; and

transmitting the privatized element and the random integer to the server, wherein the server performs a summation operation with the privatized element to estimate a frequency of the value of user data amongst a set of different client devices.

2. The non-transitory machine-readable medium of claim 1, wherein the predefined probability is defined based on a privacy parameter and the privatized element is locally differentially private.

3. The non-transitory machine-readable medium of claim 1, wherein the summation operation performed by the server determines a frequency of a user data value from the set of different client devices.

4. The non-transitory machine-readable medium of claim 1, wherein the Hadamard matrix is a square matrix having a size defined by a universe of possible user values.

5. The non-transitory machine-readable medium of claim 1, wherein the summation operation performed by the server determines a frequency of possible user data values amongst the set of different client devices.

6. The non-transitory machine-readable medium of claim 1, wherein the value of user data represents information related to one or more device features used by a user associated with the client device.

7. The non-transitory machine-readable medium of claim 1, wherein the value of user data represents health data for the user that has been collected by a user device.

8. The non-transitory machine-readable medium of claim 1, wherein the value of user data represents an activity type performed the user.

9. A device, comprising:

a processor; and

a memory coupled to the processor, the memory storing instructions, which when executed by the processor, cause the processor to perform operations to;

select a value of user data to transmit to a server from a set of user data values collected on a client device;

encode the selected value using a Hadamard matrix, wherein the encoding flips a sign of an element of the Hadamard matrix, and wherein the element is selected based on the value of user data and a random integer;

privatize the element by selectively flipping, in accordance with a predefined probability, a sign of the element of the Hadamard matrix; and

transmit the privatized element and the random integer to the server, wherein the server performs a summation operation with the privatized element to estimate a frequency of the value of user data amongst a set of different client devices.

10. The device of claim 9, wherein the predefined probability is defined based on a privacy parameter and the privatized element is locally differentially private.

11. The device of claim 9, wherein the summation operation performed by the server determines a frequency of a user data value from the set of different client devices.

12. The device of claim 9, wherein the Hadamard matrix is a square matrix having a size defined by a universe of possible user values.

13. The device of claim 9, wherein the summation operation performed by the server determines a frequency of possible user data values amongst the set of different client devices.

14. The device of claim 9, wherein the value of user data represents information related to one or more device features used by a user associated with the client device.

15. The device of claim 9, wherein the value of user data represents health data for the user that has been collected by a user device.

16. The device of claim 9, wherein the value of user data represents an activity type performed the user.

17. A method, the method comprising:

selecting a value of user data to transmit to a server from a set of user data values collected on a client device;

encoding the selected value using a Hadamard matrix, wherein the encoding flips a sign of an element of the Hadamard matrix, and wherein the element is selected based on the value of user data and a random integer;

privatizing the element by selectively flipping, in accordance with a predefined probability, a sign of the element of the Hadamard matrix; and

transmitting the privatized element and the random integer to the server, wherein the server performs a summation operation with the privatized element to estimate a frequency of the value of user data amongst a set of different client devices.

18. The method of claim 17, wherein the predefined probability is defined based on a privacy parameter and the privatized element is locally differentially private.

19. The method of claim 17, wherein the summation operation performed by the server determines a frequency of a user data value from the set of different client devices.

20. The method of claim 17, wherein the Hadamard matrix is a square matrix having a size defined by a universe of possible user values.

21. The method of claim 17, wherein the summation operation performed by the server determines a frequency of possible user data values amongst the set of different client devices.