# 「Cryptography-MIT6875」: Lecture 17

**Topics Covered: **

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

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

- NIZK in The Random Oracle Model

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