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.
Read:
Shannon Impossibility.
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.
Read:2-round Key
Agreement, Slides
Lecture 16 (Thu, May 2).
Brief Survey of Various topics. Entropic Security and
Indistinguishability, equivalence. Invertible extractors and
enctropically secure encryption. Sparse one-time pad (deterministic:
delta-biased spaces, or probabilistic: variant of
LHL). Collision-resistant Extractors and applications: entropic
commitment (aka POWHF), weak obfuscation of equality. Construction
using crooked LHL and CRHFs. Locally Computable Extractors and
Bounded Storage Model (BSM). Sample-then-Extract approach. Fuzzy
Extractors and Secure Sketches. Code Offset
Construction. Entropically Secure Sketches and Correcting Errors w/o
leaking partial info. Private fuzzy extracytors, obfusctation of
proximity, fuzzy entropic commitment, key reuse in Noisy
BSM. Extractor-MACs and authentication in noisy BSM. Robust Fuzzy
Extractors (extending non-fuzzy case). Optimal robust FE in CRS
model. Mention of Bounded Retrieval Model (BRM).
Read:
Extractors with Special Properties:
Slides and
Short Survey.