Skip to main content Link Menu Expand (external link) Copy Copied

CIS 5560: Cryptography

Spring 2024

Basics

Instructor: Pratyush Mishra
Time: Tuesdays and Thursdays, 1:45PM-3:15PM
Location: Fagin Hall 118
Office hours: Thursday 4:30-5:30PM, Towne 219B
Useful links: Ed Discussions; Canvas; Gradescope

Course description

This course is an introduction to the theory and applications of cryptography intended for advanced undergraduates and graduate students. Topics covered include:

We will also cover a selection of more advanced topics such as identification protocols, zero-knowledge proofs, secure multiparty computation, and homomorphic encryption.

Prerequisites

This course requires a basic background in discrete mathematics (at the level of CIS 1600). Prior exposure to algorithms and complexity (at the level of CIS 3200) will be helpful.

Grading

Your grade in the course is determined by the following components:

Course staff

Resources

While there is no required textbook for the course, the following books are recommended:

Schedule

The schedule below is tentative, and will likely be updated as the course progresses.

DateTopicReadings
01/18/24 Lecture Introduction and overview [Slides]
  • Logistics and course overview
  • Recap of discrete probability
  • Perfect Secrecy and Indistinguishability
  • One Time Pad
  • Shannon's Theorem
  • AC 2.1
  • MC 2
01/23/24 Lecture Computational indistinguishability and pseudorandomness [Slides]
  • Negligible functions
  • Computational indistinguishability
  • Pseudorandom generators
  • AC 3.1-3.3
  • MC 3.2, 3.3
01/25/24Lecture One-way functions and permutations [Slides]
  • Stream ciphers
  • Semantic security
  • AC 3.1-3.3
  • MC 3.2, 3.3
  • MC 8.1, 8.4
01/30/24Lecture One-way functions [Slides]
  • Next-bit Unpredictability
  • One-way functions
  • One-way permutations
  • Hardcore predicates
  • AC 3.1-3.3
  • MC 3.2, 3.3
  • MC 8.1, 8.4
02/01/24Lecture OWFs -> PRGs [Slides]
  • Hardcore predicates
  • OWPs + Hardcore predicates -> PRGs
  • PRG length extension
  • AC 5
  • MC 3.4
02/06/24Lecture Pseudorandom functions [Slides]
  • Pseudorandom functions (PRFs)
  • PRFs from PRGs
  • Pseudorandom permutations (PRPs)
  • Block ciphers
  • AC 4.1, 4.4, 4.6
  • MC 3.5
02/08/24Lecture Encryption for multiple messages [Slides]
  • Attacks on prior schemes
  • Security for multi-message encryption
  • Nonce-based encryption
  • Randomized encryption
  • AC 5
  • MC 3.4
02/13/24Lecture
Message integrity [Slides]
  • Message Authentication Codes (MACs)
  • PMAC
  • CBC-MAC
  • AC 6.1,6.3
  • MC 4.1-4.4
02/15/24Lecture Collision-resistant hashing [Slides]
  • Merkle-Damgard
  • MACs from CRH
  • HMAC
  • AC 8.1, 8.4, 8.7
  • MC 6.1-6.3
02/20/24Lecture Authenticated Encryption [Slides]
  • Attacks
  • MAC-then-Encrypt
  • Encrypt-then-MAC
  • AC 9
  • MC 5
02/22/24 Lecture
Number theory background [Slides]
  • Arithmetic modulo primes
  • Fermat's Little Theorem
  • Quadratic residuosity
  • Discrete Logarithm
  • Arithmetic modulo composites
  • Euler's Theorem
  • Factoring
  • AC Appendix A
  • MC 9
02/27/24 Lecture Key exchange [Slides]
  • Key exchange
  • Merkle puzzle
  • Diffie-Hellman
  • AC 10.1, 10.4, 10.8
  • MC 11
02/29/24 Lecture Public key encryption [Slides]
  • Public key encryption
  • El Gamal encryption
  • Hybrid encryption
  • AC 11
  • MC 12.1-12.4
03/05/24No class due to spring break 
03/07/24No class due to spring break 
03/12/24LectureTBD 
03/14/24Midterm Midterm in class
    03/19/24 Lecture RSA [Slides]
    • Trapdoor functions and permutations
    • RSA Assumption
    • RSA Encryption
    • MC 12.5
    03/21/24 Lecture Digital signatures [Slides]
    • Definition
    • Signatures from RSA
    • Signatures from El Gamal
    • AC 13
    • MC 13
    03/26/24Lecture TBD
      03/28/24 Lecture TBD
          04/02/24Lecture TBD
            04/04/24Lecture TBD
              04/09/24Lecture TBD
                  04/11/24Lecture TBD
                    04/16/24Lecture TBD
                        04/18/24LectureTBD 
                        04/23/24Lecture TBD
                            04/25/24LectureTBD
                              04/30/24LectureTBD 

                              Overview of course grade components

                              Homework

                              Homework is released on Canvas at Tuesday 12PM, and is due the following Monday at 5PM. Homework submissions are to be made on Gradescope. Your lowest 2 homework scores will be dropped. Please use the template here.

                              You are encouraged to discuss homework problems with your classmates, but you must write up your solutions on your own. In particular, you must adhere to Penn’s Code of Academic Integrity; for more information, see the Office of Student Conduct.

                              Participation

                              You are expected to attend lectures and participate in class and on EdStem.

                              Exams

                              The course has two exams: a midterm and a final. The midterm will be held in class on March 14th (03/14/2024), and the final will be held on TBD.

                              Students with disabilities

                              The University of Pennsylvania provides reasonable accommodations to students with disabilities who have self-identified and received approval from the Office of Student Disabilities Services (SDS). If SDS has approved your request for accommodations, please make an appointment to meet with me as soon as possible in order to discuss the arrangements for your accommodations. SDS services are free and confidential.

                              Wellness

                              Your emotional and physical wellness is a priority for us. We are aware of the stress you are under. If you find yourself needing help, please don’t hesitate to reach out to us if you encounter any extenuating circumstances.

                              Please also be aware of the following resources you can reach out to for help:

                              Inclusion and belonging

                              At Penn, in the CIS department, and in this class, we strive to create an environment that is inclusive and welcoming to all students, regardless of their race, ethnicity, gender identity, sexuality, or socioeconomic status. All our faculty and staff are committed to making your studies here at Penn a safe and rewarding experience. You belong here, and we are here to support you. If you have any concerns or experiences that make you feel unwelcome, please feel reach out to any of us.