CS 494 Introduction to Cryptography (Fall 2021)

Course Overview

This course is an introduction to modern cryptography, from both foundational and practical perspectives.

  • For foundational cryptographic primitives and algorithms such as encryption schemes, pseudorandom generators, hash functions, message authentication codes, etc., we will see what security guarantees are desirable, how to properly dene these security guarantees, and how to design cryptographic primitives and algorithms that satisfy them.

  • For cryptosystems widely used in practice including DES, SHA, Diffie-Hellman, etc., we will see precisely how these practical cryptosystems are built, and what security level they achieve in various scenarios.

  • Time permitting, more advanced topics will also be covered, such as fully homomorphic encryption, zero-knowledge proofs, secure computation, blockchain and cryptocurrency.

By the end of this course, you will gain a good understanding of both foundations and practice of cryptography. You will be able to design and analyze real-world cryptosystems as well as understand a good portion of cryptography research papers and standards.

Basic Information

Lecture Time: 2:00 - 3:15pm, Tuesdays and Thursdays

Instructor: Peihan Miao

Lecture Location: Science & Engineering South Room 238

Zoom Information:

Office Hour: 3:30 - 4:30pm Thursdays or by appointment

Office Hour Location: Science & Engineering Offices Room 1136 or on Zoom

Students are expected to attend on-campus lectures if they

  • Have received a COVID-19 vaccination (full vaccination series complete),

  • Have received a vaccine exemption and are saliva testing two times per week and completing their daily Healthcheck, or

  • Are partially vaccinated and are saliva testing two times per week and completing their daily Healthcheck.

All students are expected to WEAR A MASK that is tight-fitting and covers both the mouth and nose in the classroom at all time, regardless of vaccination status. Please do not come to campus if you have COVID-19 symptoms or if you are tested positive for COVID-19. Read more about the guidelines here.

All the lectures will be recorded and will be available online in a day after each lecture.

Prerequisites

(a) CS 251 and (b) STAT 381 or IE 342 or STAT 401. CS 401 is highly recommended.

Specifically, we will assume familiarity with basic (discrete) probability and modular arithmetic. Students enrolled are also expected to have had some exposure to algorithms, mainly to be comfortable reading pseudocode and to be familiar with big-O notation.

Class announcements and homework submission

We will be using Piazza for all course announcements, homework release, discussions, etc. and Gradescope for grading (homework, midterm, and final).

Textbook and Readings

This course will follow the book Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell, 3rd edition. The textbook is available for purchase at the UIC Bookstore.

Here are some other excellent (and mostly free) resources:

Grading and Policies

  • 20% Regular attendance and active participation in class

  • 30% Homework (best 5 out of 6)

  • 20% In-class midterm (Tue Oct 12)

  • 30% On-campus final exam (Wed Dec 8, 3:30-5:30pm)

You are encouraged to work on homework problems with fellow students; however, you must always write up the solutions on your own and explicitly acknowledge everyone whom you have worked with or who has given you any significant ideas about the homework. Similarly, you may use books or online resources to help solve homework problems, but you must always credit all such sources in your write-up and you must never copy material verbatim. At no time should you be in possession of another student's solution. Any late submission of the homework will NOT be accepted.

