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

CIS 5560: Cryptography

Spring 2024


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.


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.


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

Course staff


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


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

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
Message integrity [Slides]
  • Message Authentication Codes (MACs)
  • PMAC
  • AC 6.1,6.3
  • MC 4.1-4.4
02/15/24Lecture Message integrity [Slides]
  • Message Authentication Codes (MACs)
  • PMAC
  • AC 6.1,6.3
  • MC 4.1-4.4
02/20/24Lecture Collision-resistant hashing [Slides]
  • Merkle-Damgard
  • MACs from CRH
  • HMAC
  • AC 8.1, 8.4, 8.7
  • MC 6.1-6.3
02/22/24 Lecture
Authenticated Encryption [Slides]
  • Attacks
  • MAC-then-Encrypt
  • Encrypt-then-MAC
  • AC 9
  • MC 5
02/27/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/29/24 Lecture Key exchange [Slides]
  • Key exchange
  • Merkle puzzle
  • Diffie-Hellman
  • AC 10.1, 10.4, 10.8
  • MC 11
03/05/24No class due to spring break 
03/07/24No class due to spring break 
03/12/24LectureReview of material 
03/14/24Midterm Midterm in class
    03/19/24 LectureMidterm review
    03/21/24 Lecture Public key encryption [Slides]
    • Public key encryption
    • El Gamal encryption
    • Hybrid encryption
    • AC 11
    • MC 12.1-12.4
    03/26/24Lecture RSA [Slides]
    • Trapdoor functions and permutations
    • RSA Assumption
    • RSA Encryption
    • AC 11.4
    • MC 12.5
    03/28/24 Lecture In-class notebook for PKE [Notebook]
    04/02/24Lecture Digital signatures I [Slides]
    • Definition of signatures
    • One-time signatures
    • AC 13
    • MC 13
    04/04/24Lecture Digital signatures II [Slides]
    • One-time -> Many-time signatures
    • Signatures from trapdoor functions
    04/09/24Lecture Zero Knowledge and Interactive Proofs [Slides]
        04/11/24Lecture ZK II [Slides]
          04/16/24Lecture ZK III [Slides]
            04/18/24Lecture ZK IV [Slides]
              04/23/24Lecture MPC I [Slides]
                04/25/24Lecture MPC II [Slides]
                  04/30/24Lecture MPC III and Wrap up [Slides]

                    Overview of course grade components


                    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.


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


                    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 May 10th (05/10/2024) 9AM-11AM in DRLB A2.

                    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.


                    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.