CSCI-GA.3220-001 Randomness in
Cryptography (Advanced Cryptography), Spring 2014
Lecturer: Prof. Yevgeniy
Dodis, dodiscs.nyu.edu, (212)
998-3084, room 413, WWH. Office hour: Wed 7-8.
Meeting Time/Place: W 5pm-7pm, room 201, WWH.
Final: course project.
Mailing list: To subscribe to the class list, follow
To post a message to all the list members, send email to
firstname.lastname@example.org. Please, post only messages
interesting to everybody taking the class. Specific class-related
questions and most of your other correspondence should be directed to
Course Homepage: http://cs.nyu.edu/courses/spring14/CSCI-GA.3220-001/index.html
Students are expected to updated the scribe notes from the previous
year in LaTeX. The scribe notes are due by Tuesday
following the Wednesday'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
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.
Below are the current scribe notes in the last semester 3-hour
format. Please see
current syllabus to map these lectures to
the current pace. The lectures below are expected to be
updated/corrected as we move along...
- 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).