Tentative Schedule

  • Aug 24, Lecture 1
    Topics:     Introduction. Historical Ciphers.
    Textbook chapters: 1.1-1.3

  • Aug 26, Lecture 2 (HW1 release)
    Topics:     Perfectly secret encryption and limitations. One-time pad.
    Textbook chapters: 2.1-2.3

  • Aug 31, Lecture 3
    Topics:     Computational security. Definition of computationally secure encryption (EAV-security).
    Textbook chapters: 3.1, 3.2.1

  • Sept 2, Lecture 4
    Topics:     Pseudorandom generator (PRG). Construction of EAV-secure encryption scheme from PRG. Proof by reduction.
    Textbook chapters: 3.3

  • Sept 7, Lecture 5 (HW1 due)
    Topics:     Chosen-plaintext attacks (CPA) and CPA-security. Pseudorandom function (PRF).
    Textbook chapters: 3.4.2, 3.5.1

  • Sept 9, Lecture 6 (HW2 release)
    Topics:     Construction of CPA-secure encryption scheme from PRF. Hybrid argument.
    Textbook chapters: 3.5.2

  • Sept 14, Lecture 7
    Topics:     More examples of technical proofs. Homework review.

  • Sept 16, Lecture 8
    Topics:     Definition of message authentication code (MAC).
    Textbook chapters: 4.1-4.2

  • Sept 21, Lecture 9 (HW2 due)
    Topics:     Fixed-length MAC and CBC-MAC.
    Textbook chapters: 4.3.1, 4.4.1

  • Sept 23, Lecture 10 (HW3 release)
    Topics:     Chosen-ciphertext attacks (CCA) and CCA-security. Definition and generic constructions of authenticated encryption.
    Textbook chapters: 5.1-5.2, 5.3.1

  • Sept 28, Lecture 11
    Topics:     Generic constructions of authenticated encryption schemes.
    Textbook chapters: 5.3.1

  • Sept 30, Lecture 12
    Topics:     Definition of collision resistant hash function (CRHF). Merkle–Damgård transform. MAC from CRHF.
    Textbook chapters: 6.1.1, 6.2, 6.3.1

  • Oct 5, Lecture 13 (HW3 due)
    Topics:     Attacks and applications of hash functions.
    Textbook chapters: 6.4.1, 6.6

  • Oct 7, Lecture 14
    Topics:     Midterm review.

  • Oct 12, In-class midterm

  • Oct 14, Lecture 15 (HW4 release)
    Topics:     Stream ciphers and practical constructions. Block ciphers. Substitution permutation network (SPN).
    Textbook chapters: 3.6.1, 7.1, 7.2.1

  • Oct 19, Lecture 16
    Topics:     Attacks on low-round SPN. Feistel network. DES.
    Textbook chapters: 7.2.1-7.2.3

  • Oct 21, Lecture 17
    Topics:     Block cipher modes of operation. Practical hash functions.
    Textbook chapters: 3.6.3, 7.3

  • Oct 26, Lecture 18 (HW4 due)
    Topics:     Basic group theory. Factoring and RSA assumptions. Diffie-Hellman assumptions.
    Textbook chapters: 9.1.1-9.1.3, 9.2.4, 9.3.2

  • Oct 28, Lecture 19 (HW5 release)
    Topics:     Diffie-Hellman key exchange. CPA-secure public-key encryption. El Gamal encryption.
    Textbook chapters: 11.3, 12.1, 12.2.1, 12.4.1

  • Nov 2, Lecture 20
    Topics:     RSA encryption. CCA security. Homework review.
    Textbook chapters: 12.5.1, 12.5.3, 12.2.3

  • Nov 4, Lecture 21
    Topics:     Definition of digital signature. Hash-and-sign paradigm. RSA-based signatures.
    Textbook chapters: 13.1-13.3, 13.4.1

  • Nov 9, Lecture 22 (HW5 due)
    Topics:     Signatures from the discrete-logarithm problem.
    Textbook chapters: 13.5.1-13.5.2

  • Nov 11, Lecture 23 (HW6 release)
    Topics:     Homework review.
    Nov 16, Lecture 24
    Special     topic: Fully homomorphic encryption (FHE).
    References: A conceptually simple construction by Dijk et al.'10, Gentry'10.

  • Nov 18, Lecture 25
    Special topic:     Zero-knowledge proofs.
    References: ZK proofs for all NP languages covered in Lindell's Notes, Chapter 7.

  • Nov 23, Lecture 26
    Special topic:     Secure multi-party computation (MPC).
    References: Surveys and overviews of MPC by Lindell'20, Lindell-Pinkas'08.

  • Nov 25, Thanksgiving holiday (no lecture)

  • Nov 30, Lecture 27 (HW6 due)
    Special topic: Blockchain and cryptocurrencies.
    References: Bitcoin white paper by Nakamoto'08.

  • Dec 2, Lecture 28
    Topics:     Final review.