Randomness in Cryptography, Spring 2013, Lecture Summaries

# Randomness in Cryptography, Spring 2013 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.

• Lecture 0 (virtual). 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 1 (Wed, Jan 29). 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).
Read: Last year Lecture 1 (sec 1-2).

• Lecture 2 (Wed, Feb 5). 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.
Read: Last year Lecture 1 (sec 2), Last year Lecture 2 (sec 1-2).

• Lecture 3 (Wed, Feb 12). 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).
Read: Last year Lecture 2 (sec 3-4), Shannon Impossibility.

• Lecture 4 (Wed, Feb 19). 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, ...).
Read: Last year Lecture 2 (sec 4), Shannon Impossibility, Last year Lecture 3 (sec 1-3), Impossibility of crypto with SV sources.

• Lecture 5 (Fri, Feb 21). (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.
Read: Last year Lecture 3 (sec 4-5), Efficient Samplable SV sources, Impossibility of crypto with SV sources.

• Lecture 6 (Wed, Mar 5). Introduction to 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.
Read: Last year Lecture 4, DP with Imperfect Randomness (before section 4), Slides.

• Lecture 7 (Wed, Mar 12). 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.
Read: Last year Lecture 5, DP with Imperfect Randomness (after section 4), Slides, BCL Source, Bounded Erasure Source.

• Lecture 8 (Wed, Mar 26). 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.
Read: Last year Lecture 6, Encryption Implies Extraction (before section 4), Resilient Functions.

• Lecture 9 (Wed, Apr 2). 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.
Read: Last year Lecture 7, Encryption Implies Extraction (section 4), Separation for log n bits.

• Lecture 10 (Wed, Apr 9). 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.
Read: Last year Lecture 8 (first 2 pages), Overcoming Weak Expectations (up to section 3.2).

• Lecture 11 (Wed, Apr 16). 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).
Read: Overcoming Weak Expectations (sections 3.3-4.1), Leftover Hash Lemma, Revisited.

• Lecture 12 (Wed, Apr 23). 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).
Read: Last year Lecture 11, Key Derivation Without Entropy Waste (sections 1-4).

• Lecture 13 (Wed, Apr 30). 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).
Read: 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.

• Lecture 14 (Fri, May 2). 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).