Lecture Summaries

These lecture summaries can be viewed as the "past tense" course syllabus. They are intended for people who missed the class, or would like to briefly recall what was going on. Occasionally, I will include brief plan for future lectures, but do not count on it.

The lecture number in the reading section refer to
the **last year's lectures**,
which covered more in 3 hours than we do now
in 2 hours. Please see the actual description to see reading
suggestions.

. The role of randomness in Cryptography. Key generation, privacy, unpredictability, freshness, noise/confusion, efficiency, probabilistically checkable and zero-knowledge proofs, preudorandomness, extraction. Sample e-cash application and its reliance on randomness. Plan for the course.**Lecture 0 (virtual)**

Slides.*Read:*. One-time message authentication codes (MACs). Almost Universal (AU) and Almost XOR Universal (AXU) functions. MACs from AXU. AU/AXU constructions: matrix multiplication, Hankel/Toeplitz, truncated field multiplication, inner product, polynomials. (Almost) Optimal MAC parameters: |tag| = log(n/delta), |key| = 2*log(n/delta).**Lecture 1 (Wed, Jan 29)**

Last year Lecture 1 (sec 1-2).*Read:*. Imperfect (Weak) Randomness and min-entropy. MACs with weak keys. Generic 2^{m-k} perfect->impefect degradation for unpredictability games. Corollary for imperfect MACs: can tolerate entropy k>m/2. Alternative, direct proof using conditional min-entropy. Impossibility of (even one-bit) MACs when entropy k <= m/2.**Lecture 2 (Wed, Feb 5)**

Last year Lecture 1 (sec 2), Last year Lecture 2 (sec 1-2).*Read:*. Collision entropy H_2(R) and its properties. Chain rules: H_2(A,U) = H_2(A|U) + log |U|, H_2(A,B) \ge H_2(A|B) + min-ent(B). Proof that H_2(R) >= 2*log(1/delta) for one-time MACs. Statistical and relative distance, statistical and relative independence/information, basic properties. Definition of statistically/relatively (R,eps)-secure one-time encryption, statement of Generalized Shannon's bounds: relative security implies min-entropy(R) >= n (even with efficient attackers), statistical security implies length(R) >= n (with inefficient attackers).**Lecture 3 (Wed, Feb 12)**

Last year Lecture 2 (sec 3-4), Shannon Impossibility.*Read:*. Proofs of Generalized Shannon's bounds. Corollary: achieving short keys requires computationally bounded attackers AND non-zero advantage. Impossibility of (k,eps)-security for encryption when k < m, even for 1-bit messages. Generalization to most other privacy primitives (commitments, secret sharing, ...).**Lecture 4 (Wed, Feb 19)**

Last year Lecture 2 (sec 4), Shannon Impossibility, Last year Lecture 3 (sec 1-3), Impossibility of crypto with SV sources.*Read:*. (Enhanced) Block sources and Santha-Vazirani (SV) sources. Impossibility of encryption even with SV sources, generalization to other privacy primitives. Extensions to Efficiently Samplable SV sources. MACs with (enhanced) block/SV sources when k <= m/2.**Lecture 5 (Fri, Feb 21)**

Last year Lecture 3 (sec 4-5), Efficient Samplable SV sources, Impossibility of crypto with SV sources.*Read:*. Introduction to**Lecture 6 (Wed, Mar 5)***differential*privacy (DP). eps-DP and rho-accuracy. Lower bound on eps (> 1/n) and rho (> 1/eps). Laplace mechanism for low sensitivity functions. Impossibility of DP with weak sources when k < m - log(rho*eps). Necessary condition for DP with SV sources: consistent sampling.

Last year Lecture 4, DP with Imperfect Randomness (before section 4), Slides.*Read:*. Consistent Sampling and Rounded Laplace mechanism. SV-consistent sampling and feasibility of DP with SV sources. Bias-Control-Limited (BCL) Source. Impossibility of extraction, privacy applications, number of interventions to fix the outcome. Discrete Control Processes. Relation to adaptively secure coin-flipping. Open: stronger impossibility of traditional or feasibility of differential privacy, bounded budget source. Bounded Erasure Source.**Lecture 7 (Wed, Mar 12)**

Last year Lecture 5, DP with Imperfect Randomness (after section 4), Slides, BCL Source, Bounded Erasure Source.*Read:*. Encryption of b bits with n-bit key implies (efficient) eps-extraction of b - log(n) - 2*log(1/eps) bits. n-wise independent hashing and extractors for bounded number of b-sources. Application: almost perfect resilient functions, adaptive exposure-resilient functions. Impossibility of perfect security.**Lecture 8 (Wed, Mar 26)**

Last year Lecture 6, Encryption Implies Extraction (before section 4), Resilient Functions.*Read:*. Generalization to commitments and decryption error. Open: secret sharing. Encryption/extraction Separation for the 1-bit case. High-level overview for (log n) bit counter-example.**Lecture 9 (Wed, Apr 2)**

