Randomness in Cryptography, Spring 2013

LaTeX. The scribe notes are due by Wednesday following the Thursday's lecture.
Please use preamble.tex (including relevant macros) and appropriately modify the sample lecture1.tex (renaming it with right lecture number and topic, putting your name, defining new macros, etc.).
You should send me lecture?.tex, lecture?.pdf. In case you edited preamble.tex, please also send it to me, but make sure you only ADD to it, since I want all the lectures to compile with the same preamble file.

• Lecture 0: Role of Randomness in Cryptography.
• Lecture 1: One-Time MACs, (XOR) Universal hashing, Min-entropy, Weak Keys.
• Lecture 2: Optimality of One-time MACs and Shannon Impossibility.
• Lecture 3: Impossibility of Privacy with Weak Sources.
• Lecture 4: Differential Privacy with Weak Sources.
• Lecture 5: SV-robust Mechanisms and Bias-Control-Limited Source.
  • Summary Slides for Lectures 4-5
• Lecture 6: Encryption => Extraction, Bit-Fixing Source.
• Lecture 7: Privacy => Extraction, Separation for short messages.
• Lecture 8: Cryptography with Weak Keys but Perfect Local Randomness.
• Lecture 9: Overcoming Weak Expectations. (until section 3.2)
• Lecture 10: NM Extractors, Condensers, Crooked LHL, Improved LHL. (sections 3.3-4.1)
• Lecture 11: Min-entropy Condensers, Unpredictability Extractors, Key Derivation.
• Lecture 12: Optimality of I.T. Key Derivation, Computational Extractors, Dense Model.
  • Summary Slides for Lectures 9-12
• Lecture 13: Seed-Dependent Condensers and Key Derivation.
  • Slides for Seed-Dependent Condensers
• Lecture 14: Robust Extractors and Their Limitations.
• Lecture 15: Privacy Amplication against Active Attackers.
  • Slides for 2-round protocols
• Lecture 16: Entropic Security, Fuzzy Extractors, Bounded Storage Model.
  • Summary Slides

---

Brief Course Description:

We will cover a variety of topics (see the list below) revolving around randomization, entropy, information-theoretic crypto, extractors and (time permitting) leakage-resilient cryptography.

• (im)possibility of authentication with weak sources
• impossibility on basing privacy on entropy alone
• encryption => extraction
• differential privacy with SV sources
• using public randomess
• extractors (LHL, etc)
• "square-friendly" privacy applications
• randomness condensers
• robust extractors
• fuzzy extractors
• entropic security and privacy (incl. private fuzzy extractors)
• privacy amplification and non-malleable extractors
• locally computable extractors, bounded storage/retrieval model
• computational (HILL, unpredictability) entropy and computational extractors
• dense model theorem
• randomized MACs
• time permitting, leakage-resilient cryptography (many topics).

---