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.
• Lecture 0 (Mon, Jan 7). 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.
Slides.

• Lecture 1 (Thu, Jan 10). 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 2 (Thu, Jan 17). 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 3 (Thu, Jan 24). 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.
Read: Impossibility of crypto with SV sources.

• Lecture 4 (Thu, Jan 31). 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: DP with Imperfect Randomness (before section 4), Slides.

• Lecture 5 (Thu, Feb 7). 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.
Read: DP with Imperfect Randomness (after section 4), Slides, Bounded Erasure Source.

• Lecture 6 (Thu, Feb 14). 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: Encryption Implies Extraction (before section 4), Resilient Functions.

• Lecture 7 (Thu, Feb 21). 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: Encryption Implies Extraction (section 4), Separation for log n bits.

• Lecture 8 (Mon, Feb 25). 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 9 (Thu, Mar 14). 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: Overcoming Weak Expectations (until section 3.2).

• Lecture 10 (Thu, Mar 21). 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.
Read: Overcoming Weak Expectations (sections 3.3-4.1), Leftover Hash Lemma, Revisited.

• Lecture 11 (Thu, Mar 28). 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)).
Read: Key Derivation Without Entropy Waste (before section 4).

• Lecture 12 (Thu, Apr 4). 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.
Read: Key Derivation Without Entropy Waste (sections 5-6), Overcoming Weak Expectations (section 4.3), Slides.

• Lecture 13 (Thu, Apr 11). 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.
Read: Overcoming Weak Expectations (section 4.2), Seed-Dependent Condensers, Slides

• Lecture 14 (Thu, Apr 18). 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.
Read: Robust Extractors (before section III.D).

• Lecture 15 (Thu, Apr 25). 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.