Lecturer: Prof. Yevgeniy
Course Homepage: http://cs.nyu.edu/~dodis/randomness-in-crypto/index.html
Students are expected to scribe a couple of lectures
in LaTeX. The scribe notes are due by Wednesday
following the Thursday's lecture.
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
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
- Lecture 3: Impossibility of Privacy with
- Lecture 4: Differential Privacy with Weak
- Lecture 5: SV-robust Mechanisms and
- Lecture 6: Encryption => Extraction,
- Lecture 7: Privacy => Extraction,
Separation for short messages.
- Lecture 8: Cryptography with Weak Keys but
Perfect Local Randomness.
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.
- Lecture 13: Seed-Dependent Condensers and
- Lecture 14: Robust Extractors and Their
- Lecture 15: Privacy Amplication against
- Lecture 16: Entropic Security, Fuzzy
Extractors, Bounded Storage Model.
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
- dense model theorem
- randomized MACs
- time permitting, leakage-resilient cryptography (many topics).