{"id":3323,"date":"2023-12-12T23:01:02","date_gmt":"2023-12-12T14:01:02","guid":{"rendered":"https:\/\/saraheee.com\/?p=3323"},"modified":"2024-03-13T20:18:11","modified_gmt":"2024-03-13T11:18:11","slug":"dp1-database-anonymization","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2023\/12\/dp1-database-anonymization\/","title":{"rendered":"[DP#1] Database anonymization – k-anonymity, l-diversity, t-closeness"},"content":{"rendered":"

k-anonymity<\/strong><\/h2>\n\n\n\n
<\/td>ID<\/td><\/td>QID (Quasi identifiers)<\/td><\/tr>
Name<\/td>Bob<\/td>ZIP<\/td>12345<\/td><\/tr>
Address<\/td>Bobway 42<\/td>Sex<\/td>male<\/td><\/tr>
IP<\/td>127.0.0.1<\/td>Age<\/td>17<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Name<\/td>Age<\/td>Sex<\/td>ZIP<\/td>Disease<\/td><\/tr>
Alice<\/td>28<\/td>F<\/td>23467<\/td>Cancer<\/td><\/tr>
Bob<\/td>17<\/td>M<\/td>12345<\/td>Heart disease<\/td><\/tr>
Charly<\/td>34<\/td>M<\/td>65490<\/td>Flu<\/td><\/tr>
Dave<\/td>41<\/td>M<\/td>84933<\/td>Bronchitis<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Age<\/td>Sex<\/td>ZIP<\/td>Disease<\/td><\/tr>
21-30<\/td>F<\/td>23467<\/td>Cancer<\/td><\/tr>
10-19<\/td>M<\/td>12345<\/td>Heart disease<\/td><\/tr>
31-40<\/td>M<\/td>65490<\/td>Flu<\/td><\/tr>
41-50<\/td>M<\/td>84933<\/td>Bronchitis<\/td><\/tr><\/tbody><\/table>
Still unique!<\/figcaption><\/figure>\n\n\n\n

k-anonymity: an individual’s quasi identifiers have to be equivalent to at least k-1 other individuals
form an equivalence class<\/p>\n\n\n\n

Generalization<\/h4>\n\n\n\n
Age<\/td>Sex<\/td>ZIP<\/td>Disease<\/td><\/tr>
10-29<\/td>F<\/td>23467<\/td>Cancer<\/td><\/tr>
10-29<\/td>M<\/td>12345<\/td>Heart disease<\/td><\/tr>
30-49<\/td>M<\/td>65490<\/td>Flu<\/td><\/tr>
30-49<\/td>M<\/td>84933<\/td>Bronchitis<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

e.g., generalize the age to intervals of 20,
we can see that the first two cells are equal and the second two cells are equal<\/p>\n\n\n\n

k = 2 anonymity in Age<\/p>\n\n\n\n

Suppression<\/h4>\n\n\n\n
Age<\/td>Sex<\/td>ZIP<\/td>Disease<\/td><\/tr>
10-29<\/td>*<\/td>[10000-29999]<\/td>Cancer<\/td><\/tr>
10-29<\/td>*<\/td>[10000-29999]<\/td>Heart disease<\/td><\/tr>
30-49<\/td>M<\/td>[60000-89999]<\/td>Flu<\/td><\/tr>
30-49<\/td>M<\/td>[60000-89999]<\/td>Bronchitis<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

always have to weigh the Utility of the data against the Disclosure risk
important concept to understand before dealing with more sophisticated concepts, such as differential privacy<\/p>\n\n\n\n

I-diversity<\/strong><\/h2>\n\n\n\n

extends on the concept of k-anonymity and addresses some privacy issues that remain after k-anonymity is applied to protect a database from attacks
if the data is not diverse, individuals can still be identified<\/p>\n\n\n\n

Name<\/td>Age<\/td>ZIP<\/td>Disease<\/td><\/tr>
Alice<\/td>29<\/td>47677<\/td>Heart Disease<\/td><\/tr>
Bob<\/td>22<\/td>47602<\/td>Heart Disease<\/td><\/tr>
Charly<\/td>27<\/td>47678<\/td>Heart Disease<\/td><\/tr>
Dave<\/td>43<\/td>47905<\/td>Flu<\/td><\/tr>
Eve<\/td>52<\/td>47909<\/td>Heart Disease<\/td><\/tr>
Ferris<\/td>47<\/td>47906<\/td>Cancer<\/td><\/tr>
George<\/td>30<\/td>47605<\/td>Heart Disease<\/td><\/tr>
Harvey<\/td>36<\/td>47673<\/td>Cancer<\/td><\/tr>
Iris<\/td>32<\/td>47607<\/td>Cancer<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Age<\/td>ZIP<\/td>Disease<\/td><\/tr>
2*<\/td>476**<\/td>Heart Disease<\/td><\/tr>
2*<\/td>476**<\/td>Heart Disease<\/td><\/tr>
2*<\/td>476**<\/td>Heart Disease<\/td><\/tr>
40-50<\/td>4790*<\/td>Flu<\/td><\/tr>
40-50<\/td>4790*<\/td>Heart Disease<\/td><\/tr>
40-50<\/td>4790*<\/td>Cancer<\/td><\/tr>
3*<\/td>476**<\/td>Heart Disease<\/td><\/tr>
3*<\/td>476**<\/td>Cancer<\/td><\/tr>
3*<\/td>476**<\/td>Cancer<\/td><\/tr><\/tbody><\/table>
without Salary, k = 3<\/figcaption><\/figure>\n\n\n\n

3-diverse: three sensitive values within 2 class
2-diverse: two represented values within 3 class
we cannot do anything for the first equivalence class, as we would have to eliminate this equivalence class if we would want to have 2-diversity for the database<\/p>\n\n\n\n

Name<\/td>Age<\/td>ZIP<\/td>Salary<\/td>Disease<\/td><\/tr>
Alice<\/td>29<\/td>47677<\/td>3K<\/td>Gastric ulcer<\/td><\/tr>
Bob<\/td>22<\/td>47602<\/td>4K<\/td>Gastritis<\/td><\/tr>
Charly<\/td>27<\/td>47678<\/td>5K<\/td>Stomach cancer<\/td><\/tr>
Dave<\/td>43<\/td>47905<\/td>6K<\/td>Gastritis<\/td><\/tr>
Eve<\/td>52<\/td>47909<\/td>11K<\/td>Flu<\/td><\/tr>
Ferris<\/td>47<\/td>47906<\/td>8K<\/td>Bronchitis<\/td><\/tr>
George<\/td>30<\/td>47605<\/td>7K<\/td>Bronchitis<\/td><\/tr>
Harvey<\/td>36<\/td>47673<\/td>9K<\/td>Pneumonia<\/td><\/tr>
Iris<\/td>32<\/td>47607<\/td>10K<\/td>Stomach cancer<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Age<\/td>ZIP<\/td>Salary<\/td>Disease<\/td><\/tr>
2*<\/td>476**<\/td>3K<\/td>Gastric ulcer<\/td><\/tr>
2*<\/td>476**<\/td>4K<\/td>Gastritis<\/td><\/tr>
2*<\/td>476**<\/td>5K<\/td>Stomach cancer<\/td><\/tr>
>40<\/td>4790*<\/td>6K<\/td>Gastritis<\/td><\/tr>
>40<\/td>4790*<\/td>11K<\/td>Flu<\/td><\/tr>
>40<\/td>4790*<\/td>8K<\/td>Bronchitis<\/td><\/tr>
3*<\/td>476**<\/td>7K<\/td>Bronchitis<\/td><\/tr>
3*<\/td>476**<\/td>9K<\/td>Pneumonia<\/td><\/tr>
3*<\/td>476**<\/td>10K<\/td>Stomach cancer<\/td><\/tr><\/tbody><\/table>
without Salary, k = 3<\/figcaption><\/figure>\n\n\n\n

3-anonymity, 3-diversity<\/p>\n\n\n\n

l-diversity does not care about semantics<\/p>\n\n\n\n

t-closeness<\/strong><\/h2>\n\n\n\n

Salary = {3k, 4k, 5k, 6k, 7k, 8k, 9k, 10k, 11k}
P1 = {3k, 4k, 5k}, P2 = {6k, 8k, 11k}<\/p>\n\n\n\n

Earth Mover’s distance<\/p>\n\n\n\n

Ordered distance \\(D_O = \\frac{|i-j|}{n-1}\\)<\/p>\n\n\n\n

11-5 + 10-5 + 9-5 + 8-4 + 7-4 + 6-4 + 5-3 + 4-3 = 27
27 \/ 8 = 3.375
3.375 \/ 9 = 0.375: optimal mass flow<\/p>\n\n\n\n

D[P1, Q] = 0.375, D[P2, Q] = 0.167<\/p>\n\n\n\n

{Gastric ulcer, Gastritis, Stomach cancer, Flu, Pneumonia, Bronchitis}
P1 = {Gastric ulcer, Gastritis, Stomach cancer} – (3×1)\/6 = 0.5
P2 = {Gastric ulcer, Stomach cancer, Pneumonia} – (1\/3 + 1\/3 + 1)\/6 = 0.278<\/p>\n\n\n\n

<\/p>\n\n\n\n

Age<\/td>ZIP<\/td>Salary<\/td>Disease<\/td><\/tr>
20-40<\/td>4767*<\/td>3K<\/td>Gastric ulcer<\/td><\/tr>
20-40<\/td>4767*<\/td>9K<\/td>Pneumonia<\/td><\/tr>
20-40<\/td>4767*<\/td>5K<\/td>Stomach cancer<\/td><\/tr>
40-60<\/td>4790*<\/td>6K<\/td>Gastritis<\/td><\/tr>
40-60<\/td>4790*<\/td>11K<\/td>Flu<\/td><\/tr>
40-60<\/td>4790*<\/td>8K<\/td>Bronchitis<\/td><\/tr>
20-40<\/td>4760*<\/td>7K<\/td>Bronchitis<\/td><\/tr>
20-40<\/td>4760*<\/td>10K<\/td>Stomach cancer<\/td><\/tr>
20-40<\/td>4760*<\/td>4K<\/td>Gastritis<\/td><\/tr><\/tbody><\/table>
3-anonymity, 3-diversity
0.167-close (salary), 0.278-close (disease)<\/figcaption><\/figure>\n\n\n\n

Differential Privacy explained<\/h2>\n\n\n\n

data gets perturbed
noise added to the data on the server
global or centralized differential privacy<\/p>\n\n\n\n

Name<\/td>Age<\/td>ZIP<\/td>Salary<\/td>Disease<\/td><\/tr>
Alice<\/td>29<\/td>47677<\/td>3K<\/td>Gastric ulcer<\/td><\/tr>
Bob<\/td>22<\/td>47602<\/td>4K<\/td>Gastritis<\/td><\/tr>
Charly<\/td>27<\/td>47678<\/td>5K<\/td>Stomach cancer<\/td><\/tr>
Dave<\/td>43<\/td>47905<\/td>6K<\/td>Gastritis<\/td><\/tr>
Eve<\/td>52<\/td>47909<\/td>11K<\/td>Flu<\/td><\/tr>
Ferris<\/td>47<\/td>47906<\/td>8K<\/td>Bronchitis<\/td><\/tr>
George<\/td>30<\/td>47605<\/td>7K<\/td>Bronchitis<\/td><\/tr>
Harvey<\/td>36<\/td>47673<\/td>9K<\/td>Pneumonia<\/td><\/tr>
Iris<\/td>32<\/td>47607<\/td>10K<\/td>Stomach cancer<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Age<\/td>ZIP<\/td>Salary<\/td>Disease<\/td><\/tr>
20-40<\/td>4767*<\/td>3K<\/td>Gastric ulcer<\/td><\/tr>
20-40<\/td>4767*<\/td>9K<\/td>Pneumonia<\/td><\/tr>
20-40<\/td>4767*<\/td>5K<\/td>Stomach cancer<\/td><\/tr>
40-60<\/td>4790*<\/td>6K<\/td>Gastritis<\/td><\/tr>
40-60<\/td>4790*<\/td>11K<\/td>Flu<\/td><\/tr>
40-60<\/td>4790*<\/td>8K<\/td>Bronchitis<\/td><\/tr>
20-40<\/td>4760*<\/td>7K<\/td>Bronchitis<\/td><\/tr>
20-40<\/td>4760*<\/td>10K<\/td>Stomach cancer<\/td><\/tr>
20-40<\/td>4760*<\/td>4K<\/td>Gastritis<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

improve our data subjects’ privacy by applying differential privacy to the salary
how do we apply the noise?<\/p>\n\n\n

\n
\"\"<\/figure><\/div>\n\n\n


epsilon: privacy parameter of differential privacy
improve our data subjects’ privacy by applying differential privacy to the salary
how do we apply the noise?<\/p>\n\n\n\n

Age<\/td>ZIP<\/td>Salary<\/td><\/td>Disease<\/td>Noise<\/td><\/tr>
20-40<\/td>4767*<\/td>3K<\/td>4K<\/td>Gastric ulcer<\/td>1<\/td><\/tr>
20-40<\/td>4767*<\/td>9K<\/td>11K<\/td>Pneumonia<\/td>2<\/td><\/tr>
20-40<\/td>4767*<\/td>5K<\/td>5K<\/td>Stomach cancer<\/td>0<\/td><\/tr>
40-60<\/td>4790*<\/td>6K<\/td>3K<\/strong><\/td>Gastritis<\/td>-6<\/strong><\/td><\/tr>
40-60<\/td>4790*<\/td>11K<\/td>11K<\/td>Flu<\/td>0<\/td><\/tr>
40-60<\/td>4790*<\/td>8K<\/td>8K<\/td>Bronchitis<\/td>0<\/td><\/tr>
20-40<\/td>4760*<\/td>7K<\/td>6K<\/td>Bronchitis<\/td>-1<\/td><\/tr>
20-40<\/td>4760*<\/td>10K<\/td>15K<\/strong><\/td>Stomach cancer<\/td>5<\/td><\/tr>
20-40<\/td>4760*<\/td>4K<\/td>4K<\/td>Gastritis<\/td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Noise can also be so large that values can become negative
Global or Centralized DP
noisy mean salary = 7.44<\/p>\n\n\n\n

Randomized Response<\/h4>\n\n\n\n

the idea is trivial: the participant flips a coin
randomized response gives 75% chance of the answer being the actual answer with 25% of being the wrong one<\/p>\n\n\n\n

Differential privacy: a technique that wanders around the edges of utility and privacy<\/p>\n\n\n\n

Crypto Shredding explained<\/h2>\n\n\n\n

Name: Bob
Address: Bobway 42
ZIP: 12345
Sex: male
Age: 17<\/p>\n\n\n\n

Name<\/td>Age<\/td>Sex<\/td>ZIP<\/td>Address<\/td><\/tr>
Alice<\/td>28<\/td>F<\/td>23467<\/td>Alice road 20<\/td><\/tr>
Bob<\/td>17<\/td>M<\/td>12345<\/td>Bobway 42<\/td><\/tr>
Charly<\/td>34<\/td>M<\/td>65490<\/td>Charly Avenue 137<\/td><\/tr>
Dave<\/td>41<\/td>M<\/td>84933<\/td>Dave street 98<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Name<\/td>Key<\/td><\/tr>
Alice<\/td>209fwefjs0f9fSEwf0f8h<\/td><\/tr>
Bob<\/td>ae09ffjvnxcvdsgertEWE<\/td><\/tr>
Charly<\/td>99dfjsd9f0safjssfaaWEEF<\/td><\/tr>
Dave<\/td>sdfoicnvnynvre8u8WEW<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

analyst <\/> – (Cache DB – Encrypted DB – Keys) – Cache builder
Cache builder: obviously first the keys decrypt the data and encrypted data from the encrypted database
Cache builder – Keys
Cache DB – analyst: query + read
analyst \u2192 Encrypted DB: write
analyst – Keys<\/p>\n\n\n\n

<\/p>\n\n\n\n

References<\/h3>\n\n\n\n