## Privacy

### Privacy
- Determine when/how/what information is communicated to others
- Aspects
- Right to be let alone
- Self-identity / personal growth
- Protection intimate relationships
- Data privacy: Detect/control data inference
- DB Security: Control access / protect content
- Challenge: Utilize data while protect individuals privacy
- Idea: Anonymize all attributes that could be used for de-anonymization

### Privacy: Risks + Protection
- Problem: Growing availability of information
- Who is allowed to see what?
- Goal: Anonymize data
- Protection technique: Formal models
- Specify privacy model
- Derive conditions
- Design algorithms satisfying privacy conditions
- Example: K-anonymity, L-diversity, L-closeness, (c,k)-safety

### k-Anonymity
- Protection model, ensure anonymity in relational data
- Idea: Generalize, modify, distort identifiers -> no unique identification
- Definition: R(A1, … An), Quasi-identifiers
- R satisfies k-Anonymity <=> each sequence R[QI] at least k times
- Meaning: Matching cannot reduce to fewer than k individuals 
- Large k => higher privacy 
- Find quasi-identifiers: Hard / impossible
- Algorithm (NP-hard)
- Delete cell values / tuples (generalization causes information loss)
- Generalize cell values (quasi-identifiers)

#### Attacks
- Unsorted matching attack:
- Data often sorted, sort data
- Complementary release attack:
- Two data sets, match with problem attribute
- Homogeneity attack:
- Problem attribute for class is same (little diversity)
- Background knowledge attack:
- Very complex attack (knowledge not known)

### L-Diversity
- Prevent homogeneity / background knowledge attack
- Sensitive attributes in a class must be L different values
- No perfect anonymization (Binary attribute hard to achieve, distribution not considered)

#### Curse of Dimensionality
- Data many attributes
- Data sparse
- K nearest neighbors are far away
- Result: Loss of information 

### Sparse data: Deanonymization  
- no quasi-identifiers
- Netflix: K-Anonymization generalization high data loss
- Idea:
- Calculate similarity Netflix and IMDB
- Most similar record is a match
- No record: Candidates also reveal information
- Information:
- political orientation
- Religious views

### Social Networks
- Prediction of intimate information (sexual orientation, ethnicity, religious)
- Interaction tells sth about user
- Goals anonymization
- No identification individuals
- No inference of friendships/interaction
- Secret sensitive attributes
- Re-identification: Graph + background knowledge

#### Social Networks: Advanced anonymization 
- K-anonymization? No changing of neighborhood
- Protect:
- node re-identification
- Edge disclosure
- Sensitive attributes
- Anonymize
- Node degree
- Neighborhood
- Attributes
- Structural knowledge
- Degree distribution
- Goal: Transform to k-degree anonymous graph
- Create degree distribution similar to original one (edges)