Course:Introductory:Fall 2007

From CRYPTUTOR

Jump to: navigation, search
[edit]

Theoretical Foundations of Cryptography, an introductory course

Second Edition: Fall 2007

[edit]

Roadmap (high-level)

  • Private-key encryption, definitions of security IND-CPA and SIM-CPA, construction using PRFs. (On the way we'll cover notions of computational indistinguishability and pseudorandomness; for building PRFs we'll learn about tools including one-way functions/permutations and hard-core predicates for them, and PRGs. We'll also see proof techniques like simulation and hybrid arguments. By this point you would have been exposed to the language and the methods of the field, and can expect to pick up the following concepts more easily.)
  • Public-Key encryption; an example: Elgamal encryption. Generalized to constructions based on trapdoor permutations. (On the way we'll see some simple group theoretic concepts, and a classic "hardness assumption" namely the Decisional Diffie-Hellman assumption.)
  • Non-malleable encryption: Problem with SIM-CPA. Strengthening it to be "non-malleable," or secure against "chosen ciphertext attack." (This leads to the state-of-the-art in encryption.)
  • Message authentication codes (MAC)/digital signatures. Application of MAC to non-malleable encryption. Construction of MACs and signatures. (On the way we will learn about some notions of cryptographic hash functions.)
  • Final part of the course is a selection of topics. A small selection of features for encryption and authentication constructs. One big concept is of "secure function evaluation" or "multiparty computation" protocols. We will see (the basics of) fascinating concepts including "zero-knowledge proofs," "commitment protocols," "oblivious transfer" and "garbled circuit evaluation," all of which contribute towards realizing multiparty computation. Another fundamental and powerful concept we shall look at is of "secret-sharing." The final topic we will cover is "obfuscation."
[edit]

List of Lectures

  • Lecture 0
Introduction, The Edifice of Cryptography, Course contents.
  • Lecture 1
One-Message Shared-key Encryption. Definitions: Perfectly secret encryption and SIM-onetime security. Construction: One-time pad.
  • Lecture 2
One-Message Shared-key Encryption. Equivalence of Definitions.
Computational Considerations: PPT, Security parameter, Negligible function, Computational indistinguishability, SIM-CPA security, IND-CPA security, Pseudorandomness generator (PRG), Next-bit unpredictable PRG, Stream cipher.
  • Lecture 4
Equivalence of NBU PRG and IND-PRG, Building a PRG from a one extra bit PRG in turn from a one-way permutation and its hardcore predicate. Proofs using hybrid arguments.
  • Lecture 5
One-way functions (also Weak one-way functions, one-way function collections, one-way permutations, regular one-way functions, enhanced one-way functions). Example candidates: Rabin collection, RSA collection. Hardcore predicates and hardcore functions, Goldreich-Levin predicate.
  • Lecture 6
Stream cipher from a PRG, Stateful-SIM-CPA secure shared-key encryption using a stream cipher, block ciphers, pseudorandom functions (PRFs), constructing a PRF from a PRG.
Block ciphers, IND-CPA private-key encryption using CTR mode of operation of a block cipher. Pseudorandom permutations (and strong PRPs). Luby-Rackoff construction.
  • Lecture 8
Public-key encryption, SIM-CPA and IND-CPA security for public-key encryption. Diffie-Hellman key exchange and introduction to Decisional Diffie-Hellman assumption and Elgamal encryption scheme.
  • Lecture 9
Elgamal encryption scheme and its proof of security under Decisional Diffie-Hellman Assumption. Group of quadratic residues (\mathbb{QR}^*_P) modulo a safe prime P, where the DDH assumption is considered to hold. Trapdoor pseudorandomness generator for IND-CPA public-key encryption. Trapdoor PRG from DDH assumption. Building Trapdoor PRG from Trapdoor one-way permutations.
  • Lecture 10
Examples of a Trapdoor OWP based/depending on the hardness of factoring, Rabin trapdoor permutation and RSA trapdoor permutation. Algebra Background: Chinese remainder theorem, multiplicative group modulo the product of two primes (\mathbb{Z}^*_{PQ}) and its subgroup of quadratic residues (\mathbb{QR}^*_{PQ}). Blum integers.
Chosen-ciphertext attack: An example. Security against CCA: SIM-CCA security and IND-CCA security
  • Lecture 12
Equivalence of SIM-CCA and IND-CCA. Message Authentication Codes (MAC). Using MACs to construct an IND-CCA secure private-key encryption scheme from an IND-CPA private-key encryption scheme.
  • Lecture 13
SIM-CCA secure public-key encryption schemes: Cramer-Shoup encryption scheme. Hybrid encryption. Random oracle model.
  • Lecture 14
Message Authentication Codes (MAC).
  • Lecture 15
Hash functions and collision resistance. Birthday attack. Universal hash function, Universal one-way hash functions (UOWHFs) and Collision Resistant Hash Functions (CRHFs). Pre-image collision resistance and second pre-image collision resistance.
  • Lecture 16
Digital signatures and comparison with MACs. Comparison with public-key encryption (and why inverse of encryption is not a secure signature). Lamport's one-time signature scheme.
  • Lecture 17
Digital signatures continued: Using CRHFs for signing longer messages. A stateful signature scheme using a tree of signed keys. A digital signature scheme using a one-time signature scheme, a CRHF and a PRF. More efficient scheme in the random oracle model.
Recap of secure communication. Cryptographic essentials in Transportation Layer Security (TLS).
  • Lecture 19
Secret-sharing, Shamir's secret-sharing scheme for threshold access structures, Linear secret-sharing schemes, Verifiable secret-sharing.
  • Lecture 20
Introduction to Secure multiparty computation. Examples: oblivious transfer and commitment. Passive vs. active adversary.
  • Lecture 21
Yao's garbled circuit for 2-party secure function evaluation against passive adversaries.
  • Lecture 22
Commitment Schemes Introduction to zero-knowledge proofs. A classical statistically binding commitment scheme and a classical zero-knowledge proof protocol for graph 3-colorability SZK Statistical Difference Constructions and Lower Bounds.
Composition of zero-knowledge proof protocols.
Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Course:Introductory:Fall_2007"
Personal tools