The descriptions below will summarize what we did up to now and
might give the plan for the upcoming lecture. It might also suggest
reading material for a given lecture. Make sure you also check the
sections for other handouts and suggested reading.
- Lecture 1
(Wed, Sep 9).
Identification problem. Dimension 1: secure verifier storage?
Dimension 2: secure Communitation? Dimension 3: partially compromised
prover's storage (leakage-resilience)? Password Authentication
(insecure storage, secure communication). Solution using OWFs.
Leakage-resilient password authentication and OWFs, from SPR hash
functions. Constructions of SPR hash functions (from OWFs and CRHFs).
Symmetric-Key ID Schemes (secure storage, insecure
communication). Active vs. passive attacks.
- Lecture 2
(Wed, Sep 16).
Symmetric-Key ID schemes based on symmetric encrytion and symmetric
message authentication. Instantiations (PRP, XOR encryption, CBC-MAC,
HMAC). Public-Key ID schemes. Schnorr's protocol. Properties: special
HVZK and special soundness. Special soundness implies Proof of
Knowledge (PoK). Simple rewinding extractor (advantage = eps*eps, time
= 2). More efficient extractor (advantage = 1/2, time = 1/eps).
- Lecture 3
(Wed, Sep 23).
Sigma protools. Sigma protocols for OWFs give passive ID schemes. GQ
protocol for RSA. Leakage-resilient (LR) passive ID scheme from Sigma
protocols for LR OWFs. Witness indistinguishability (WI).
Sigma-prtocols imply WI. Sigma protocols for SPR functions give
actively secure (and leakage-resilient!) ID schemes. Okamoto's ID
- Lecture 4
(Wed, Sep 30).
OR proofs. Applications to actively secure ID schemes, anonymous
resource sharing, ``off-the-record'' designated verifier proofs and
communication. Trapdoor Commitments (TCs) from Sigma
protocols. Pedersen's commitment. Leakage-Resilient TCs.
Applications: on-line/off-line signatures, chameleon signatures.
- Lecture 5
(Wed, Oct 7).
Collision-Resistant Hash Functions from Sigma-protocols with strong
HVZK property. One-time Signatures from Sigma-protocols for SPR
functions. Leakage-Resilient One-time Signatures when Sigma-protocol
has strong HVZK property. Fiat-Shamir transformation. Proof of
security in the Random Oracle Model. (Un)soundness of FS-signatures in
standard model (Goldwasser-Kalai). Introduction to and definition of
- Lecture 6
(Wed, Oct 14).
Definition of ZK proofs/arguments. Importance or prover/verifier
randomness. Connection between ZK of Sigma-protocols with large
challenge space and soundness of Fiat-Shamir. ZK of Sigma-protocols
with small challenge spaces. Impossibility of 3/4-round black-box ZK
proofs/argument. Close under sequential compossition, (non)-closure
under parallel composition. 4/5-round ZK argument/proof using
commitments. Less efficient ZK argument using trapdoor commitments.
- Lecture 7
(Wed, Oct 21).
Zk argument from trapdoor commitments (from last class).
Witness-hiding (WH) proofs. Constructions from SPR and OR proofs.
Concurrent ZK in the CRS model. Sigma-protocol for all of NP
(Hamiltonian Cycle). Non-interactive ZK (NIZK). NIZK in RO model via
Fiat-Shamir. Loss of Deniability.
- Lecture 8
(Wed, Oct 28).
Non-programmable RO. Extractable Commitments in NP-RO model.
Straightline extractable proofs (Omega-protocols) in NP-RO
model. Construction from Sigma protocols. 2-round partially-deniable
(concurrent) ZK in NP-RO in 2-rounds. NIZK in the CRS model. Insist on
oblivious CRS (indep. of input). Olivious vs. same-string NIZK:
oblivious argument <=> same-string argument, same-string proofs
impossible. Inefficient-prover perfecrt NIZK proof for Hamiltonian
- Lecture 9
(Wed, Nov 4).
Efficient-prover (oblivious) NIZK proof for HC using trapdoor hard
predicates (implies by TDPs, mention ones from bilinear groups).
Adaptive-ZK and Adaptive Soundness. Genetic way to get adaptive
soundness, adaptive-ZK (ok due to oblivious CRS). Unbounded
(multiple-theorems with same CRS) and Composable (ok even with
trapdoor) ZK. Composable => Unbounded. Construction using OR trick.
Making CRS of fixed size (using circuit-SAT). Outcome: composable (=>
unbounded) oblivious NIZK with fixed size CRS.
- Lecture 10
(Wed, Nov 11).
Simulation-sound NIZK proofs. One-time SS-NIZK. Construction from
one-time signatures, commitments and one-time NIZK. Application: CCA
encryption from CPA encryption. DDN construction using one-time NIZK
and one-time signatures. NY construction using one-time SS-NIZK.
- Lecture 11
(Wed, Nov 18).
Towards efficint CCA encryption. Designated-Verifier (DV) t-time
SS-NIZK. (t+1)-Universal Hash Proof Systems (HPS). (t+1)-universal HPS
imply t-time DV-SS-NIZK. Constructing 1-universal and 2-universal HPS
for DDH language (g1,g2,(g1)^r,(g2)^r). Adding label support for
1-time SS. NY with 1-DV-SS-NIZK, example with ElGamal. Simplification
using any language L with ``hard membership'' problem having
1-universal HPS (for encapsulated key) and 2-universal labeled HPS
(for the 1-DV-SS-NIZK). Example: apply to DDH language => Cramer-Shoup
scheme. Formal Proof of CCA security.
- Lecture 12
(Wed, Nov 25).
Leakage-resilient (LR) CCA encryption. Direct proof for HPS-based CCA
schemes. Two options: using implicit extractors vs. explicit
extractors. Applying to CS encryption. Towards higher leakage: Using
HPS for high-leakage LR-CPA schemes. Example from DDH with more
generators (mention others). LR-CCA from LR-CPA: NY works! Variant
(a): LR-CPA + CPA + 1-SS-NIZK. Variant (b): LR-CPA + CCA (with labels)
+ one-time-sigs + NIZK. Open: efficient high-leakage CCA schemes.
KEM-DEM approach (w/o leakage). Kurosawa-Desmedt: push more to
symmetric side, use SS-proof itself as key and rely on authenticated
symmetric encryption. Final KPSY encryption using 1-universal HPS (for
DDH language) and 4-wise independent hash functions. LR case open.
- Lecture 13
(Mon, Nov 30).
Signatures from MACs, commitments and NIZK. Proofs of Knowledge (PoK),
weak and (strong) Simulation Extractability (SE). Constructions: (a)
PoK from CPA encryption and NIZK; (b) wSE-NIZK from CCA encryption and
NIZK; (c) SE-NIZK from CPA encryption and Simulation-Sound NIZK
(SS-NIZK). SS-NIZK from NIZK via OR proofs using: (1) CCA encryption;
(2) commitments, PRFs and one-time signatures. Signatures from
wSE-NIZK and OWFs. LR-Signatures from LR-OWFs (e.g., SPRFs). Open:
- Lecture 14
(Wed, Dec 9).
Introduction to Real/Ideal paradigm and UC security. Ideal
functionality for ZK. Any ZK PoK protocol realizes ZK functionality
without UC. Impossibility of UC ZK in plain model. The CRS model and
two views: (1) fresh CRS and (2) re-usable CRS. Any NIZK PoK
UC-realizes ZK in fresh CRS model, any wSE NIZK UC-realizes ZK in
re-usable CRS model. Efficient interactive protocols to realize UC ZK:
from Omega protocol and any trapdoor commitment in the fresh CRS
model, from Omega protocol and Identity-Based Trapdoor Commitment in
the re-usable model. Construction of Identity-Based Trapdoor
Commitments from Sigma protocols and Signature schemes.
Last modified: December 17, 2009