Lattice Identity-Based Encryption (IBE) and Attribute-Based Encryption (ABE), then differential privacy

Before ThisWhere Lecture 12 Left Off

Lecture 12 added computation on ciphertexts. Fully-homomorphic encryption was defined by its four algorithms and two requirements, and GSW (Gentry-Sahai-Waters) supplied the concrete scheme: the secret key as an approximate eigenvector of the ciphertext matrix, the gadget matrix carrying the plaintext, noise growing by the gadget factor per multiplicative level. Levelled FHE came from sizing the modulus to a depth bound, and bootstrapping removed the bound by homomorphically evaluating the scheme's own decryption circuit under circular security. One application remains, and then the course moves to its second half.

This LectureWhat It Adds

The first part finishes Chapter 4. Identity-Based Encryption (IBE) removes certificates by letting an identity serve as the public key, with a trusted authority issuing the matching secret keys; Attribute-Based Encryption (ABE) generalizes the access structure so a key corresponds to a policy over attributes. Both are built from learning with errors (LWE) using the trapdoors of Lecture 10. The second part opens Chapter 5. Data exploitation promises correlations, statistics and learning from datasets that describe people. The three opening attacks, the differential attack, the needle in a haystack and the big bang, show that aggregates alone break privacy. Differential privacy is the definition that survives those attacks: neighboring datasets produce output distributions within a factor $e^{\eps}$. The lecture covers the definition and counting queries, the three structural properties, randomized response with its $\ln 3$ parameter, the Laplace mechanism with its sensitivity-scaled noise, and closes with approximate DP and the Gaussian mechanism.

Study PlanWhat to Read, in Lecture Order

1. Chapter 4 §12: Identity-Based Encryption (IBE) and Attribute-Based Encryption (ABE) from lattices. The identity-as-public-key idea, the trusted authority, policy keys and the learning with errors (LWE) construction. This is the last section of Chapter 4.
2. Chapter 5 §1: Data exploitation. The three opening attacks, the NYC taxicab and Netflix de-anonymizations and the lesson that accuracy is the attack surface.
3. §2: The definition. Neighboring datasets, the ratio bound, the three notes and the four counting-query families. Step through the neighboring-datasets stage.
4. §3: Properties. Postprocessing, group privacy and basic composition, each with its short proof via the privacy-loss variable.
5. §4: Randomized response. The two-coin protocol, the $\ln 3$ parameter, the estimator and its Chebyshev bound. Run the lab with a small room and a large one.
6. §5: The Laplace mechanism. The privacy proof by triangle inequality, the tail bound and the multivariate version with $\ell_1$-sensitivity. Run the lab at two epsilons.
7. §6: Approximate Differential Privacy (DP) and the Gaussian mechanism. The $\delta$ relaxation, the Gaussian scale, the privacy-loss distribution and the dimension comparison with Laplace.

PracticeExercises for This Lecture

• Estimate the true fraction from a YES count, the randomized-response estimator on real numbers.
• The privacy loss of generalized randomized response, computing the worst-case ratio at $\eps = 0.1$.
• A Laplace budget, the noise scale and error bound for a fixed dataset size and epsilon.
• Group privacy and composition arithmetic, chaining the definition across rows and across runs.
• The Gaussian scale, computing $\sigma$ from $\Delta_2$, $\eps$ and $\delta$.