MAT302 (Winter 2012): Algebraic Cryptography


Course Information

INSTRUCTOR Vinod Vaikuntanathan
Office: 3073 CCT Building
E-mail: firstname.lastname@utoronto [dot] ca
WHEN & WHERE Mondays: 1-2pm at IB 370
Wednesdays: 1-3pm at IB 379
Tutorial (Fri): 10-11am at IB 360
OFFICE HOURS Wednesdays 3-4pm (and by appointment)
TEXTBOOK We have a recommended textbook that we will more or less follow through the course. In cases where the material taught is not readily available online, I will try to provide course notes or other online references.
  • Recommended: Christof Paar and Jan Pelzl, Understanding Cryptography: A Textbook for Students and Practitioners, Springer, 2nd Ed. Available online via the UofT Libraries!
  • Reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Available online at
  • Reference: Thomas Cormen, Charles Leiserson and Ronald Rivest, Introduction to Algorithms, The MIT Press.
GRADING Five problem sets (for a total of 35%), class participation (5%), a midterm (20%) and a final (40%). Problem Sets are due in the beginning of the class.

All this information (and more) can be found in the course information sheet.

See here for the policy on special consideration in case of late assignment submissions.

Students should become familiar with and are expected to adhere to the Code of Behaviour on Academic Matters, which can be found in the UTM Calendar or at: (Academic Honesty) (Advice on avoiding plagiarism).

Course Description

The course will take students on a journey through the methods of algebra and number theory in cryptography, from Euclid to Zero Knowledge Proofs. Topics include: Block ciphers and the Advanced Encryption Standard (AES); Algebraic and Number-theoretic techniques and algorithms in Cryptography, including methods for primality testing and factoring large numbers; Encryption and Digital Signature systems based on RSA, Factoring, Elliptic Curves and Integer Lattices; and Zero-Knowledge Proofs.

Prerequisites: MAT223H5 Linear Algebra I, MAT224H5 Linear Algebra II, MAT301H5 Groups and Symmetries.

Problem Sets

Supplementary Material for the Lectures

Schedule (subject to change)

Lecture Topic Announcements Problem Sets
Lecture 1 (Jan 2) Administrivia. a one-hour version of the course. [ supplementary material ]
Lecture 2 (Jan 4) The Caesar and Affine Ciphers. Some Basic Number Theory -- the groups Zn and Z*n and the Euler Totient Function. Problem Set 1 posted;
due Jan 16 in class.
Lecture 3 (Jan 9) The Vigenere Cipher. Frequency Analysis attacks.
Lecture 4 (Jan 11) Perfect Security and the One-time Pad. The (extended) Euclidean Algorithm
Lecture 5 (Jan 16) Problem Set 1 due in class
Lecture 6 (Jan 18) Problem Set 2 posted;
due Jan 30 in class.
Lecture 7 (Jan 23)
Lecture 8 (Jan 25)
Lecture 9 (Jan 30) Problem Set 2 due in class
Problem Set 3 posted;
due Feb 13 in class.
Lecture 10 (Feb 1)
Lecture 11 (Feb 6)
Lecture 12 (Feb 8)
Lecture 13 (Feb 13) Problem Set 3 due in class
Problem Set 4 posted;
due Mar 12 in class
(You have 4 weeks for this pset!)
Lecture 14 (Feb 15)
Feb 20--24 Reading Week -- NO CLASSES
Lecture 15 (Feb 27)
Lecture 16 (Feb 29) MIDTERM (in class)
Lecture 17 (Mar 5)
Lecture 18 (Mar 7)
Lecture 19 (Mar 12) Problem Set 4 due in class
Lecture 20 (Mar 14)
Lecture 21 (Mar 19)
Lecture 22 (Mar 21) Problem Set 5 posted;
due Apr 2 at 1pm in the instructor's office CCT 3073
Lecture 23 (Mar 26)
Lecture 24 (Mar 28)