• Introduction [Ch1] [KL 1,2]
    1. Introduction & Overview
    2. 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]
    1. One-way Functions and Computationally bounded adversaries.

      Randomized Efficient Algorithms. One-way functions (OWF). Weak and Strong OWFs.

    2. Computational Number Theory.

      Euclid’s Algorithm, Modular Exponentiation, Basic group
      theory, Euler’s and Fermat’s Theorems, Primes.

    3. Computational Hardness.

      Factoring assumption and
      the Discrete log assumptions. One way permutation
      and Trapdoor permutations.

    4. Collections of OWFs.
  • Indistinguishability and Pseudo-Randomness [Ch3]
    1. Computational Indistinguishability


    2. Indistinguishability, Hybrid Lemma, Pseudo-randomness
    3. Next-bit Test, Pseudo-random generators
    4. Pseudo-random generators

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

    5. Hard-core bits from any one-way function.

      The Goldreich-Levin Theorem. Hard-core functions. The XOR Lemma.

    6. Pseudo-random generators & Functions

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

    7. PRFs and Private-key Encryption

      Construction of a PRF, applications to encryption

    8. Private-key Encryption

      Many-message Encryption, CPA, CCA Encryption

    9. Public-key Encryption

      General constructions from permutations and hard-core bits

    10. Public-key Encryption

      El Gamal

  • Knowledge
    1. Interactive Proofs

      Examples of Waldo, Graph Isomorphism

    2. Interactive Proofs + Zero-Knowledge

      Definition, construction for Graph-Isomorphism

    3. Zero-knowledge

      Definition, 3-coloring protocol for NP languages

    4. Commitments
    5. Semantical Security

      Knowledge-based definitions of encryption. Equivalence with indistinguishability-based definitions.

    6. Witness Indistinguishability
  • Authentication
    1. Digital Signatures

      Definitions and Constructions

    2. Hash functions
    3. Message Authentication Codes
    4. Zero-Knowledge based Authentication
  • Computing on Secret Inputs
    1. Secret Sharing
    2. Secure Computation

      Oblivious Transfer.
      General secure computation.

  • Composability
    • Composability of Encryption schemes
    • Composability of Zero-Knowledge proofs

Leave a Reply