Course:Introductory:Fall 2006

From CRYPTUTOR

Jump to: navigation, search

1 Theoretical Foundations of Cryptography, an introductory course

[edit]

Theoretical Foundations of Cryptography, an introductory course

[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. The constructions in the public-key settingare fairly advanced and we shall omit the details. We will see the constructions in the private-key setting shortly.)
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. 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

Course contents: "Old stuff" (but in a modern perspective) related to secure communication (encryption and authentication), and a little bit of the "modern stuff" related to secure computation (multi-party computation, obfuscation). Concepts and tools for all this: randomness, computational hardness, probability based definitions of security, proofs of security as reductions, and various primitives and tools like one-way and trapdoor functions, pseudorandomness generators, pseudorandom functions, commitment schemes, secret-sharing schemes and zero-knowledge proofs.

Lecture 1

One-time pad for perfectly secret encryption and equivalent definitions IND-onetime and SIM-onetime.

Lecture 2

Chosen Plaintext Attack security: IND-CPA and SIM-CPA and their equivalence.

Assignment 1

Lecture 3

Introduction to pseudorandomness generators and pseudorandom functions and their use in private-key encryption.

Lecture 4

Security parameter and negligible functions. Computational indistinguishability. One-way functions, hard-core predicates, introduction to building a PRG from a one extra bit PRG, in turn from one-way permutations. Introduction to hybrid arguments.

Lecture 5

Building a PRG from a one extra bit PRG, proof using a hybrid argument. Uniform and non-uniform adversaries.

Lecture 6

Next Bit Unpredictable PRG, and its equivalence to PRG.

Assignment 2

Lecture 7

A candidate one-way permutation. Pseudorandom functions, the GGM PRF and introduction to its proof of security.

Lecture 8

Proof of security of the GGM PRF. 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 9

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 10

Elgamal encryption scheme and its proof of security under Decisional Diffie-Hellman Assumption. Example of a group where the DDH assumption is believed to hold (and one where it does not hold, though Discrete Logarithm Assumption is believed to hold). Algebra Background: Group of integers modulo an integer ( $\mathbb{Z}_n$ ) and in particular modulo a prime ( $\mathbb{Z}_P$ ), Multiplicative group modulo a prime ( $\mathbb{Z}^*_P$ ) and its subgroup of quadratic residues ( $\mathbb{QR}^*_P$ ). Safe primes.

Assignment 3

Lecture 11

Trapdoor pseudorandomness generator for IND-CPA public-key encryption. Trapdoor PRG from DDH assumption. Building Trapdoor PRG from Trapdoor one-way permutations.

Lecture 12

Example of Trapdoor PRG (based on a version of the RSA assumption). Example of a Trapdoor OWP (namely, squaring in the group of quadratic residues modulo a product of large primes). 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.

Lecture 13

Chosen-ciphertext attack: An example. Security against CCA: SIM-CCA security and IND-CCA security, and their equivalence.

Lecture 14

Equivalence of SIM-CCA and IND-CCA (continued). 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 15

Hybrid encryption. Proof of SIM-CPA security of hybrid encryption using SIM-CPA public-key and SIM-onetime provate-key encryption schemes. Homomorphic encryption. Identity-based encryption. Anonymous encryption.

Lecture 16

Message Authentication Codes (MAC). Constucting a MAC from a pseudorandom function, first for fixed-length messages and then extending it to general messages. CBC-MAC for fixed length messages, and its extensions to general messages.

Lecture 17

Class Test 1

Lecture 18

Solutions for class test 1, and review of concepts involved.

Lecture 19

Collision Resistant Hash Functions (CRHFs) for various notions of collision resistance. Birthday attack. Merkle-Damgard hashes. Description of NMAC and assumptions for its security. HMAC. Handout on MACs and CRHFs (from book by Katz and Lindell; available with Mike)

Lecture 20

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. Handout-1 on Digital signatures (from book by Katz and Lindell; available with Mike)

Lecture 21

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. Handout-2 on Digital signatures (from book by Katz and Lindell; available with Mike)

Assignment 4

Lecture 22

Universal one-way hash functions (UOWHFs). Comparison with CRHFs. Constructing a UOWHF from a one-way permutation and a universal hash function. Composition of UOWHFs to extend input-length. Comparison with Merkle Trees for CRHFs. Digital signatures using UOWHF. Encryption/Authentication wrap-up. Random oracle methodology. Handout on RSA-OAEP and RSA-PSS; available with Mike)

Lecture 23

Class Test 2

Lecture 24

Canceled.

Lecture 25

Secure multiparty computation (MPC): what it is, how it is qualitatively different from secure communication, and how to define its security. Restricted variants: two-party computation, honest-but-curious adversary model, and MPC in restricted environments. A protocol for secure two-party computation of arbitrary functions: Yao's garbled circuit, using oblivious transfer.