#

##
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
instructions at

To post a message to all the list members, send email to `
csci_ga_3220_001_sp14@cs.nyu.edu`. Please, post only messages *
interesting to everybody taking the class*. Specific class-related
questions and most of your other correspondence should be directed to
the instructor.

**Course Homepage:** `http://cs.nyu.edu/courses/spring14/CSCI-GA.3220-001/index.html`

### Scribe Notes:

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*.

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*.
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
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.
- 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.
- Lecture 13: Seed-Dependent Condensers and
Key Derivation.
- Lecture 14: Robust Extractors and Their
Limitations.
- Lecture 15: Privacy Amplication against
Active Attackers.
- 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
extractors
- dense model theorem
- randomized MACs
- time permitting, leakage-resilient cryptography (many topics).