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 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 (Mon, Jan 7)**

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). 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.**Lecture 1 (Thu, Jan 10)**. Impossibility of (even one-bit) MACs when entropy k <= m/2. Collision entropy H_2(R). Proof that H_2(R) >= 2*log(1/delta). Statistical and relative distance, statistical and relative independence/information, basic properties. Definition of statistically/relatively (R,eps)-secure one-time encryption. Genaralizations of Shannon's bound: relative security implies min-entropy(R) >= n (even with efficient attackers), statistical security implies length(R) >= n (with inefficient attackers). Corollary: achieving short keys requires bounded attackers AND non-zero advantage.**Lecture 2 (Thu, Jan 17)**

Shannon Impossibility.*Read:*. Impossibility of (k,eps)-security for encryption when k < m, even for 1-bit messages. Generalization to most other privacy primitives. (Enhanced) Block sources and Santha-Vazirani (SV) sources. Impossibility of encryption even with SV sources, generalization to other privacy primitives. MACs with (enhanced) block/SV sources when k <= m/2.**Lecture 3 (Thu, Jan 24)**

Impossibility of crypto with SV sources.*Read:*. Introduction to**Lecture 4 (Thu, Jan 31)***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.

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, 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 5 (Thu, Feb 7)**

DP with Imperfect Randomness (after section 4), Slides, 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 6 (Thu, Feb 14)**

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 7 (Thu, Feb 21)**

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. Overview of topics (extractors, condensers, privacy amplification, robustness, reusability/unlinkability, fuzziness). Use of local randomness for CPA/CCA encryption, MACs, signatures, especially coupled with interaction. Interactive 2-round iCCA from CPA, 2-round iCMA from CCA. Probilistic MACs (using XOR-universal hashing, CCA encryption).**Lecture 8 (Mon, Feb 25)**. 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 9 (Thu, Mar 14)**

Overcoming Weak Expectations (until 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). Crooked LHL. Application to saving private randomness in OWFs.**Lecture 10 (Thu, Mar 21)**

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 2*loglog(1/e) for same security O(e), no entropy loss with e'=O(e*log(1/eps)).**Lecture 11 (Thu, Mar 28)**

Key Derivation Without Entropy Waste (before section 4).*Read:*. 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). 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, smooth transition between two proofs.**Lecture 12 (Thu, Apr 4)**

Key Derivation Without Entropy Waste (sections 5-6), Overcoming Weak Expectations (section 4.3), Slides.*Read:*. 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), weak implications for min-entropy SD condensers (open: better min-entropy SD condensers). Side Information: importance and impossibility. Overcoming impossibility: SD condensers for side information. Application to Fiat-Shamir (public-coin proofs -> 2-round public-coin arguments). Distributional Collision-Resistance.**Lecture 13 (Thu, Apr 11)**

Overcoming Weak Expectations (section 4.2), Seed-Dependent Condensers, Slides*Read:*. 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. Computational robust extractors. Construction in Random Oracle Model beating k > n/2 bound.**Lecture 14 (Thu, Apr 18)**

Robust Extractors (before section III.D).*Read:*. Overcoming k>n/2 bound: (a) computational robust extractors; (b) interaction (Privacy Amplification). Identification and Liveness Tests. 2-round solution with optimal O(log(1/delta)) communication. 2-source extractors and liveness tests with weak seeds. 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 (Thu, Apr 25)**

2-round Key Agreement, Slides*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 16 (Thu, May 2)**

Extractors with Special Properties: Slides and Short Survey.*Read:*

Back to the course page