Data anonymization based on guessing anonymity

• US 8,627,483 B2
• Filed: 12/18/2008
• Issued: 01/07/2014
• Est. Priority Date: 12/18/2008
• Status: Active Grant

• Current Assignee: Accenture Global Services Limited (Accenture PLC)
• Original Assignee: Accenture Global Services Limited (Accenture PLC)
• Inventors: Rachlin, Yaron, Probst, Katherine, Ghani, Rayid
• Primary Examiner(s): OBEID, MAMON A
• Application Number:
  US12/338,483
• Publication Number:
  US 20100162402A1
• Time in Patent Office: 1,846 Days
• Field of Search: 705/26, 705/30, 705/50, 705/51
• US Class Current: 726/26
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• 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

Privacy is defined in the context of a guessing game based on the so-called guessing inequality. The privacy of a sanitized record, i.e., guessing anonymity, is defined by the number of guesses an attacker needs to correctly guess an original record used to generate a sanitized record. Using this definition, optimization problems are formulated that optimize a second anonymization parameter (privacy or data distortion) given constraints on a first anonymization parameter (data distortion or privacy, respectively). Optimization is performed across a spectrum of possible values for at least one noise parameter within a noise model. Noise is then generated based on the noise parameter value(s) and applied to the data, which may comprise real and/or categorical data. Prior to anonymization, the data may have identifiers suppressed, whereas outlier data values in the noise perturbed data may be likewise modified to further ensure privacy.

Claims

1. A method, implemented by a processing device, to perform anonymization of data through an application of noise to the data, the anonymization assessed according to a first anonymization parameter and a second anonymization parameter, the method comprising:

determining, by the processing device, a desired level for the first anonymization parameter,

the first anonymization parameter relating to privacy, and

the desired level relating to a minimum privacy;

determining, by the processing device, a range of noise parameter values constrained by the desired level for the first anonymization parameter;

determining, by the processing device and from the range of noise parameter values, a value for a noise parameter of a noise model that optimizes the second anonymization parameter,

the second anonymization parameter relating to distortion;

applying, by the processing device, noise, generated by the noise model based on the determined value of the noise parameter, to the data to provide noise perturbed data,

the noise, when applied to the data, ensuring anonymization performance, according to the first anonymization parameter, that satisfies the desired level; and

providing, by the processing device, the noise perturbed data to another processing device.

2. The method of claim 1, wherein optimization of the second anonymization parameter comprises minimizing a distortion subject to the minimum privacy.

3. The method of claim 1, wherein applying the noise further comprises:

applying the noise to at least one quasi-identifier in the data.

4. The method of claim 1,

wherein the other processing device is associated with a third party.

5. The method of claim 4, further comprising:

modifying outlier data in the noise perturbed data prior to providing the noise perturbed data to the third party.

6. The method of claim 1, further comprising:

suppressing identifiers in the data.

7. The method of claim 1, wherein the noise model is applicable to real attributes in the data.

8. The method of claim 1, wherein the noise model is applicable to categorical attributes in the data.

9. An apparatus for anonymizing data through an application of noise to the data, the anonymization assessed according to a first anonymization parameter and a second anonymization parameter, the apparatus comprising:

a memory to store instructions; and

at least one processor to execute the stored instructions to

determine a desired level for the first anonymization parameter,

the first anonymization parameter relating to privacy, and

the desired level relating to a minimum privacy;

determine a range of noise parameter values constrained by the desired level for the first anonymization parameter;

determine, from the range of noise parameter values, a value for a noise parameter of a noise model that optimizes the second anonymization parameter,

the second anonymization parameter relating to distortion;

apply noise, generated by the noise model based on the determined value of the noise parameter, to the data to provide noise perturbed data,

the noise, when applied to the data, ensuring anonymization performance according to the first anonymization parameter, that satisfies the desired level; and

provide the noise perturbed data to at least one other processor.

10. The apparatus of claim 9, wherein the at least one processor, when determining the value for the noise parameter, is further to:

optimize the second anonymization parameter by minimizing a distortion subject to the minimum privacy.

11. The apparatus of claim 9, wherein the at least one processor, when applying the noise to the data, is further to:

apply the noise to at least one quasi-identifier in the data.

12. The apparatus of claim 9, wherein the

wherein the at least one other processor is associated with a third party.

13. The apparatus of claim 12, wherein the at least one processor is further to:

modify outlier data in the noise perturbed data prior to providing the noise perturbed data to the third party.

14. The apparatus of claim 9, wherein the at least one processor is further to:

suppress identifiers in the data.

15. The apparatus of claim 9, wherein the noise model is applicable to real attributes in the data.

16. The apparatus of claim 9, wherein the noise model is applicable to categorical attributes in the data.

17. A non-transitory computer readable medium storing instructions, the instructions comprising:

one or more instructions which, when executed by at least one processor, cause the at least one processor to;

determine a desired level for a first anonymization parameter,

the first anonymization parameter relating to privacy, and

the desired level relating to a minimum privacy;

determine a range of noise parameter values constrained by the desired level for the first anonymization parameter;

determine, from the range of noise parameter values, a value for a noise parameter of a noise model that optimizes a second anonymization parameter,

the second anonymization parameter relating to distortion;

apply noise, generated by the noise model based on the determined value of the noise parameter, to data to provide noise perturbed data,

the noise, when applied to the data, ensuring anonymization performance according to the first anonymization parameter, that satisfies the desired level; and

provide the noise perturbed data to at least one other processor.

18. The non-transitory computer readable medium of claim 17, wherein the one or more instructions to determine the value for the noise parameter include:

one or more instructions to optimize the second anonymization parameter by minimizing a distortion subject to the minimum privacy.

19. The non-transitory computer readable medium of claim 17, wherein the one or more instructions to apply the noise to the data include:

one or more instructions to apply the noise to at least one quasi-identifier in the data.

20. The non-transitory computer readable medium of claim 17, wherein the at least one other processor is associated with a third party.

21. The non-transitory computer readable medium of claim 17, wherein the instructions further comprise:

one or more instructions to modify outlier data in the noise perturbed data prior to providing the noise perturbed data to the third party.

22. The non-transitory computer readable medium of claim 17, wherein the instructions further comprise:

one or more instructions to suppress identifiers in the data.

23. The non-transitory computer readable medium of claim 17, wherein the noise model is applicable to real attributes in the data.

24. The non-transitory computer readable medium of claim 17, wherein the noise model is applicable to categorical attributes in the data.