Topics Covered:

• Definition of IND-CCA Security
• Application of NIZK: Construction of CCA-secure encryption scheme

Topics Covered:

• IP for Quadratic Non-Residuosity
• Non-interactive ZK
  • NIZK in The Common Random String(CRS) Model
  • Construction in CRS Model: Blum-Feldman-Micali’88 (quadratic residuosity)
  • NIZK for QNR
  • NIZK for 3SAT
• Proofs vs. Argument

Topics Covered:

• Sequential vs Parallel Repetition: reduce soundness error
• Proof of Knowledge
  • PoK of DLOG
• Non-Interactive ZK(NIZK)
  • NIZK in The Random Oracle Model
    • NIZK for 3COL
  • NIZK in The Common Random String Model (Lecture 16)

Topics Covered:

• Perfect ZK Proof for QR Language
• Perfect ZK Proof for Graph Isomorphism
• Comp. ZK Proof for 3Coloring
• All NP Languages have Comp. ZK Proofs
• Commitment Schemes

Topics Covered:

• Zero knowledge, definitions and example
• ZK Proof for QR Language.
  • honest-verifier ZK
  • malicious-verifier ZK

Topics Covered:

• Construction of CRHF from Discrete Log

• Digital Signatures only from OWF

• Direct Constructions:Trapdoor Permutation and the Hash-and-Sign Paradigm.

• Random Oracles.

Today’s topic is Many-time Digital Signatures.

Topics Covered:

• Many-time, stateful, signature schemes.
• Naor-Yung construction: stateless EUF-CMA-secure signature schemes.

Today’s topic is Digital Signatures.

Topics Covered:

• Motivation for Digital Signatures.
• Definition: EUF-CMA Security
• One-time signatures: Lamport’s Scheme.
  • how to sign a single bit, once
  • how to sign $n$ bits, once
• Collision-resistant hashing
  • how to sign polynomially many bits, once.

Topics Covered:

• Quadratic Residue and Quadratic Residuosity Assumption
• Goldwasser-Micali Encryption and Homomorphism
• Diffie-Hellman Key Exchange
• El Gamal Encryption

Topics Covered:

• Public-key Encryption and Key exchange.
• Definitions: IND-Security (IND-CPA)
• Trapdoor permutations.

It is indeed possible for $F(x)$ to leak a lot of information about $x$ even if $F$ is one-way.

The hardcore predicate $B(x)$ represent the specific piece of information about $x$ which is hard to compute given $F(x)$.

Topics Covered:

• Definition of one-way functions (OWF)
• Definition of hardcore bit/predicate (HCB)
• One-way permutations → PRG.
  (In fact, one-way functions → PRG, but that’s a much harder theorem.)
• Goldreich-Levin Theorem: every OWF has a HCB.
  (Proof for an important special case.)

Topics covered:

• Groups, Order of a group and the Order of an element, Cyclic Groups.
• The Multiplicative Group $\mathbb{Z}_N^*$ and $\mathbb{Z}_P^*$ for a prime $P$.
• Generators of $\mathbb{Z}_P^*$.
• Primes, Primality Testing.
• The Discrete Logarithm (DLOG) problem and a candidate OWF.
• Diffie-Hellman assumptions: DDH and CDH.

Topics covered:

• Applications of PRFs

Note: The second half of Lecture 5, Number Theory, is contained in Lecture 6.

Topics:

• Stateless Secret-key Encryption with PRF.
• The Goldreich-Goldwasser-Micali (GGM) PRF construction.

Topics:

• The Hybrid Argument.
• An application: PRG length extension.
• The notion of pseudorandom functions: Definition, motivation, discussion and comparison with PRGs.
• PRG implies (stateful) secret-key encryption.
• PRFs imply (stateless) secret-key encryption.

Science wins either way.

Topics:

• How to circumvent Shannon’s lower bound: the computational adversary
• Definition of computational security
• The definition of pseudorandom generators(PRG)

Everything you’ve ever wanted is on the other side of fear.

Topics:

• Introduction to cryptography
• Secure Communication and Shannon’s definitions of perfect secrecy
• Perfect Indistinguishability definitions.
• The One-time pad construction
• Shannon’s lower bound.