Last year Lecture 7, Encryption Implies Extraction (section 4), Separation for log n bits.*Read:*. Second half: weak secrets, perfect public/local randomness. Motivating examples. "Passive" vs. "Active" setting. Real/ideal advantage, ideal security, (m-d)-real model. eps' = 2^d*eps degradation for unpredictability applications for min-entropy. Renyi entropy and indistinguishability applications: eps' = sqrt(2^d * sigma) degradation, where sigma is square security. Bounding square security by regular security: simple bound for unpredicatability apps, "double run" trick for CPA encryption. Abstracting double run trick, weak q-PRFs. Special case q=1: extractors and variant of leftover hash lemma.**Lecture 10 (Wed, Apr 9)**

Last year Lecture 8 (first 2 pages), Overcoming Weak Expectations (up to section 3.2).*Read:*. Weak q-wise independent hash functions. Non-malleable extractors for entropy k>m/2 from q=2. Side information. Key Derivation revisited. Condensers for collision and min-entropy. Universal hash functions are H2-condenders. Improved LHL (log(1/e) instead of 2log(1/e) loss).**Lecture 11 (Wed, Apr 16)**

Overcoming Weak Expectations (sections 3.3-4.1), Leftover Hash Lemma, Revisited.*Read:*. Key Derivation for unpredictability applications, min-entropy condensers, unpredictability extractors, balanced hashing and relation among all these primitives (essentially the same). t-wise independent hash functions are balanced => good condensers => good UExtractors => good KDFs. Parameters: entropy loss loglog(1/e) for same security O(e), no entropy loss with e'=O(e*log(1/eps)). Summary of Key Derivation so far: generic LHL (L=2*log(1/e)) < square-friendly (L=log(1/e)) < unpredictability (L=loglog(1/e)+O(1)) < RO (L=0).**Lecture 12 (Wed, Apr 23)**

Last year Lecture 11, Key Derivation Without Entropy Waste (sections 1-4).*Read:*. Optimality: (a) efficient samplability does not help; (b) square-friendly with e' = O(sqrt(e)); (c) unpredictability with e'=O(e*log(1/e)). Computational Extractors. Failure of extract-then-expand for low-entropy. Square-friendly key derivation by 2-weak-PRFs. Construction from PRG. Construction through condensers and dense-model theorem. Open: improve params (match RO?), smooth transition between two proofs, computational condensers. Seed-Dependent (SD) Key Derivation. SD Extractors: (a) impossibility if sampling time > extraction time; (b) constrution using t-wise independence when sampling time << extraction time. SD-condensers: application for key derivation, despite sampling time >> extraction time. SD condensers for Collision entropy (CRHFs). Mention application to Fiat-Shamir (with side info).**Lecture 13 (Wed, Apr 30)**

Last year Lecture 12, Last year Lecture 13 (sec 1-3), Key Derivation Without Entropy Waste (sections 5-6), Slides for Unp. Apps, Overcoming Weak Expectations (sections 4.3, 4.2), Seed-Dependent Condensers, Slides for SD-Cond.*Read:*. Brief Survey of Various topics. Entropic Security and Indistinguishability, equivalence. Invertible extractors and enctropically secure encryption. Sparse one-time pad (deterministic: delta-biased spaces, or probabilistic: variant of LHL). Collision-resistant Extractors and applications: entropic commitment (aka POWHF), weak obfuscation of equality. Construction using crooked LHL and CRHFs. Locally Computable Extractors and Bounded Storage Model (BSM). Sample-then-Extract approach. Fuzzy Extractors and Secure Sketches. Code Offset Construction. Entropically Secure Sketches and Correcting Errors w/o leaking partial info. Private fuzzy extracytors, obfusctation of proximity, fuzzy entropic commitment, key reuse in Noisy BSM. Extractor-MACs and authentication in noisy BSM. Robust Fuzzy Extractors (extending non-fuzzy case). Optimal robust FE in CRS model. Mention of Bounded Retrieval Model (BRM).**Lecture 14 (Fri, May 2)**

*Read:*

Last year Lecture 16, Extractors with Special Properties: Slides and Short Survey.. Privacy Amplification. 1-round protocol via robust extractors. Pre-application vs. post-application robustness. Construction using "mixed" universal/pairwise-independent hash AS+B. Paramemers: k>n/2, number of extracted bit m approx 2k-n (pre-application), m approx k - n/2 (post-application. Necessity for k>n/2 limitation (even with imperfect correctness). Necessity for k>n/2 even for probabilistic non-interactive MACs. Overcoming k>n/2 bound: (a) computational robust extractors (construction in Random Oracle Model beating k > n/2 bound); (b) interaction. Identification and Liveness Tests. 2-round solution with optimal O(log(1/delta)) communication. Message Authentication. 2-round template using Extractors and MACs. Protocol using non-malleable extractor and any MAC: existence of optimal 2-round MACs and constructive solution for k>n/2. [Impossibility of related-key one-time MACs.] Lookahead extractors and MACs: efficient solution for k = Omega(v*log(1/delta)) with O(v*log(1/delta)) communication for v-bit messages. From MACs to privacy amplification: authenticating seed without increasing number of rounds. Post-application robustness, and its implication to improved 2-round MACs and privacy amplification. Recent state-of-the-improvements.**Lecture 15 (Wed, May 7)**

Last year Lecture 14, Robust Extractors (before section III.D), 2-round Key Agreement, Slides.*Read:*

Back to the course page