## Syllabus

- Introduction [Ch1] [KL 1,2]
- Introduction & Overview
- Information Theoretic Security
Shannon’s Definition of security. One-time Pads. Limitations of the Information Theoretic Approach.

- Computational Hardness and One-wayness [Ch2] [KL 3.1,7]
- One-way Functions and Computationally bounded adversaries.
Randomized Efficient Algorithms. One-way functions (OWF). Weak and Strong OWFs.

- Computational Number Theory.
Euclid’s Algorithm, Modular Exponentiation, Basic group

theory, Euler’s and Fermat’s Theorems, Primes. - Computational Hardness.

Factoring assumption and

the Discrete log assumptions. One way permutation

and Trapdoor permutations. - Collections of OWFs.

- Indistinguishability and Pseudo-Randomness [Ch3]
- Computational Indistinguishability
Indistinguishability

- Indistinguishability, Hybrid Lemma, Pseudo-randomness
- Next-bit Test, Pseudo-random generators
- Pseudo-random generators

Constructions based on permutations and hard-core bits, Example construction based on discrete log

- Hard-core bits from any one-way function.
The Goldreich-Levin Theorem. Hard-core functions. The XOR Lemma.

- Pseudo-random generators & Functions

One-bit expansion to Many-bit expansion constructions, definitions of pseudo-random functions

- PRFs and Private-key Encryption

Construction of a PRF, applications to encryption

- Private-key Encryption

Many-message Encryption, CPA, CCA Encryption

- Public-key Encryption

General constructions from permutations and hard-core bits

- Public-key Encryption
El Gamal

- Knowledge
- Interactive Proofs
Examples of Waldo, Graph Isomorphism

- Interactive Proofs + Zero-Knowledge
Definition, construction for Graph-Isomorphism

- Zero-knowledge
Definition, 3-coloring protocol for NP languages

- Commitments
- Semantical Security
Knowledge-based definitions of encryption. Equivalence with indistinguishability-based definitions.

- Witness Indistinguishability
- Authentication
- Digital Signatures
Definitions and Constructions

- Hash functions
- Message Authentication Codes
- Zero-Knowledge based Authentication
- Computing on Secret Inputs
- Secret Sharing
- Secure Computation
Oblivious Transfer.

General secure computation. - Composability
- Composability of Encryption schemes
- Composability of Zero-Knowledge proofs