Lecture Summaries

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 Handouts and Reading 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 scheme.

• 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 ZK.

• 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 Cycle.

• 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: efficiency.

• 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